J. Bank et F. Werner, Heuristic algorithms for unrelated parallel machine scheduling with a common due date, release dates, and linear earliness and tardiness penalties, MATH COMP M, 33(4-5), 2001, pp. 363-383
This paper considers a scheduling problem where each of n jobs has to be pr
ocessed without interruption on exactly one of m unrelated parallel machine
s. For each job, a release date and the processing times on each machine ar
e given, and a common due date d is given for all jobs. The objective is to
distribute the jobs to the machines and to schedule the jobs assigned to e
ach machine such that the weighted sum of linear earliness and tardiness pe
nalties is minimal. For this problem, we derive some structural properties
useful in connection with the search for an approximate solution. Furthermo
re, we present various constructive and iterative heuristic algorithms whic
h are compared on problems with up to 500 jobs and 20 machines. (C) 2001 El
sevier Science Ltd. All rights reserved.