On Minimizing Lmax for Large-Scale, Job Shop Scheduling Problems Scott R. Schultz Department of Mechanical and Industrial Engineering Mercer University Macon, GA 31207 Thom J. Hodgson Department of Industrial Engineering North Carolina State University Raleigh, NC 27695-7906 Russell E. King Department of Industrial Engineering North Carolina State University Raleigh, NC 27695-7906 Phone: (919) 515-5186 FAX: (919) 515-1543 [email protected] (corresponding author) Kristin A. Thoney Department of Textile & Apparel Technology & Management North Carolina State University Raleigh, NC 27695-8301 February 2004 Keywords: scheduling: lateness: job shop: benchmark: simulated annealing: performance bounds1 Abstract: In a recent paper by Hodgson et al. (2000) a procedure is presented for solving the job shop scheduling problem of minimizing Lmax. Their iterative-adaptive simulation-based procedure is shown to perform well on large-scale problems. However, there is potential for improvement in closing the gap between best known solutions and the lower bound. In this paper, a simulated annealing post processing procedure is presented and evaluated on large-scale problems. A new neighborhood structure for local searches in the job shop scheduling problem is developed. The procedure is also evaluated using benchmark problems and new upper bounds are established. 1. Introduction Consider the classic job shop scheduling problem. A set of jobs is to be processed on a set of machines without preemption. Each job has a given technological route, i.e., a specified sequence of operations and required processing times on the machines. All jobs are ready at time 0, and due dates are given for each job i (di). A job can only be processed on one machine at a time, and a machine can only process one job at a time. A job's lateness is its completion time minus its due date (Ci - di). The objective is to sequence the operations on the machines in order to minimize the maximum lateness over all jobs ( }]{maxmin[iiidC − ). Using the Graham, et al. (1979) scheduling notation, this problem is referred to as J//Lmax. The problem was first introduced by Muth and Thompson (1963). Since then, job shop scheduling has been a standard topic in scheduling textbooks (e.g. see Baker, 1974 and Morton and Pentico, 1993). Rinnooy Kan (1976) proved that the job shop problem with the makespan objective is NP-Hard. Furthermore, other authors (see e.g. Adams et al., 1988 and Werner and Winkler, 1995) indicate that not only is the job shop problem NP-Hard, it is one of the worst NP-hard problems. One classical 10x10 job shop problem formulated by Muth and Thompson (1963) was not solved until Carlier and Pinson (1989). Van Laarhoven, et al. (1992) and Matsuo, et al. (1998) used simulated annealing to solve job shop problems with the makespan objective. They compared their simulated annealing approach to three other job shop scheduling heuristics and found superior or equivalent results for most problems. However, the procedure requires significant computational effort.2 Dell’Amico and Trubian (1993), Nowicki and Smutnicki (1996), and Pezzella and Merelli (2000) use various Tabu search heuristics finding optimal or near-optimal solutions on numerous benchmark problems. Demirkol, et al. (1998) established a series of benchmark problems with the intent that researchers could use them to evaluate the effectiveness of their algorithms. For the J//Lmax problem, they posted 160 problems including the best known solutions (upper bounds) along with solution times. Balas, et al. (1998) utilized a shifting bottleneck strategy combined with a guided local search procedure to obtain significant improvement in the upper bounds originally posted. The guided local search procedure searches through a neighborhood tree structure to overcome local optima. To the best of our knowledge, the solutions found by Balas, et al. (1998) are the current best known solutions to the benchmark problems. Hodgson, et al. (1998) presented a procedure (referred to as the Virtual Factory) for efficiently and effectively solving industrial-size job shop scheduling problem with the objective of minimizing maximum lateness, J//Lmax. They presented results for an iterative adaptive simulation-based scheduling procedure based on an idea found in Morton and Pentico (1993). For each iteration of the procedure, jobs are ordered at each machine based on the notion of revised slack. Revised slack is a function of the job's due date, processing time on the current machine and all downstream operations, and estimated queuing times for all downstream operations. Downstream queuing times are estimated from the previous iteration of the procedure. Hodgson, et al. (2000) enhanced the procedure by accelerating hot jobs, i.e. those jobs whose lateness is equal or nearly equal to the Lmax value. Acceleration is accomplished by inserting idle time so that when a hot job arrives at a machine, it begins processing immediately. In this paper, a simulated annealing post processing procedure is added to the Virtual Factory. The goal is to develop a procedure that improves on the Virtual Factory solutions, and does so efficiently. The procedure is evaluated on large-scale problems and compared to a lower bound. In addition, the Dermikol, et al. (1998) benchmark problems are evaluated and the results are compared to the Balas, et al. (1998) solutions. 2. Algorithm Development3 We experimented with a variety of local improvement procedures for the Virtual Factory solution. Based on these experiments, simulated annealing was selected for further evaluation since it yielded the most promising results. Simulated annealing requires a solution representation, a method to generate initial solutions, a method to generate neighboring solutions, and a method to evaluate neighboring solutions. Each of these is described below. 2.1 Solution Representation A solution is represented by a sequence of jobs for each and every machine, referred to here as the machine-job sequence. For example, a possible solution to a 4-machine, 3-job problem is: Machine Job Sequence 1 {1,2,3} 2 {2,1,3} 3 {3,1,2} 4 {1,3,2} 2.2 Initial Solution An initial solution is generated for the J//Lmax problem using the Virtual Factory (Hodgson, et al. 1998, 2000) described above. For the benchmark problems, the Virtual Factory produces solutions close to, and