Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420988 | Discrete Applied Mathematics | 2006 | 22 Pages |
Abstract
This paper considers single machine scheduling problems in which the job processing times and/or their release dates are controllable. Possible changes to the controllable parameters are either individual or done by controlling the relevant processing or release rate. The objective is to minimize the sum of the makespan plus the cost for changing the parameters. For the problems of this type, we provide a number of polynomial-time algorithms and give a fairly complete complexity classification.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Natalia V. Shakhlevich, Vitaly A. Strusevich,