A fixed interval due-date scheduling problem with earliness and due-date costs

In this paper we consider a problem where N jobs are to be scheduled on a single machine and assigned to one of the two due-dates which are given at equal intervals. Tardy jobs are not allowed, thus the due-dates are deadlines. There is a linear due-date penalty and linear earliness penalty, and the sum of these penalties is to be minimized. This problem is shown to be NP-hard. One case of the problem (the unrestricted case) is shown to be easy to solve. For the restricted case, lower and upper bounds are developed. Computational experience is reported which suggests that the bounds are quite effective.