Processing-plus-wait due dates in single-machine scheduling

We study the problem of schedulingn jobs on a single machine. Each job is assigned a processing-plus-wait due date, which is an affine-linear function of its processing time. The objective is to minimize the symmetric earliness and tardiness costs. We analyze a combined decision model which includes computing both the optimal job sequence and optimal due date parameters. For the quadratic objective function, we propose a heuristic solution based on a bicriterion approach. Additionally, we provide computational results to compare this model with two simpler models. For the maximum objective function, we show that it is efficiently solved by the shortest processing time sequence.Part of this research was undertaken during a visit of the first author at the University of Manitobe, Canada in 1991. This visit was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant OPG0036424. The numerical results were obtained with the assistance of T. P. Lindenthal. The authors are thankful for his help.