SCHEDULING UNDER A COMMON DUE-DATE ON PARALLEL UNRELATED MACHINES

Due-date determination problems have gained significant attention in r ecent 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. Th e common due-date is a decision variable. The objective is to allocate and sequence the jobs on the machines and to determine the optimal du e-date, so that the total cost be minimised. This cost is composed of the due-date assignment, the total earliness and the total tardiness c ost. As the problem is NP-hard, a polynomial time heuristic procedure, which provides efficient solutions, is developed. The procedure is il lustrated by means of an example and is tested via two small size expe riments. (C) 1998 Elsevier Science B.V.