Scheduling under a common due-date on parallel unrelated machines

Due-date determination problems have gained significant attention in recent years due to the industrial focus in the just-in-time philosophy. In this paper the problem of scheduling a set of independent jobs on parallel unrelated processors under a common due-date is examined. The common due-date is a decision variable. The objective is to allocate and sequence the jobs on the machines and to determine the optimal due-date, so that the total cost be minimised. This cost is composed of the due-date assignment, the total earliness and the total tardiness cost. As the problem is NP-hard, a polynomial time heuristic procedure, which provides efficient solutions, is developed. The procedure is illustrated by means of an example and is tested via two small size experiments. (C) 1998 Elsevier Science B.V.