No-wait flowshop scheduling problems with the objective to minimize the total flow time is an important se-quencing problem in the field of developing production plans and has a wide engineering background. Genetic al...No-wait flowshop scheduling problems with the objective to minimize the total flow time is an important se-quencing problem in the field of developing production plans and has a wide engineering background. Genetic algo-rithm (GA) has the capability of global convergence and has been proven effective to solve NP-hard combinatorial op-timization problems,while simple heuristics have the advantage of fast local convergence and can be easily imple-mented. In order to avoid the defect of slow convergence or premature,a heuristic genetic algorithm is proposed by in-corporating the simple heuristics and local search into the traditional genetic algorithm. In this hybridized algorithm,the structural information of no-wait flowshops and high-effective heuristics are incorporated to design a new method for generating initial generation and a new crossover operator. The computational results show the developed heuristic ge-netic algorithm is efficient and the quality of its solution has advantage over the best known algorithm. It is suitable for solving the large scale practical problems and lays a foundation for the application of meta-heuristic algorithms in in-dustrial production.展开更多
The permutation flowshop scheduling problem （PFSP） is one of the most well-known and well-studied production scheduling problems with strong industrial background. This paper presents a new hybrid optimization algor...The permutation flowshop scheduling problem （PFSP） is one of the most well-known and well-studied production scheduling problems with strong industrial background. This paper presents a new hybrid optimization algorithm which combines the strong global search ability of artificial immune system （AIS） with a strong local search ability of extremal optimization （EO） algorithm. The proposed algorithm is applied to a set of benchmark problems with a makespan criterion. Performance of the algorithm is evaluated. Comparison results indicate that this new method is an effective and competitive approach to the PFSP.展开更多
The flowshop scheduling problem is NP complete. To solve it by genetic algorithm, an efficient crossover operator is designed. Compared with another crossover operator, this one often finds a better solution within th...The flowshop scheduling problem is NP complete. To solve it by genetic algorithm, an efficient crossover operator is designed. Compared with another crossover operator, this one often finds a better solution within the same time.展开更多
The m-machine no-wait flowshop scheduling problem is addressed where setup times are treated as separate from processing times. The objective is to minimize total tardiness. Different dispatching rules have been inves...The m-machine no-wait flowshop scheduling problem is addressed where setup times are treated as separate from processing times. The objective is to minimize total tardiness. Different dispatching rules have been investigated and three were found to be superior. Two heuristics, a simulated annealing (SA) and a genetic algorithm (GA), have been proposed by using the best performing dispatching rule as the initial solution for SA, and the three superior dispatching rules as part of the initial population for GA. Moreover, improved versions of SA and GA are proposed using an insertion algorithm. Extensive computational experiments reveal that the improved versions of SA and GA perform about 95% better than SA and GA. The improved version of GA outperforms the improved version of SA by about 3.5%.展开更多
基金Project 60304016 supported by the National Natural Science Foundation of China
文摘No-wait flowshop scheduling problems with the objective to minimize the total flow time is an important se-quencing problem in the field of developing production plans and has a wide engineering background. Genetic algo-rithm (GA) has the capability of global convergence and has been proven effective to solve NP-hard combinatorial op-timization problems,while simple heuristics have the advantage of fast local convergence and can be easily imple-mented. In order to avoid the defect of slow convergence or premature,a heuristic genetic algorithm is proposed by in-corporating the simple heuristics and local search into the traditional genetic algorithm. In this hybridized algorithm,the structural information of no-wait flowshops and high-effective heuristics are incorporated to design a new method for generating initial generation and a new crossover operator. The computational results show the developed heuristic ge-netic algorithm is efficient and the quality of its solution has advantage over the best known algorithm. It is suitable for solving the large scale practical problems and lays a foundation for the application of meta-heuristic algorithms in in-dustrial production.
基金Project supported by the National Natural Science Foundation of China （Grant No.60574063）
文摘The permutation flowshop scheduling problem （PFSP） is one of the most well-known and well-studied production scheduling problems with strong industrial background. This paper presents a new hybrid optimization algorithm which combines the strong global search ability of artificial immune system （AIS） with a strong local search ability of extremal optimization （EO） algorithm. The proposed algorithm is applied to a set of benchmark problems with a makespan criterion. Performance of the algorithm is evaluated. Comparison results indicate that this new method is an effective and competitive approach to the PFSP.
文摘The flowshop scheduling problem is NP complete. To solve it by genetic algorithm, an efficient crossover operator is designed. Compared with another crossover operator, this one often finds a better solution within the same time.
文摘The m-machine no-wait flowshop scheduling problem is addressed where setup times are treated as separate from processing times. The objective is to minimize total tardiness. Different dispatching rules have been investigated and three were found to be superior. Two heuristics, a simulated annealing (SA) and a genetic algorithm (GA), have been proposed by using the best performing dispatching rule as the initial solution for SA, and the three superior dispatching rules as part of the initial population for GA. Moreover, improved versions of SA and GA are proposed using an insertion algorithm. Extensive computational experiments reveal that the improved versions of SA and GA perform about 95% better than SA and GA. The improved version of GA outperforms the improved version of SA by about 3.5%.
