Multi-objective Models And Algorithms For Job Shop Scheduling Problem

Job shop scheduling problem is a typical combinatorial optimization problem, is animportant branch of production scheduling problems. Currently, researches on job shopscheduling problems have gained wide attention and have achieved great development.At the same time, there are also many problems. A systematic study on job shopscheduling problem was made in this paper, and the main research results were asfollows:1. To solve the job shop scheduling problem more effectively, a hybrid geneticalgorithm was proposed. A mixed selection operator based on the fitness value and theconcentration was designed to increase the diversity of the population and avoid thealgorithm fall into a local optimal solution; According to the graph theory model of thejob shop scheduling problem, a new crossover operator based on the machine andmutation operator based on the critical path were specifically designed in order toimprove the global search ability and convergence speed, and we also proposed a neweffective method for solving the critical path; A local search operator was designed toimprove local search ability of the algorithm; Based on these genetic operators, animproved hybrid genetic algorithm was proposed and its convergence was proved. Thecomputer simulations were made on a set of benchmark problems and the resultsdemonstrated the effectiveness of the proposed algorithm.2. For the job shop scheduling problem, we considered both the completionsituation of the jobs and the inventory capacity, proposed a multi-objective job shopscheduling model, in which both the make-span (the total completion time) and theinventory capacity were as objectives and were optimized simultaneously. To solve theproposed model, a new crossover operator based on the critical path was specificallydesigned. A local search operator was designed in order to improve the local searchability of the algorithm. Based on all these, a hybrid genetic algorithm was proposed.The computer simulations were made on a set of benchmark problems and the resultsdemonstrated the effectiveness of the proposed algorithm.3. The core theory of the basic genetic algorithm is the schema theorem and theconvergence theory. The traditional schema theorem used binary representation andproved, and the operation based encoding method was used in this paper, it’s a limited character set encoding. Therefore, we have given some typical genetic operators firstand based on these, we proved the schema theorem using limited character set encoding.The result showed that the numbers of schema which order of low, defined length ofshort and the fitness value greater than the average fitness value grown exponentially.4. For the job shop scheduling problem, we considered both the completionsituation of the jobs and the usage situation of the machines, proposed a multi-objectivejob shop scheduling problem model, in which both the make-span (the total completiontime) and the mean continuous running time were as objectives and were optimizedsimultaneously. The proposed model was solved by an improved hybrid geneticalgorithm. The computer simulations were made on a set of benchmark problems andthe results demonstrated the effectiveness of the proposed algorithm.