Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
481734 | European Journal of Operational Research | 2009 | 10 Pages |
Abstract
The classical weighted minsum scheduling and due-date assignment problem (with earliness, tardiness and due-date costs) was shown to be polynomially solvable on a single machine, more than two decades ago. Later, it was shown to have a polynomial time solution in the case of identical processing time jobs and parallel identical machines. We extend the latter setting to parallel uniform machines. We show that the two-machine case is solved in constant time. Furthermore, the problem remains polynomially solvable for a given (fixed) number of machines.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Gur Mosheiov, Assaf Sarig,