2-STAGE HEURISTIC-PROCEDURE FOR SCHEDULING JOB SHOPS

In many job shops, a variety of products of different size batches pas s through different sequences of machines and operations. As jobs and operations increase, computations increase exponentially, and optimal scheduling is essentially unsolvable with reasonable computer power an d time. An alternate approach is to use heuristic scheduling methods t o produce feasible, good (although not necessarily optimal) schedules in cost-effective time. This approach is particularly appropriate in l ow-technology job shops, which generally have modest computing power. A heuristic has been developed for achieving a minimum makespan schedu le for the shop. The heuristic considers both jobs in a given queue an d those yet to arrive at any machine, to sequence the operations to be processed on all machines. It is a single-pass procedure and creates a feasible, near-minimum makespan schedule. A modification (improvemen t) stage is then employed to further improve the schedule. This looks only at a subset of the set of feasible schedules. The sequence of ope rations processed on each machine is interchanged for the job with the maximum makespan such that each interchange introduces minimal distur bance to the existing schedule. Results on benchmark problems indicate that the resulting heuristic is superior to other commonly used heuri stics, and the combined algorithm yields results comparable to several optimal scheduling algorithms, yet with vastly fewer and simpler iter ations.