A heuristic for common due-date assignment and job scheduling on parallel machines

This paper considers the problem of scheduling a set of simultaneously available jobs on several parallel and identical machines. The problem is to find the optimal due-date, assuming this to be the same for all jobs. The paper also seeks to sequence the jobs such that some are early and some are late so as to minimize a penalty function. For the single-machine problem, it presents a simple proof of the well-known optimality result that the optimal due-date coincides with one of the job completion times. The paper shows that the optimal job sequence for the single-machine problem can be easily determined. It proves that the same optimal due-date result can be generalized to the parallel-machine problem. However, determination of the optimal job sequence for such a problem is much more complex, and the paper presents a simple heuristic to find an approximate solution. On the basis of a limited experiment, it observes that the heuristic is very effective in obtaining near-optimal solutions.