1990
A simpler and faster algorithm for optimal total-work-content-power due date determination
Publication
Publication
Mathematical and Computer Modelling p. 81- 83
Due date determination problems comprise scheduling problems in which not only the scheduling of n jobs is involved, but the assignment of due dates to jobs as well. This paper considers the case where a schedule is given and there is a single decision variable involved: the due date multiplier. The multiplier is used to set the due dates in order to minimize a composite objective function. Recently, an O(n2) algorithm was presented, the validity of which was proved on basis of the dual of the linear programming formulation of this problem. We give a simpler and faster algorithm based upon strictly primal arguments, requiring only O(n log n) time. In addition, we point out that these arguments can be employed for alternative proofs in case of a common due date.
| Additional Metadata | |
|---|---|
| , | |
| doi.org/10.1016/0895-7177(90)90373-U, hdl.handle.net/1765/12358 | |
| ERIM Article Series (EAS) | |
| Mathematical and Computer Modelling | |
| Organisation | Erasmus Research Institute of Management |
|
van de Velde, S. (1990). A simpler and faster algorithm for optimal total-work-content-power due date determination. Mathematical and Computer Modelling, 81–83. doi:10.1016/0895-7177(90)90373-U |
|
