In a local search algorithm,one of its most important features is the definition of its neighborhood which is crucial to the algorithm's performance.In this paper,we present an analysis of neighborhood combination...In a local search algorithm,one of its most important features is the definition of its neighborhood which is crucial to the algorithm's performance.In this paper,we present an analysis of neighborhood combination search for solv-ing the single-machine scheduling problem with sequence-dependent setup time with the objective of minimizing total weighted tardiness(SMSWT).First,We propose a new neighborhood structure named Block Swap(B1)which can be con-sidered as an extension of the previously widely used Block Move(B2)neighborhood,and a fast incremental evaluation technique to enhance its evaluation efficiency.Second,based on the Block Swap and Block Move neighborhoods,we present two kinds of neighborhood structures:neighborhood union(denoted by B1UB2)and token-ring search(denoted by B1→B2),both of which are combinations of B1 and B2.Third,we incorporate the neighborhood union and token-ring search into two representative metaheuristic algorithms:the Iterated Local Search Algorithm(ILSnew)and the Hybrid Evolutionary Algorithm(HEA_(new))to investigate the performance of the neighborhood union and token-ring search.Exten-sive experiments show the competitiveness of the token-ring search combination mechanism of the two neighborhoods.Tested on the 120 public benchmark instances,our HEA_(new)has a highly competitive performance in solution quality and computational time compared with both the exact algorithms and recent metaheuristics.We have also tested the HEA,new algorithm with the selected neighborhood combination search to deal with the 64 public benchmark instances of the single-machine scheduling problem with sequence-dependent setup time.HEAnew is able to match the optimal or the best known results for all the 64 instances.In particular,the computational time for reaching the best well-known results for five chal-lenging instances is reduced by at least 61.25%.展开更多
As the global economy develops and people's awareness of environmental protection increases,the efficient scheduling of production lines in workshops has received more and more attention.However,there is very litt...As the global economy develops and people's awareness of environmental protection increases,the efficient scheduling of production lines in workshops has received more and more attention.However,there is very little research focusing on distributed scheduling for heterogeneous factories.This study addresses a multi-objective distributed heterogeneous permutation flow shop scheduling problem with sequence-dependent setup times(DHPFSP-SDST).The objective is to optimize the trade-off between the maximum completion time(Makespan)and total energy consumption.First,to describe the concerned problems,we establish a mathematical model.Second,we use the artificial bee colony(ABC)algorithm to optimize the two objectives,incorporating five local search strategies tailored to the problem characteristics to enhance the algorithm's performance.Third,to improve the convergence speed of the algorithm,a Q-learning based strategy is designed to select the appropriated local search operator during iterations.Finally,based on experiments conducted on 72 instances,statistical analysis and discussions show that the Q-learning based ABC algorithm can effectively solve the problems better than its peers.展开更多
A new scheduling model for the bulk ore blending process in iron-making industry is presented , by converting the process into an assembly flow shop scheduling problem with sequence-depended setup time and limited int...A new scheduling model for the bulk ore blending process in iron-making industry is presented , by converting the process into an assembly flow shop scheduling problem with sequence-depended setup time and limited intermediate buffer , and it facilitates the scheduling optimization for this process.To find out the optimal solution of the scheduling problem , an improved genetic algorithm hybridized with problem knowledge-based heuristics is also proposed , which provides high-quality initial solutions and fast searching speed.The efficiency of the algorithm is verified by the computational experiments.展开更多
The hybrid flow shop group scheduling problem(HFGSP)with the delivery time windows has been widely studied owing to its better flexibility and suitability for the current just-in-time production mode.However,there are...The hybrid flow shop group scheduling problem(HFGSP)with the delivery time windows has been widely studied owing to its better flexibility and suitability for the current just-in-time production mode.However,there are several unresolved challenges in problem modeling and algorithmic design tailored for HFGSP.In our study,we place emphasis on the constraint of timeliness.Therefore,this paper first constructs a mixed integer linear programming model of HFGSP with sequence-dependent setup time and delivery time windows to minimize the total weighted earliness and tardiness(TWET).Then a penalty groups-assisted iterated greedy integrating idle time insertion(PG IG ITI)is proposed to solve the above problem.In the PG IG ITI,a double decoding strategy is proposed based on the earliest available machine rule and the idle time insertion rule to calculate the TWET value.Subsequently,to reduce the amount of computation,a skip-based destruction and reconstruction strategy is designed,and a penalty groups-assisted local search is proposed to further improve the quality of the solution by disturbing the penalized groups,i.e.,early and tardy groups.Finally,through comprehensive statistical experiments on 270 test instances,the results prove that the proposed algorithm is effective compared to four state-of-the-art algorithms.展开更多
基金supported by the National Natural Science Foundation of China under Grant Nos.62202192,71801218,and 72101094.
文摘In a local search algorithm,one of its most important features is the definition of its neighborhood which is crucial to the algorithm's performance.In this paper,we present an analysis of neighborhood combination search for solv-ing the single-machine scheduling problem with sequence-dependent setup time with the objective of minimizing total weighted tardiness(SMSWT).First,We propose a new neighborhood structure named Block Swap(B1)which can be con-sidered as an extension of the previously widely used Block Move(B2)neighborhood,and a fast incremental evaluation technique to enhance its evaluation efficiency.Second,based on the Block Swap and Block Move neighborhoods,we present two kinds of neighborhood structures:neighborhood union(denoted by B1UB2)and token-ring search(denoted by B1→B2),both of which are combinations of B1 and B2.Third,we incorporate the neighborhood union and token-ring search into two representative metaheuristic algorithms:the Iterated Local Search Algorithm(ILSnew)and the Hybrid Evolutionary Algorithm(HEA_(new))to investigate the performance of the neighborhood union and token-ring search.Exten-sive experiments show the competitiveness of the token-ring search combination mechanism of the two neighborhoods.Tested on the 120 public benchmark instances,our HEA_(new)has a highly competitive performance in solution quality and computational time compared with both the exact algorithms and recent metaheuristics.We have also tested the HEA,new algorithm with the selected neighborhood combination search to deal with the 64 public benchmark instances of the single-machine scheduling problem with sequence-dependent setup time.HEAnew is able to match the optimal or the best known results for all the 64 instances.In particular,the computational time for reaching the best well-known results for five chal-lenging instances is reduced by at least 61.25%.
基金supported by the Science and Technology Development Fund(FDCT),Macao SAR(No.0019/2021/A)National Natural Science Foundation of China(No.62173356)+2 种基金Zhuhai Industry-University-Research Project with Hongkong and Macao(No.ZH22017002210014PWC)Guangdong Basic and Applied Basic Research Foundation(No.2023A1515011531)Key Technologies for Scheduling and Optimization of Complex Distributed Manufacturing Systems(No.22JR10KA007).
文摘As the global economy develops and people's awareness of environmental protection increases,the efficient scheduling of production lines in workshops has received more and more attention.However,there is very little research focusing on distributed scheduling for heterogeneous factories.This study addresses a multi-objective distributed heterogeneous permutation flow shop scheduling problem with sequence-dependent setup times(DHPFSP-SDST).The objective is to optimize the trade-off between the maximum completion time(Makespan)and total energy consumption.First,to describe the concerned problems,we establish a mathematical model.Second,we use the artificial bee colony(ABC)algorithm to optimize the two objectives,incorporating five local search strategies tailored to the problem characteristics to enhance the algorithm's performance.Third,to improve the convergence speed of the algorithm,a Q-learning based strategy is designed to select the appropriated local search operator during iterations.Finally,based on experiments conducted on 72 instances,statistical analysis and discussions show that the Q-learning based ABC algorithm can effectively solve the problems better than its peers.
基金Item Sponsored by National Key Technology Research and Development Program in 11th Five-Year Plan of China ( 2006AA04Z184 )National Natural Science Foundation of China ( 60974023 )
文摘A new scheduling model for the bulk ore blending process in iron-making industry is presented , by converting the process into an assembly flow shop scheduling problem with sequence-depended setup time and limited intermediate buffer , and it facilitates the scheduling optimization for this process.To find out the optimal solution of the scheduling problem , an improved genetic algorithm hybridized with problem knowledge-based heuristics is also proposed , which provides high-quality initial solutions and fast searching speed.The efficiency of the algorithm is verified by the computational experiments.
基金This work was supported by the Natural Science Foundation of Shandong province(No.ZR2023MF022)National Natural Science Foundation of China(Nos.61973203,61803192,62106073,and 61966012)Guangyue Young Scholar Innovation Team of Liaocheng University(No.LCUGYTD2022-03).
文摘The hybrid flow shop group scheduling problem(HFGSP)with the delivery time windows has been widely studied owing to its better flexibility and suitability for the current just-in-time production mode.However,there are several unresolved challenges in problem modeling and algorithmic design tailored for HFGSP.In our study,we place emphasis on the constraint of timeliness.Therefore,this paper first constructs a mixed integer linear programming model of HFGSP with sequence-dependent setup time and delivery time windows to minimize the total weighted earliness and tardiness(TWET).Then a penalty groups-assisted iterated greedy integrating idle time insertion(PG IG ITI)is proposed to solve the above problem.In the PG IG ITI,a double decoding strategy is proposed based on the earliest available machine rule and the idle time insertion rule to calculate the TWET value.Subsequently,to reduce the amount of computation,a skip-based destruction and reconstruction strategy is designed,and a penalty groups-assisted local search is proposed to further improve the quality of the solution by disturbing the penalized groups,i.e.,early and tardy groups.Finally,through comprehensive statistical experiments on 270 test instances,the results prove that the proposed algorithm is effective compared to four state-of-the-art algorithms.
