Simulated annealing for parallel machine scheduling with earliness-tardiness penalties and sequence-dependent set-up times

Scheduling problems with earliness and tardiness penalties are commonly enc ountered in today's manufacturing environment due to the current emphasis o n the just-in-time (JIT) production philosophy. The problem studied in this work is the parallel machine earliness-tardiness non-common due date seque nce-dependent set-up time scheduling problem (PETNDDSP) for jobs with varyi ng processing times, where the objective is to minimize the sum of the abso lute deviations of job completion times from their corresponding due dates. The research presented provides a first step towards obtaining near optima l solutions for this problem using local search heuristics in the framework of a meta-heuristic technique known as simulated annealing (SA). The compu tational study shows that, using the SA methodology, significant improvemen ts to the local search heuristic solutions can be achieved for problems of this type.