EARLY TARDY SCHEDULING WITH SEQUENCE-DEPENDENT SETUPS ON UNIFORM PARALLEL MACHINES/

We consider the problem of scheduling N jobs on M parallel machines th at operate at different speeds (known as uniform parallel machines), t o minimize the sum of earliness and tardiness costs. Jobs are assumed to arrive in a dynamic albeit deterministic manner, and have nonidenti cal due dates. Violations of due dates result in earliness or tardines s penalties that may be different for different jobs. Setup times are job-sequence dependent and may be different on different machines base d on the characteristics of the machines. For this problem, we present a mixed integer formulation that has substantially fewer zero-one var iables than typical formulations for scheduling problems of this type. We present our computational experience in using this model to solve small sized problems, and discuss solution approaches for solving larg er problems. (C) 1998 Elsevier Science Ltd. All rights reserved.