A new job shop scheduling heuristic

Job shop scheduling involves solving problems with n jobs and m machines where each job has a specifically defined route that may or may not be the same for all jobs. Thus, all machines may not be required by all jobs and the number of processing stages may not be equal among the jobs. Furthermore, a job may require processing on a particular machine more than once in its routing. Large job shop scheduling problems have been documented as belonging to a class of problems that are NP-Complete. As such, these problems are some of the most intractable to solve. Exact solution methods have been previously developed to optimally solve small job scheduling problems; typically, problems with only a few jobs or few machines. More recent work has included the development and use of heuristics to solve larger problems. A prominently documented heuristic that provides high quality solutions in minimizing makespans is the Shifting Bottleneck Heuristic (SBH). The SBH iteratively searches, identifies, selects, and schedules “bottleneck” machines one at a time until all machines have been scheduled. Several tradeoffs between solution quality and computing times for various heuristics, including the SBH, have been previously assessed and documented in evaluating the performance of these solution techniques. The focus of this research is the development of a new heuristic for job shop scheduling. This new heuristic, named the Deal-Parks Heuristic (DPH), utilizes a procedure that evaluates machine availability and job requirements at each incremental point in a time horizon. If multiple candidate jobs are available for scheduling at a given time, the heuristic employs sequence and processing time matrices to compute the scheduling decision. The DPH performs forward and reverse passes and includes “tie-breaking” criteria to construct a schedule with the smallest makespan. The performance of the DPH is assessed both absolutely and relatively for a set of test problems. Makespans are evaluated absolutely through a procedure for computing the makespan's lower bound. Relative performance is assessed by comparing the DPH's results with those of the SBH. The DPH produced high quality solutions with substantially less computing time.