The distributed hybrid flow shop scheduling problem(DHFSP),which integrates distributed manufacturing models with parallel machines,has gained significant attention.However,in actual scheduling,some adjacent machines ...The distributed hybrid flow shop scheduling problem(DHFSP),which integrates distributed manufacturing models with parallel machines,has gained significant attention.However,in actual scheduling,some adjacent machines do not have buffers between them,resulting in blocking.This paper focuses on addressing the DHFSP with blocking constraints(DBHFSP)based on the actual production conditions.To solve DBHFSP,we construct a mixed integer linear programming(MILP)model for DBHFSP and validate its correctness using the Gurobi solver.Then,an advanced iterated greedy(AIG)algorithm is designed to minimize the makespan,in which we modify the Nawaz,Enscore,and Ham(NEH)heuristic to solve blocking constraints.To balance the global and local search capabilities of AIG,two effective inter-factory neighborhood search strategies and a swap-based local search strategy are designed.Additionally,each factory is mutually independent,and the movement within one factory does not affect the others.In view of this,we specifically designed a memory-based decoding method for insertion operations to reduce the computation time of the objective.Finally,two shaking strategies are incorporated into the algorithm to mitigate premature convergence.Five advanced algorithms are used to conduct comparative experiments with AIG on 80 test instances,and experimental results illustrate that the makespan and the relative percentage increase(RPI)obtained by AIG are 1.0%and 86.1%,respectively,better than the comparative algorithms.展开更多
To meet the multi-cooperation production demand of enterprises,the distributed permutation flow shop scheduling problem(DPFSP)has become the frontier research in the field of manufacturing systems.In this paper,we inv...To meet the multi-cooperation production demand of enterprises,the distributed permutation flow shop scheduling problem(DPFSP)has become the frontier research in the field of manufacturing systems.In this paper,we investigate the DPFSP by minimizing a makespan criterion under the constraint of sequence-dependent setup times.To solve DPFSPs,significant developments of some metaheuristic algorithms are necessary.In this context,a simple and effective improved iterated greedy(NIG)algorithm is proposed to minimize makespan in DPFSPs.According to the features of DPFSPs,a two-stage local search based on single job swapping and job block swapping within the key factory is designed in the proposed algorithm.We compare the proposed algorithm with state-of-the-art algorithms,including the iterative greedy algorithm(2019),iterative greedy proposed by Ruiz and Pan(2019),discrete differential evolution algorithm(2018),discrete artificial bee colony(2018),and artificial chemical reaction optimization(2017).Simulation results show that NIG outperforms the compared algorithms.展开更多
基金This work was jointly supported by the National Natural Science Foundation of Shandong Province(No.ZR2023MF022)National Natural Science Foundation of China(Nos.61973203,62173216,and 62173356)Guangyue Youth Scholar Innovation Talent Program Support from Liaocheng University(No.LCUGYTD2022-03).
文摘The distributed hybrid flow shop scheduling problem(DHFSP),which integrates distributed manufacturing models with parallel machines,has gained significant attention.However,in actual scheduling,some adjacent machines do not have buffers between them,resulting in blocking.This paper focuses on addressing the DHFSP with blocking constraints(DBHFSP)based on the actual production conditions.To solve DBHFSP,we construct a mixed integer linear programming(MILP)model for DBHFSP and validate its correctness using the Gurobi solver.Then,an advanced iterated greedy(AIG)algorithm is designed to minimize the makespan,in which we modify the Nawaz,Enscore,and Ham(NEH)heuristic to solve blocking constraints.To balance the global and local search capabilities of AIG,two effective inter-factory neighborhood search strategies and a swap-based local search strategy are designed.Additionally,each factory is mutually independent,and the movement within one factory does not affect the others.In view of this,we specifically designed a memory-based decoding method for insertion operations to reduce the computation time of the objective.Finally,two shaking strategies are incorporated into the algorithm to mitigate premature convergence.Five advanced algorithms are used to conduct comparative experiments with AIG on 80 test instances,and experimental results illustrate that the makespan and the relative percentage increase(RPI)obtained by AIG are 1.0%and 86.1%,respectively,better than the comparative algorithms.
基金This work was jointly supported by the National Natural Science Foundation of China(Nos.61803192,61973203,61966012,61773192,61603169,61773246,and 71533001)Thanks for the support of Shandong province colleges and universities youth innovation talent introduction and education program.
文摘To meet the multi-cooperation production demand of enterprises,the distributed permutation flow shop scheduling problem(DPFSP)has become the frontier research in the field of manufacturing systems.In this paper,we investigate the DPFSP by minimizing a makespan criterion under the constraint of sequence-dependent setup times.To solve DPFSPs,significant developments of some metaheuristic algorithms are necessary.In this context,a simple and effective improved iterated greedy(NIG)algorithm is proposed to minimize makespan in DPFSPs.According to the features of DPFSPs,a two-stage local search based on single job swapping and job block swapping within the key factory is designed in the proposed algorithm.We compare the proposed algorithm with state-of-the-art algorithms,including the iterative greedy algorithm(2019),iterative greedy proposed by Ruiz and Pan(2019),discrete differential evolution algorithm(2018),discrete artificial bee colony(2018),and artificial chemical reaction optimization(2017).Simulation results show that NIG outperforms the compared algorithms.
