Simpler and Faster Algorithm for Optimal Total-Work-Content-Power Due Date Determination

摘要

Due date determination problems comprise scheduling problems in which not only the scheduling of jobs is involved, but the assignment of due dates to jobs as well. The paper considers a special case in the sense that a schedule is given and that there is a single decision variable involved: the due data multiplier. This multiplier is used to set the due dates in order to minimize a composite objective function. Recently, an algorithm was presented for which its validity was proven on basis of the dual of the linear programming formulation of this problem. The paper gives a simpler and faster algorithm, based upon strictly primal arguments.