Early/tardy scheduling with sequence dependent setups on uniform parallel machines

We consider the problem of scheduling N jobs on M parallel machines that operate at different speeds (known as uniform parallel machines), to minimize the sum of earliness and tardiness costs. Jobs are assumed to arrive in a dynamic albeit deterministic manner, and have nonidentical due dates. Violations of due dates result in earliness or tardiness penalties that may be different for different jobs. Setup times are job-sequence dependent and may be different on different machines based on the characteristics of the machines. For this problem, we present a mixed integer formulation that has substantially fewer zero–one variables 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 larger problems.