SCHEDULING OF MULTIPLE PRODUCTS ON PARALLEL UNITS WITH TARDINESS PENALTIES USING SIMULATED ANNEALING

We present a solution methodology to obtain near-optimal solutions for the problem of scheduling multiple products on a network of single-st age, unrelated parallel units using simulated annealing (SA) with a pe rformance criterion based on tardiness minimization. The approach inco rporates sequence dependent clean-up times, varying processing rates f or different products on different units, and constraints on feasible product-to-unit assignments. Near-optimal solutions are obtained for p roblems with 20-100 products and 3-11 units. A comparison is made betw een solutions obtained by SA, solutions obtained by the heuristic impr ovement method of Musier and Evans for similar computational effort, a nd solutions obtained by a list scheduling algorithm.