To solve the NP-complete no-wait flowshop problems, objective increment properties are analyzed and proved for fundamental operations of heuristics. With these properties, whether a new generated schedule is better or...To solve the NP-complete no-wait flowshop problems, objective increment properties are analyzed and proved for fundamental operations of heuristics. With these properties, whether a new generated schedule is better or worse than the original one is only evaluated by objective increments, instead of completely calculating objective values as the traditional algorithms do, so that the computational time can be considerably reduced. An objective increment-based hybrid genetic algorithm （IGA） is proposed by integrating the genetic algorithm （GA） with an improved various neighborhood search （VNS）as a local search. An initial solution generation heuristic（ISG） is constructed to generate one individual of the initial population. An expectation value-based selection mechanism and a crossover operator are introduced to the mating process. The IGA is compared with the traditional GA and two best-so-far algorithms for the considered problem on 110 benchmark instances. An experimental results show that the IGA outperforms the others in effectiveness although with a little more time consumption.展开更多
Aiming at the hybrid flow-shop （HFS） scheduling that is a complex NP-hard combinatorial problem with wide engineering background, an effective algorithm based on differential evolution （DE） is proposed. By using a...Aiming at the hybrid flow-shop （HFS） scheduling that is a complex NP-hard combinatorial problem with wide engineering background, an effective algorithm based on differential evolution （DE） is proposed. By using a special encoding scheme and combining DE based evolutionary search and local search, the exploration and exploitation abilities are enhanced and well balanced for solving the HFS problems. Simulation results based on some typical problems and comparisons with some existing genetic algorithms demonstrate the proposed algorithm is effective, efficient and robust for solving the HFS problems.展开更多
Aiming at the flexible flowshop group scheduling problem,taking sequence dependent setup time and machine skipping into account, a mathematical model for minimizing makespan is established,and a hybrid differential ev...Aiming at the flexible flowshop group scheduling problem,taking sequence dependent setup time and machine skipping into account, a mathematical model for minimizing makespan is established,and a hybrid differential evolution( HDE) algorithm based on greedy constructive procedure( GCP) is proposed,which combines differential evolution( DE) with tabu search( TS). DE is applied to generating the elite individuals of population,while TS is used for finding the optimal value by making perturbation in selected elite individuals. A lower bounding technique is developed to evaluate the quality of proposed algorithm. Experimental results verify the effectiveness and feasibility of proposed algorithm.展开更多
基金The National Natural Science Foundation of China(No.60504029,60672092)the National High Technology Research and Development Program of China(863Program)(No.2008AA04Z103)
文摘To solve the NP-complete no-wait flowshop problems, objective increment properties are analyzed and proved for fundamental operations of heuristics. With these properties, whether a new generated schedule is better or worse than the original one is only evaluated by objective increments, instead of completely calculating objective values as the traditional algorithms do, so that the computational time can be considerably reduced. An objective increment-based hybrid genetic algorithm （IGA） is proposed by integrating the genetic algorithm （GA） with an improved various neighborhood search （VNS）as a local search. An initial solution generation heuristic（ISG） is constructed to generate one individual of the initial population. An expectation value-based selection mechanism and a crossover operator are introduced to the mating process. The IGA is compared with the traditional GA and two best-so-far algorithms for the considered problem on 110 benchmark instances. An experimental results show that the IGA outperforms the others in effectiveness although with a little more time consumption.
基金supported by the National Natural Science Fundation of China (60774082 70871065+2 种基金 60834004)the Program for New Century Excellent Talents in University (NCET-10-0505)the Doctoral Program Foundation of Institutions of Higher Education of China(20100002110014)
文摘Aiming at the hybrid flow-shop （HFS） scheduling that is a complex NP-hard combinatorial problem with wide engineering background, an effective algorithm based on differential evolution （DE） is proposed. By using a special encoding scheme and combining DE based evolutionary search and local search, the exploration and exploitation abilities are enhanced and well balanced for solving the HFS problems. Simulation results based on some typical problems and comparisons with some existing genetic algorithms demonstrate the proposed algorithm is effective, efficient and robust for solving the HFS problems.
基金Shanghai Municipal Natural Science Foundation of China(No.10ZR1431700)
文摘Aiming at the flexible flowshop group scheduling problem,taking sequence dependent setup time and machine skipping into account, a mathematical model for minimizing makespan is established,and a hybrid differential evolution( HDE) algorithm based on greedy constructive procedure( GCP) is proposed,which combines differential evolution( DE) with tabu search( TS). DE is applied to generating the elite individuals of population,while TS is used for finding the optimal value by making perturbation in selected elite individuals. A lower bounding technique is developed to evaluate the quality of proposed algorithm. Experimental results verify the effectiveness and feasibility of proposed algorithm.
