Research On The Shop Scheduling Problem With Naturally-Inspired Heuristic Algorithms

Scheduling is a key factor for manufacturing productivity. Proper and effective scheduling can help cut lead times, improve on-time delivery, reduce inventory, so as to increase the prestige of enterprises. Recently, with the upgrading of market competition as a result of the economic globalization and the variety and individuality of consumers'demands, scheduling is playing an increasingly important role in the manufacturing industry.Practically, different domains and applications require different variations of the scheduling problem. Meanwhile, the Job-Shop scheduling problem (JSP) is the most fundamental and well-known. The fact is that the JSP is notoriously difficult, as well as widely accepted as one of the most difficult NP-hard problems. Despite over 40 years of efforts, resulting in hundreds of published journal articles and tens of dissertations, even those state-of-the-art algorithms often fail to consistently locate optimal solutions to relatively small problem instances. During the last decade, the meta-heuristics algorithms developed by mimicking the process of natural laws, such as genetic algorithms (GA), tabu search (TS), simulated annealing (SA), particle swarm optimization (PSO), and ant colony optimization (ACO), have shown the effectiveness for the solution of difficult combinatorial optimization problems and captured the interest of a significant number of researchers.Among these approaches, genetic algorithm and local search are two primary algorithms applied to solving the JSP. Genetic algorithm, which exhibits parallelism, contains certain redundancy and historical information of past solutions, and requires little problem-specific knowledge other than fitness, has been widely applied in the production scheduling field. In this paper we improve the traditional GA and propose three novel features for this algorithm to solve the JSP. Firstly, a new full-active schedule (FAS) procedure based on the operation-based representation is presented to construct schedule, which further reduces the search space. Secondly, a new crossover operator, called Precedence Operation Crossover (POX), is proposed for the operation-based representation, which can preserve the meaningful characteristics of the previous generation. Thirdly, in order to reduce the disruptive effects of genetic operators, the approach of an improved generation alteration model is introduced. The proposed GA is tested on some standard instances and compared with the other GA procedures. The experimental results validate the effectiveness of the proposed algorithm. Next, the application of local search, especially tabu search, is studied.Tabu search is among the most effective approaches for solving the job shop scheduling problem. However, the efficiency of TS depends mostly on the modeling, and neighborhood structures and move evaluation strategies play the central role in the effectiveness and efficiency of TS for the JSP. In this paper, a new enhanced neighborhood structure is proposed. By combining it with the appropriate move evaluation strategy and parameters, we proposed a dynamic intensified TS approach. This approach is tested on a set of standard benchmark instances and found a large number of better upper bounds among the unsolved instances. The computational results show that for the rectangular problem our TS approach dominates all others in terms of both solution quality and performance.Genetic algorithm, simulated annealing and tabu search (local search techniques) are all naturally motivated and have complementary strengths and weaknesses. Recently, most studies indicate that a single technique cannot solve this stubborn problem, and hybrid methods are able to provide high-quality solutions within reasonable computing times. However, hybridizing algorithms are sort of an art so far. Since the solution space of the JSP owns"big valley"(BV) and the best elite solutions disperse over BV area. By application of the natural law to explore the whole big valley, two effective hybrid optimization strategies are proposed, which combine the advantage properties of each algorithm. The hybrid algorithms proposed were tested on the standard benchmark sets and compared with other approaches, we improved 84 upper bounds among the 106 unsolved instances for the general ABZ, YN, SWV, TA and DUM benchmark sets. Meanwhile, for the well-known Taillard's benchmark set, I found 20 new upper bounds among the 33 unsolved instances, some of which provide the optimal solutions. In addition, the results of comparison between our hybrid algorithms and the best approximation algorithms show that for the most difficult Job-Shop scheduling problem our work has reached the advanced international level.Actually the scheduling problems in real world are complex, dynamic and require different sets of evaluation criteria. Based on the fruits of researching the traditional JSP, we studied the widely existed scheduling problems in practice, such as the flexible job-shop scheduling problem (FJSP), dynamic scheduling and their different sets of evaluation criteria, and proposed the corresponding optimal strategies according to their characteristics. For example, a multistage-based generation alteration model of genetic algorithm is proposed to solve the FJSP; an improved genetic-based rolling horizon scheduling strategy is presented, which extends the previous research on static scheduling to dynamic scheduling. In addition, the dynamic scheduling prototype system is developed, which can be adopted in enterprises to make contributions to the society.Scheduling is the key component of Manufacturing Execution System (MES). Proper scheduling is prerequisite for MES applied to manufacturing industry. Based on the study of theories and applications above, AMES (Agile Manufacturing Execution System, AMES V1.0) software has been designed and developed for the cooperative factory, and integrated with other manufacturing resources.