Scheduling for the job shop is very important in both fields of production management and combinatorial optimization. However, it is quite difficult to achieve an optimal solution to this problem with traditional optimization methods owing to the high computational complexity (NP-hard). Genetic algorithms (GA) have been proved to be effective for a variety of situations, including scheduling and sequencing. Unfortunately, its efficiency is not satisfactory. In order to make GA more efficient and practical, the knowledge relevant to the problem to be solved is helpful. In this paper, a kind of hybrid heuristic GA is proposed for problem n/m/G/Cmax, where the scheduling rules, such as shortest processing time (SPT) and MWKR, are integrated into the process of genetic evolution. In addition, the neighborhood search technique (NST) is adopted as an auxiliary procedure to improve the solution performance. The new algorithm is proved to be effective and efficient by comparing it with some popular methods, i.e. the heuristic of neighborhood search, simulated annealing (SA), and traditional GA.
Scheduling for job shops is an important topic in production management. It is concerned with determining the release order and times of a set of jobs on the relevant machines subject to the processing constraints, in an effort to improve the production efficiency and reduce the processing duration so as to gain as high profits as possible. The problem studied in this paper is quite general. A set of n jobs has to be processed on m machines, where the processing of each job consists of m operations performed on these machines in a specified sequence. The operation of job i has to be performed on machine j with deterministic processing time tij. A machine can process only one job at a time, and an operation cannot be preempted. The goal for optimization is to minimize the makespan (Cmax). Following the notations of Siman (1982), we can denote the problem as n/m/G/Cmax.
It is well known that this problem is NP-hard (Garey, Johnson & Sethi, 1976), and even a rather simple instance with small size, such as 10 jobs and 10 machines, is hard to solve with an exact approach. In fact, the optimal solution is not necessarily needed in many practical situations, because the computation time and cost for an optimal solution are usually so large that one can hardly afford them, and a good suboptimal solution can be well accepted. Hence, more and more efficient methods for seeking suboptimal solutions, such as various kinds of heuristic, have been developed recently (Rodammer & White, 1988). From the existing investigations, genetic algorithms (GAs) have shown great advantages, and have been proved quite effective (Croce et al., 1995 and Syswerda, 1991). The suboptimal solutions reached using GAs are usually superior to those obtained using traditional searching approaches due to their inherent features of global search and convergence. So far, the methods based on GA have become a popular and effective way for solving large-scale combinatorial optimization problems, including job shop scheduling.
GAs are problem-independent, which means little specific knowledge relevant to a given problem is required, and what we have to know is just the fitness evaluation for each solution. This feature makes GA more robust than many other searching schemes, such as greedy techniques and algorithms based on gradient. However, some researchers found that there was a tradeoff between the efficiency and the robustness, and sometimes the efficiency of an algorithm is more important. In order to make the GA more efficient, the knowledge relevant to the given problem is helpful. Hence it would be of great advantage to consider a GA hybrid when specific information about the problem is available (Davis, 1991 and Goldberg, 1989). In this paper, the scheduling rules of shortest processing time (SPT) (the job with the shortest processing time has the highest priority for processing) and MWKR (the job with the most work remaining would be scheduled first) are applied to the process of generating new individuals, and the neighborhood search technique (NST) is employed as an auxiliary searching procedure following genetic search in an effort to avoid or reduce the harmful side effects of reduction of the solution space incurred by introducing the scheduling rules. The new algorithm is proved both effective and efficient by comparing it with some methods that are commonly used at present, such as NST (Siman, 1982), simulated annealing (SA) (Van Laarhoven & Aarts, 1987), and general GA (Davis, 1991).
We proposed a kind of hybrid heuristic genetic algorithm (GA) in this paper. The main purpose of the research is to improve the efficiency of the traditional GA and explore some more effective and efficient approaches to solving job shop scheduling problems. The peculiarity of our algorithm lies in the introduction of heuristic scheduling rules into the process of generating new individuals to guide the genetic evolution, and the employment of NST to improve the performance of solutions. We compared the algorithm with some popular approaches, such as SA, NST, and GA; the computational results show that our algorithm is quite superior to the others in effectiveness and efficiency.
The GA has been proved effective to solve job shop problems by many researchers, but how to improve its efficiency still remains an important problem. The study in this paper confirms the idea that one promising way to speed up the convergence is to integrate the GA with the specific techniques for job shop problems, such as the heuristic rules and local search techniques. There is no doubt that these kinds of procedure are well worth further exploration.
