Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9663766 | European Journal of Operational Research | 2005 | 14 Pages |
Abstract
We study a single-machine scheduling problem with the objective of minimizing a linear combination of total job completion times and total deviation of job completion times from a common due-date. The due-date is assumed to be restrictive, i.e., it may be sufficiently small to have an impact on the optimal sequence. When more weight is allocated to total job completion times, the problem is shown to have a polynomial time solution. When more weight is allocated to total completion time deviations from the due-date, the problem is NP-hard in the ordinary sense. For the latter case, we introduce an efficient dynamic programming algorithm, which is shown numerically to perform well in all our tests.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Gur Mosheiov,