MINIMIZING TARDINESS ON A SINGLE PROCESSOR WITH SEQUENCE-DEPENDENT SETUP TIMES - A SIMULATED ANNEALING APPROACH

In today's fast-paced Just-In-Time and mass customization manufacturin g in a sequence-dependent setup environment, the challenge of making p roduction schedules to meet due-date requirements is becoming a more c omplex problem. Unfortunately, much of the research on operations sche duling problems has either ignored setup times or assumed that setup t imes on each machine are independent of the job sequence. This paper c onsiders the problem of minimizing tardiness, a common measure of due- date performance, in a sequence-dependent setup environment. Simulated annealing was used to solve the sequencing problem, and its performan ce was compared with random search. Our experimental results show that the algorithm can find a good solution fairly quickly, and thus can r ework schedules frequently to react to variations in the schedule. The algorithm is invaluable for 'on-line' production scheduling and 'last -minute' changes to production schedule. The results of this research also suggest ways in which more complex and realistic job shop environ ments, such as multiple machines with a higher number of jobs in the s equence, and other scheduling objectives can be modeled. This research also investigates computational aspects of simulated annealing in sol ving complex scheduling problems. (C) 1997 Elsevier Science Ltd. All r ights reserved.