Optimal slack due-date determination and sequencing

This paper considers the n-job, single-machine sequencing problem with slack (SLK) due-dates. The objective is to determine the optimal value of the slack allowance k* and the optimal job sequence σ* to minimize a cost function based on the slack allowance and the job earliness and tardiness values. A linear-programming formulation of the problem is proposed and the optimal slack allowance is derived through solving the LP dual problem. It is shown that for a problem in the general form the optimal job sequence cannot be determined, but under a special condition it can elegantly be established. After the theoretical treatment, a numerical example is given for discussion.