Optimally Solving Job Shop Scheduling Problem (JSSP) through a Heuristic Based Approach

Abstract

Job shops are the mother of all manufacturing system; identifying features of a job shop are general purpose machines, high variety, low volume and high human involvement in production activities. As rapid changes in models and addition of new features in consumer products is becoming a norm, job shops are coming back in action again. To fully engage and utilize the capabilities of a job shop an optimal schedule is a necessary requirement. An optimal schedule to a job shop scheduling problem enhances machine utilization, improve productivity of manufacturing system, reduce lead times and lower costs. Due to complexity and wide-ranging application of job shop scheduling problems, a large numbers of approaches and algorithms have been developed and proposed by numerous researchers for many decades. To solve job shop scheduling problem two hybrid methods has been proposed. These methods are based on simulated annealing (SA) and fast simulated annealing (FSA). These methods are hybridized with quenching, another material treatment process. The proposed methods utilize SA and FSA for global search and quenching for local search. Search is started with a relatively higher temperature and as the algorithm performs its iterations, this temperature is gradually reduced to a low value. The algorithm keeps record of the best solution found so far, if this best solution does not improve for a certain number of iterations, then a quenching cycle is initiated. This novel quenching cycle reduces temperature drastically to nearly a zero value and increase iterations by many folds. The unique feature of these algorithms is their ability to avoid and escape local optimal solutions in both local and global search phases. The ability is imparted by the use of Boltzmann probability distribution function (PDF) for SA and Cauchy PDF for FSA. When quenching cycles run its course original values of temperature and iterations are restored. Due to relaxation in temperature search moves to another part of solution space and then another quenching cycle is invoked to perform local search. Effectiveness of proposed algorithm is established by solving 88 benchmark problems. The proposed hybrid version of SA was able to solve 22 benchmark problems to their respective optimal solutions, and the hybrid version of FSA was able to solve 45 problems to optimality. The proposed approaches were compared with 17 other published works, and it out performed 15 approaches. On the basis of these experimental results, it can be safely concluded that proposed methods are efficient in finding solution of job shop scheduling problems.