Scheduling with alternatives: a link between process planning and scheduling

The objective of this research is to develop and evaluate effective, comput ationally efficient procedures for scheduling jobs in a large-scale manufac turing system involving, for example, over 1000 jobs and over 100 machines. The main performance measure is maximum lateness; and a useful lower bound on maximum lateness is derived from a relaxed scheduling problem in which preemption of jobs is based on the latest finish time of each job at each m achine. To construct a production schedule that minimizes maximum lateness, an iterative simulation-based scheduling algorithm operates as follows: (a ) job queuing times observed at each machine in the previous simulation ite ration are used to compute a refined estimate of the effective due date (sl ack) for each job at each machine; and (b) in the current simulation iterat ion, jobs are dispatched at each machine in order of increasing slack. Iter ations of the scheduling algorithm terminate when the lower bound on maximu m lateness is achieved or the iteration limit is reached. This scheduling a lgorithm is implemented in Virtual Factory, a Windows-based software packag e. The performance of Virtual Factory is demonstrated in a suite of randoml y generated test problems as well as in a large furniture manufacturing fac ility. To further reduce maximum lateness, a second scheduling algorithm al so incorporates a tabu search procedure that identifies process plans with alternative operations and routings for jobs. This enhancement yields impro ved schedules that minimize manufacturing costs while satisfying job due da tes. An extensive experimental performance evaluation indicates that in a b road range of industrial settings, the second scheduling algorithm can rapi dly identify optimal or nearly optimal schedules.