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.展开更多
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%.展开更多
In the manufacturing industry,reasonable scheduling can greatly improve production efficiency,while excessive resource consumption highlights the growing significance of energy conservation in production.This paper st...In the manufacturing industry,reasonable scheduling can greatly improve production efficiency,while excessive resource consumption highlights the growing significance of energy conservation in production.This paper studies the problem of energy-efficient distributed heterogeneous permutation flowshop problem with variable processing speed(DHPFSP-VPS),considering both the minimum makespan and total energy consumption(TEC)as objectives.A discrete multi-objective squirrel search algorithm(DMSSA)is proposed to solve the DHPFSPVPS.DMSSA makes four improvements based on the squirrel search algorithm.Firstly,in terms of the population initialization strategy,four hybrid initialization methods targeting different objectives are proposed to enhance the quality of initial solutions.Secondly,enhancements are made to the population hierarchy system and position updating methods of the squirrel search algorithm,making it more suitable for discrete scheduling problems.Additionally,regarding the search strategy,six local searches are designed based on problem characteristics to enhance search capability.Moreover,a dynamic predator strategy based on Q-learning is devised to effectively balance DMSSA’s capability for global exploration and local exploitation.Finally,two speed control energy-efficient strategies are designed to reduce TEC.Extensive comparative experiments are conducted in this paper to validate the effectiveness of the proposed strategies.The results of comparing DMSSA with other algorithms demonstrate its superior performance and its potential for efficient solving of the DHPFSP-VPS problem.展开更多
基金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.
文摘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%.
基金supported by the Key Research and Development Project of Hubei Province(Nos.2020BAB114 and 2023BAB094).
文摘In the manufacturing industry,reasonable scheduling can greatly improve production efficiency,while excessive resource consumption highlights the growing significance of energy conservation in production.This paper studies the problem of energy-efficient distributed heterogeneous permutation flowshop problem with variable processing speed(DHPFSP-VPS),considering both the minimum makespan and total energy consumption(TEC)as objectives.A discrete multi-objective squirrel search algorithm(DMSSA)is proposed to solve the DHPFSPVPS.DMSSA makes four improvements based on the squirrel search algorithm.Firstly,in terms of the population initialization strategy,four hybrid initialization methods targeting different objectives are proposed to enhance the quality of initial solutions.Secondly,enhancements are made to the population hierarchy system and position updating methods of the squirrel search algorithm,making it more suitable for discrete scheduling problems.Additionally,regarding the search strategy,six local searches are designed based on problem characteristics to enhance search capability.Moreover,a dynamic predator strategy based on Q-learning is devised to effectively balance DMSSA’s capability for global exploration and local exploitation.Finally,two speed control energy-efficient strategies are designed to reduce TEC.Extensive comparative experiments are conducted in this paper to validate the effectiveness of the proposed strategies.The results of comparing DMSSA with other algorithms demonstrate its superior performance and its potential for efficient solving of the DHPFSP-VPS problem.
