An O(n2) algorithm for a controllable machine scheduling problem |
| |
| Authors: | HUANG, WANZHEN ZHANG, FENG |
| |
| Affiliation: | Department of Mathematics and Statistics, School of Mathematical Sciences, Lakehead University Ontario, Canada, P7B 5E1
Department of Applied Mathematics, Shanghai Second Polytechnic University P. R. China |
| |
| Abstract: | A single-machine scheduling problem with controllable processingtimes is discussed in this paper. For some jobs, the processingtime can be crashed up to u units of time with the additionalcost c per unit of time crashed. The object is to find an optimalprocessing sequence as well as crash activities to minimizetotal costs of completion and crash. This problem is shown tobe polynomially solvable, and an O(n2) algorithm is given togetherwith the theoretical proof. |
| |
| Keywords: | Single-machine scheduling problems controllable processing times crash activities polynomial-time algorithm |
| 本文献已被 Oxford 等数据库收录！ |
|
