OPTIMAL SINGLE-MACHINE SEQUENCING AND ASSIGNMENT OF COMMON DUE-DATES

This paper considers an n-job one-machine sequencing problem with common due-dates. The objective is to determine the optimal common due-date value and the optimal job sequence that jointly minimize a cost function which is dependent on the individual job earliness and tardiness values. Using KKuhn-Tucker's optimality conditions for constrained convex programming problems, we show that for a given job sequence, the optimal due-date is a simple function of the number of jobs. This result allows separation of the due-date assignment problem from the job sequencing problem. A well-known theorem in algebra can be applied to solve the latter problem, which in turn yields the optimal solution to the overall problem.