A V-shape property of optimal schedule of jobs about a common due date (Q1069850): Difference between revisions

\textit{J. J. Kanet} [Nav. Res. Logist. Q. 28, 643-651 (1981; Zbl 0548.90037)] considered the problem of minimizing the average deviation of job completion times about a common due date when the due date exceeds the make-span of the job set. In this note we establish the V-shape of an optimal schedule for any common due date. The V-shape means that in the optimal schedule the jobs are processed according to decreasing order of processing times until the job with the shortest processig time is completed and then the jobs are scheduled according to increasing order of processing times. \textit{S. Eilon} and \textit{I. G. Chowdhury} [Manage. Sci. 23, 567-575 (1977; Zbl 0362.90051)] proved the V-shape of optimal schedules for yet another class of single machine sequencing problems.