یک الگوریتم ژنتیک ترکیبی برای مشکلات زمان بندی عدم انتظار تولید کارگاهی

A no-wait job shop (NWJS) describes a situation where every job has its own processing sequence with the constraint that no waiting time is allowed between operations within any job. A NWJS problem with the objective of minimizing total completion time is a NP-hard problem and this paper proposes a hybrid genetic algorithm (HGA) to solve this complex problem. A genetic operation is defined by cutting out a section of genes from a chromosome and treated as a subproblem. This subproblem is then transformed into an asymmetric traveling salesman problem (ATSP) and solved with a heuristic algorithm. Subsequently, this section with new sequence is put back to replace the original section of chromosome. The incorporation of this problem-specific genetic operator is responsible for the hybrid adjective. By doing so, the course of the search of the proposed genetic algorithm is set to more profitable regions in the solution space. The experimental results show that this hybrid genetic algorithm can accelerate the convergence and improve solution quality as well.

A no-wait job shop (NWJS) is a job shop with the constraint that no waiting time is allowed between operations within any job. This phenomena often occurs in steel productions, plastic modeling and chemical industries, where it is physically prohibited to wait between processing. Another application can be found in modern manufacturing environment. Traditional scheduling models take little considerations about minimizing inventory while meeting required performance; no-wait scheduling problem can model this environment and the methodologies of it becomes a recent interest. An NWJS problem with makespan (Cmax), i.e., the maximum completion times of all jobs, as objective function is known to be NP-hard in the strong sense ( Lenstra, Rinnooy Kan, & Brucker, 1977). Sahni and Cho (1979) showed that even when restricted to two machines, the problem is still NP-hard. Hall and Sriskandarajah (1996) reviewed relevant literatures on no-wait and blocking shop problems and found that NWJS problems have received surprisingly little attention from either a theoretical or computational perspective. Most researches on NWJS problems tackled the mathematical complexity issues ( Goyal and Sriskandarajah, 1988, Hall and Sriskandarajah, 1996, Kamoun and Sriskandarajah, 1993, Sahni and Cho, 1979 and Sriskandarajah and Ladet, 1986). As to the solution methodologies, Sriskandarajah and Ladet (1986), as well as Kubiak (1989) proposed pseudo-polynomial time algorithms for two machines no-wait job shop problems with unit processing time. Reddi and Ramamoorthy (1973) derived a lower bound for a special case of NWJS by requiring no subsuming jobs in the job set. Goyal (1975) found that solving NWJS problem is the same as solving a set of asymmetrical traveling salesman problems (ATSP), and the one with the smallest tour length is thus the optimal solution for the problem. As for meta-heuristics, Raaymakers and Hoogeven (2000) presented a simulated annealing (SA) approach to NWJS problems with parallel machines and their results showed that SA improved on the best of the initial solutions by 10% on the average. Macchiaroli, Molè, Riemma, and Trifiletti (1996) presented a two-phase tabu search (TS) approach and found that it generated better solutions than those of the dispatching rules by an average of 9%. Brizuela, Zhao, and Sannomiya (2001) proposed a genetic algorithm (GA) using simple encoding and adequate decoding techniques to solve classical job shop benchmark problems with no-wait constraints. Recently, Mascis and Pacciarelli (2002) extended the idea of disjunctive graph formulation to the so-called alternative graph formulation. By this formulation, solving a NWJS problem with makespan as objective is the same as finding a selection of the alternative arc set that minimizes the longest path of the graph with no cycles occurred. Computational results for the proposed greedy heuristics were conducted on classical job shop benchmark problems by imposing no-wait constraint. This study proposes a hybrid genetic algorithm (HGA), which encapsulates a problem-specific genetic operator into the GA procedures, to solve the NWJS problems. This problem-specific genetic operator randomly selects a consecutive section of genes from a chromosome, and treats it as a NWJS subproblem. This subproblem is then transformed to an ATSP and solved. After that, a local search based on ATSP solution is implemented. The best sequence obtained by the local search is placed back into the chromosome. By doing this, new building blocks consisting of suboptimal schedules for subproblem is introduced. The performance of the HGA is evaluated by means of 58 benchmark problems obtained from a public library (Beasly, 1990). The computational experiments show that HGA converges more quickly and to a better solution than pure genetic algorithm does. This suggests that the incorporation of the problem-oriented knowledge can direct the search of GA to more profitable regions in the solution space.

This paper proposes a hybrid genetic algorithm to solve the no-wait job shop problems. The main purpose of the hybrid operator is to improve the efficiency of the traditional genetic approach. In the lack of problem-specific heuristic for no-wait job shop (NWJS) problems, this study utilizes an asymmetric traveling salesman problem formulation for a special case of NWJS problems, which requires no passing among jobs, to serve as a fast heuristic. After that, a local search is carried out to explore even better solution region. Benchmark instances for classical job shop problems are tested by imposing no-wait conditions. The computational results show that HGA is as good as GA in small size instances while it is superior to GA for large size instances. It is also found that the HGA reaches best performance most of the time if the cut length is set close to 1/3 of the chromosome length. Larger cut length results in early convergence to local optimum while smaller cut length degrades the performance of HGA. Some possible directions for future research are suggested as follows. First, it is interesting to investigate whether searching non-delay schedules only is more promising than searching active schedules. However, there are no systematic ways to generate active schedules for NWJS problems up to now. Another suggestion is to determine the best parameter combinations. Because the parameter setting is rather problem dependent, a large scale of experiments is needed to determine the effects of each parameter for each problem type. One last suggestion is to investigate whether there are other heuristics to be capsulated into the procedures of GA for NWJS problems. These heuristics can be meta-heuristics, such as tabu search, simulated annealing, or other problem-specific heuristics.