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.展开更多
Safe and efficient sortie scheduling on the confined flight deck is crucial for maintaining high combat effectiveness of the aircraft carrier.The primary difficulty exactly lies in the spatiotemporal coordination,i.e....Safe and efficient sortie scheduling on the confined flight deck is crucial for maintaining high combat effectiveness of the aircraft carrier.The primary difficulty exactly lies in the spatiotemporal coordination,i.e.,allocation of limited supporting resources and collision-avoidance between heterogeneous dispatch entities.In this paper,the problem is investigated in the perspective of hybrid flow-shop scheduling problem by synthesizing the precedence,space and resource constraints.Specifically,eight processing procedures are abstracted,where tractors,preparing spots,catapults,and launching are virtualized as machines.By analyzing the constraints in sortie scheduling,a mixed-integer planning model is constructed.In particular,the constraint on preparing spot occupancy is improved to further enhance the sortie efficiency.The basic trajectory library for each dispatch entity is generated and a delayed strategy is integrated to address the collision-avoidance issue.To efficiently solve the formulated HFSP,which is essentially a combinatorial problem with tightly coupled constraints,a chaos-initialized genetic algorithm is developed.The solution framework is validated by the simulation environment referring to the Fort-class carrier,exhibiting higher sortie efficiency when compared to existing strategies.And animation of the simulation results is available at www.bilibili.com/video/BV14t421A7Tt/.The study presents a promising supporting technique for autonomous flight deck operation in the foreseeable future,and can be easily extended to other supporting scenarios,e.g.,ammunition delivery and aircraft maintenance.展开更多
A new bottleneck-based heuristic for large-scale flow-shop scheduling problems with a bottleneck is proposed, which is simpler but more tailored than the shifting bottleneck （SB） procedure. In this algorithm, a sche...A new bottleneck-based heuristic for large-scale flow-shop scheduling problems with a bottleneck is proposed, which is simpler but more tailored than the shifting bottleneck （SB） procedure. In this algorithm, a schedule for the bottleneck machine is first constructed optimally and then the non-bottleneck machines are scheduled around the bottleneck schedule by some effective dispatching rules. Computational results show that the modified bottleneck-based procedure can achieve a tradeoff between solution quality and computational time comparing with SB procedure for medium-size problems. Furthermore it can obtain a good solution in quite short time for large-scale scheduling problems.展开更多
The Mixed No-Idle Flow-shop Scheduling Problem(MNIFSP)is an extension of flow-shop scheduling,which has practical significance and application prospects in production scheduling.To improve the efficacy of solving the ...The Mixed No-Idle Flow-shop Scheduling Problem(MNIFSP)is an extension of flow-shop scheduling,which has practical significance and application prospects in production scheduling.To improve the efficacy of solving the complicated multiobjective MNIFSP,a MultiDirection Update(MDU)based Multiobjective Particle Swarm Optimization(MDU-MoPSO)is proposed in this study.For the biobjective optimization problem of the MNIFSP with minimization of makespan and total processing time,the MDU strategy divides particles into three subgroups according to a hybrid selection mechanism.Each subgroup prefers one convergence direction.Two subgroups are individually close to the two edge areas of the Pareto Front(PF)and serve two objectives,whereas the other one approaches the central area of the PF,preferring the two objectives at the same time.The MDU-MoPSO adopts a job sequence representation method and an exchange sequence-based particle update operation,which can better reflect the characteristics of sequence differences among particles.The MDU-MoPSO updates the particle in multiple directions and interacts in each direction,which speeds up the convergence while maintaining a good distribution performance.The experimental results and comparison of six classical evolutionary algorithms for various benchmark problems demonstrate the effectiveness of the proposed algorithm.展开更多
基金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 financial support of the National Key Research and Development Plan(2021YFB3302501)the financial support of the National Natural Science Foundation of China(12102077)。
文摘Safe and efficient sortie scheduling on the confined flight deck is crucial for maintaining high combat effectiveness of the aircraft carrier.The primary difficulty exactly lies in the spatiotemporal coordination,i.e.,allocation of limited supporting resources and collision-avoidance between heterogeneous dispatch entities.In this paper,the problem is investigated in the perspective of hybrid flow-shop scheduling problem by synthesizing the precedence,space and resource constraints.Specifically,eight processing procedures are abstracted,where tractors,preparing spots,catapults,and launching are virtualized as machines.By analyzing the constraints in sortie scheduling,a mixed-integer planning model is constructed.In particular,the constraint on preparing spot occupancy is improved to further enhance the sortie efficiency.The basic trajectory library for each dispatch entity is generated and a delayed strategy is integrated to address the collision-avoidance issue.To efficiently solve the formulated HFSP,which is essentially a combinatorial problem with tightly coupled constraints,a chaos-initialized genetic algorithm is developed.The solution framework is validated by the simulation environment referring to the Fort-class carrier,exhibiting higher sortie efficiency when compared to existing strategies.And animation of the simulation results is available at www.bilibili.com/video/BV14t421A7Tt/.The study presents a promising supporting technique for autonomous flight deck operation in the foreseeable future,and can be easily extended to other supporting scenarios,e.g.,ammunition delivery and aircraft maintenance.
基金This project is supported by National Natural Science Foundation of China (No.60274013, No.60474002)Shanghai City Development Found for Science and Technology, China(No.04DZ11008)
文摘A new bottleneck-based heuristic for large-scale flow-shop scheduling problems with a bottleneck is proposed, which is simpler but more tailored than the shifting bottleneck （SB） procedure. In this algorithm, a schedule for the bottleneck machine is first constructed optimally and then the non-bottleneck machines are scheduled around the bottleneck schedule by some effective dispatching rules. Computational results show that the modified bottleneck-based procedure can achieve a tradeoff between solution quality and computational time comparing with SB procedure for medium-size problems. Furthermore it can obtain a good solution in quite short time for large-scale scheduling problems.
基金国家科技公关计划项目(the Key Technologies R&D Program of China under Grant No.2001BA201A32)国家高技术研究发展计划(863) (the National High-Tech Research and Development Plan of China under Grant No.2002AA415270)
基金This work was partly supported by the National Natural Science Foundation of China(No.61772173)the Science and Technology Research Project of Henan Province(No.202102210131)+1 种基金the Innovative Funds Plan of Henan University of Technology(No.2020ZKCJ02)the Grant-in-Aid for Scientific Research(C)of Japan Society of Promotion of Science(No.19K12148).
文摘The Mixed No-Idle Flow-shop Scheduling Problem(MNIFSP)is an extension of flow-shop scheduling,which has practical significance and application prospects in production scheduling.To improve the efficacy of solving the complicated multiobjective MNIFSP,a MultiDirection Update(MDU)based Multiobjective Particle Swarm Optimization(MDU-MoPSO)is proposed in this study.For the biobjective optimization problem of the MNIFSP with minimization of makespan and total processing time,the MDU strategy divides particles into three subgroups according to a hybrid selection mechanism.Each subgroup prefers one convergence direction.Two subgroups are individually close to the two edge areas of the Pareto Front(PF)and serve two objectives,whereas the other one approaches the central area of the PF,preferring the two objectives at the same time.The MDU-MoPSO adopts a job sequence representation method and an exchange sequence-based particle update operation,which can better reflect the characteristics of sequence differences among particles.The MDU-MoPSO updates the particle in multiple directions and interacts in each direction,which speeds up the convergence while maintaining a good distribution performance.The experimental results and comparison of six classical evolutionary algorithms for various benchmark problems demonstrate the effectiveness of the proposed algorithm.
