Research On The Job Shop Scheduling Problem With Memetic Algorithms

With increasingly keen market competition, each enterprise is searching for a goodmanagement system for production and operation to improve efficiency in production,operation and management as well, thereby enhance its own core competitive advantage.Scheduling is a key factor for manufacturing productivity. Proper and effectivescheduling can help minimize makespan, reduce inventory and improve on-timedelivery. Practically, different domains and applications require different variations ofthe scheduling problem. Meanwhile, the job shop scheduling problem (JSSP) is one ofthe most well-known. The fact is that the JSSP is notoriously difficult, as well as widelyaccepted as one of the most difficult NP-hard problems. Despite over several decades ofefforts, even those state-of-the-art algorithms often fail to get satisfactory solvingqualitative and computational efficiency.In the research on job shop scheduling problem, a large number of deterministicalgorithms and heuristic algorithms are proposed. During the last decade, themeta-heuristics algorithms developed by mimicking the process of natural laws, such asgenetic algorithms (GA), simulated annealing (SA), particle swarm optimization (PSO),and ant colony optimization (ACO), have shown the effectiveness for the solution ofdifficult combinatorial optimization problems and captured the interest of a significantnumber of researchers. In accordance with the No Free Lunch Theorem, there is nooptimal diversity metric, but rather its design should take into account the problem andthe evolutionary swarm intelligence structure under consideration. Memetic Algorithms(MAs) are population-based metaheuristics composed of an evolutionary frameworkand a set of local search algorithms which are activated within the generation cycle ofthe external framework.Based on analysis of all aspects of memetic algorithm for job shop schedulingproblem, this thesis presented memetic algorithms to minimize makespan, minimizetotal weighted tardiness and optimize multiple objectives simultaneously. The mainworks of the thesis is as following:①Using memetic algorithm for solving optimization problem the first thing is todesign the elements of the algorithm. This thesis analyzed the operation basedrepresentation and the binary representation of scheduling problem. The Euclideandistance of the solution space of the scheduling problem is defined. The decoding procedures, evolution operations and generation alternation models are analyzed by thedefined Euclidean distance.②This thesis presents a new generation alternation model for the job shopscheduling problem. Every pair of randomly selected parents must pass either crossoveror mutation, which are deployed in parallel. When the mating process is carried out,crossover operator or the mutation operator is applied to the two parents multiple timesand the best individual in those offspring is selected to the next generation. Comparedwith the simple genetic algorithm, the proposed algorithm can makes the offspringinherited the characteristics of the parent better and have a wider search range.③For the job shop scheduling problem for minimizing makespan, the thesisanalyzed of the common neighborhood structure based on critical path and operationblock. A new memetic algorithm is proposed by combining the new evolutionaryprocedure and the steepest descent method. Numerical experiments on the classic testproblems show that the proposed method is better than other mainstream algorithms.④For the job shop scheduling problem for minimizing total weighted tardiness,the objective is a due date related problem and is more difficult. This thesis designedthree new neighborhoods to solve this problem. The computation results validate theeffectiveness of the proposed algorithm.⑤Proposed a elitist strategy based multi-objective memetic algorithm for themulti-objective job shop scheduling problem. The thesis studied the design philosophyof the mainstream algorithm in the field of multiobjective optimization algorithm. Amultiobjective memetic algorithm is designed with the elitist strategy embedded in theevolutionary process and the local search. Numerical experiments on two and threeoptimization objective job shop scheduling problem show that the proposed algorithm isbetter than NSGAII and the result is better than other papers.⑥To relate theory with practice, the research results were used to a productionmanagement system. The system schedule production tasks and generate operation planto provide a basis for organizing production activities scientifically.