Flexible job shop scheduling problems(FJSP)have received much attention from academia and industry for many years.Due to their exponential complexity,swarm intelligence(SI)and evolutionary algorithms(EA)are developed,...Flexible job shop scheduling problems(FJSP)have received much attention from academia and industry for many years.Due to their exponential complexity,swarm intelligence(SI)and evolutionary algorithms(EA)are developed,employed and improved for solving them.More than 60%of the publications are related to SI and EA.This paper intents to give a comprehensive literature review of SI and EA for solving FJSP.First,the mathematical model of FJSP is presented and the constraints in applications are summarized.Then,the encoding and decoding strategies for connecting the problem and algorithms are reviewed.The strategies for initializing algorithms?population and local search operators for improving convergence performance are summarized.Next,one classical hybrid genetic algorithm(GA)and one newest imperialist competitive algorithm(ICA)with variables neighborhood search(VNS)for solving FJSP are presented.Finally,we summarize,discus and analyze the status of SI and EA for solving FJSP and give insight into future research directions.展开更多
A modified bottleneck-based （MB） heuristic for large-scale job-shop scheduling problems with a welldefined bottleneck is suggested, which is simpler but more tailored than the shifting bottleneck （SB） procedure. I...A modified bottleneck-based （MB） heuristic for large-scale job-shop scheduling problems with a welldefined bottleneck is suggested, which is simpler but more tailored than the shifting bottleneck （SB） procedure. In this algorithm, the bottleneck is first scheduled optimally while the non-bottleneck machines are subordinated around the solutions of the bottleneck schedule by some effective dispatching rules. Computational results indicate that the MB heuristic can achieve a better tradeoff between solution quality and computational time compared to SB procedure for medium-size problems. Furthermore, it can obtain a good solution in a short time for large-scale jobshop scheduling problems.展开更多
The job shop scheduli ng problem has been studied for decades and known as an NP-hard problem. The fl exible job shop scheduling problem is a generalization of the classical job sche duling problem that allows an oper...The job shop scheduli ng problem has been studied for decades and known as an NP-hard problem. The fl exible job shop scheduling problem is a generalization of the classical job sche duling problem that allows an operation to be processed on one machine out of a set of machines. The problem is to assign each operation to a machine and find a sequence for the operations on the machine in order that the maximal completion time of all operations is minimized. A genetic algorithm is used to solve the f lexible job shop scheduling problem. A novel gene coding method aiming at job sh op problem is introduced which is intuitive and does not need repairing process to validate the gene. Computer simulations are carried out and the results show the effectiveness of the proposed algorithm.展开更多
针对遗传算法解决车间作业调度问题时存在早熟收敛的缺点,采用一种新型进化算法——DNA进化算法解决车间作业调度问题.将算法从连续优化问题拓展用于解决离散优化问题,并将其成功地应用于Job shop生产调度.采用了著名的M u th和T hom p...针对遗传算法解决车间作业调度问题时存在早熟收敛的缺点,采用一种新型进化算法——DNA进化算法解决车间作业调度问题.将算法从连续优化问题拓展用于解决离散优化问题,并将其成功地应用于Job shop生产调度.采用了著名的M u th和T hom pson标准问题FT 10进行了验证.仿真结果表明,与遗传算法相比,该算法简单有效,不仅具有很好的求解性能,而且具有更快的收敛速度和全局搜索能力.展开更多
基金supported in part by the National Natural Science Foundation of China(61603169,61773192,61803192)in part by the funding from Shandong Provincial Key Laboratory for Novel Distributed Computer Software Technologyin part by Singapore National Research Foundation(NRF-RSS2016-004)
文摘Flexible job shop scheduling problems(FJSP)have received much attention from academia and industry for many years.Due to their exponential complexity,swarm intelligence(SI)and evolutionary algorithms(EA)are developed,employed and improved for solving them.More than 60%of the publications are related to SI and EA.This paper intents to give a comprehensive literature review of SI and EA for solving FJSP.First,the mathematical model of FJSP is presented and the constraints in applications are summarized.Then,the encoding and decoding strategies for connecting the problem and algorithms are reviewed.The strategies for initializing algorithms?population and local search operators for improving convergence performance are summarized.Next,one classical hybrid genetic algorithm(GA)and one newest imperialist competitive algorithm(ICA)with variables neighborhood search(VNS)for solving FJSP are presented.Finally,we summarize,discus and analyze the status of SI and EA for solving FJSP and give insight into future research directions.
基金the National Natural Science Foundation of China (6027401360474002)Shanghai Development Found for Science and Technology (04DZ11008).
文摘A modified bottleneck-based （MB） heuristic for large-scale job-shop scheduling problems with a welldefined bottleneck is suggested, which is simpler but more tailored than the shifting bottleneck （SB） procedure. In this algorithm, the bottleneck is first scheduled optimally while the non-bottleneck machines are subordinated around the solutions of the bottleneck schedule by some effective dispatching rules. Computational results indicate that the MB heuristic can achieve a better tradeoff between solution quality and computational time compared to SB procedure for medium-size problems. Furthermore, it can obtain a good solution in a short time for large-scale jobshop scheduling problems.
文摘The job shop scheduli ng problem has been studied for decades and known as an NP-hard problem. The fl exible job shop scheduling problem is a generalization of the classical job sche duling problem that allows an operation to be processed on one machine out of a set of machines. The problem is to assign each operation to a machine and find a sequence for the operations on the machine in order that the maximal completion time of all operations is minimized. A genetic algorithm is used to solve the f lexible job shop scheduling problem. A novel gene coding method aiming at job sh op problem is introduced which is intuitive and does not need repairing process to validate the gene. Computer simulations are carried out and the results show the effectiveness of the proposed algorithm.
文摘针对遗传算法解决车间作业调度问题时存在早熟收敛的缺点,采用一种新型进化算法——DNA进化算法解决车间作业调度问题.将算法从连续优化问题拓展用于解决离散优化问题,并将其成功地应用于Job shop生产调度.采用了著名的M u th和T hom pson标准问题FT 10进行了验证.仿真结果表明,与遗传算法相比,该算法简单有效,不仅具有很好的求解性能,而且具有更快的收敛速度和全局搜索能力.
