离散回溯搜索算法求解多柔性作业车间调度

doi:10.12005/orms.2022.0013

运筹与管理 ›› 2022, Vol. 31 ›› Issue (1): 87-91.DOI: 10.12005/orms.2022.0013

离散回溯搜索算法求解多柔性作业车间调度

董海¹, 徐晓鹏²

1.沈阳大学应用技术学院,辽宁沈阳 110044;
2.大连理工大学机械工程学院,辽宁沈阳 110044

收稿日期:2019-07-30 出版日期:2022-01-25 发布日期:2022-02-11
作者简介:董海(1971-),男,山东淄博人,教授,博士,研究方向:先进生产系统建模优化与控制、制造企业物流运作流程优化;徐晓鹏(1991-),男,辽宁沈阳人,硕士研究生,研究方向:先进生产系统建模优化与控制。
基金资助:
自然科学基金资助项目(71672117)

Solving Multi-flexible Job-shop Scheduling Problem by Discrete Backtracking Search Algorithm

DONG Hai¹, XU Xiao-peng²

1. School of Applied Technology, Shenyang University, Shenyang 110044, China;
2. School of Mechanical Engineering. Shenyang University, Shenyang 110044, China

Received:2019-07-30 Online:2022-01-25 Published:2022-02-11

摘要/Abstract

摘要： 针对柔性作业车间生产中机器和工序柔性与多能工的存在建立模型,并提出一种整数编码方案和设一种基于Pareto解集的离散回溯搜索算法进行求解。首先,采用精英化历史种群的方法提升历史种群引导当前种群进化的能力;其次,在交叉变异步骤用遗传交叉算子替代回溯搜索算法原有结构;再次,为保留更多较优解到当前种群,结合快速非支配排序方法更新当前种群;最后,求解数值实例,与多种智能算法进行对比,验证算法的可行性和有效性。

关键词: 作业车间调度问题, 多能工, 回溯搜索算法, 快速非支配排序

Abstract: Considering multi-skilled workers and the flexibility of machines and operations, a model is built. An integer coding and a discrete backtracking search algorithm based on Pareto set is proposed. Firstly, a method of improving the historical population is proposed to better guide evolution; secondly, at the mutation and crossover stage, the genetic crossover operators are used to replace the origin algorithm structure in the backtracking search algorithm; thirdly, to ensure better solutions to be retained, the current population is refreshed based on fast non-dominated sorting. Finally, effectiveness and feasibility of the algorithm is tested in a calculation example constructed.

Key words: job-shop scheduling problem, multi-skilled workers, backtracking search algorithm, fast non-dominated sorting

中图分类号:

董海, 徐晓鹏. 离散回溯搜索算法求解多柔性作业车间调度[J]. 运筹与管理, 2022, 31(1): 87-91.

DONG Hai, XU Xiao-peng. Solving Multi-flexible Job-shop Scheduling Problem by Discrete Backtracking Search Algorithm[J]. Operations Research and Management Science, 2022, 31(1): 87-91.

参考文献

[1] 徐华,张庭.混合离散蝙蝠算法求解多目标柔性作业车间调度[J].机械工程学报,2016,52(18):201-212.
[2] 艾子义,雷德明.基于新型蛙跳算法的低碳柔性作业车间调度[J].控制理论与应用,2017,34(10):1361-1368.
[3] 张其亮,俞祚明.基于优势种群的离散果蝇优化算法求解无等待流水车间调度问题[J].计算机集成制造系统,2017,23(03) 609-615.
[4] 雷德明.基于新型教学优化算法的低碳柔性作业车间调度[J].控制与决策,2017,32(09):1621-1627.
[5] 肖华军,柴子力,张超勇,等.基于混合化学反应算法的柔性作业车间调度[J].计算机集成制造系统,2018,24(09):2234-2245.
[6] 姜天华.基于灰狼优化算法的低碳车间调度问题[J].计算机集成制造系统,2018,24(10):2428-2435.
[7] 黄海松,刘凯,初光勇.离散花朵授粉算法求解多目标柔性车间调度[J].计算机集成制造系统,2018,24(11):2808-2818.
[8] 任彩乐,张超勇,孟磊磊,等.基于改进候鸟优化算法的混合流水车间调度问题[J].计算机集成制造系统,2019,25(03):643-653.
[9] 黄学文,马雪丽,曹德弼.工序顺序柔性的作业车间调度问题的改进遗传算法求解[J].运筹与管理,2013,22(01):65-70.
[10] 黄学文,赵兴野,于跃绮,等.作业车间关键柔性的描述及其度量研究综述[J].计算机集成制造系统,2015,21(12):3153-3165.
[11] 黄学文,孙娜,孙榕,等.工序顺序柔性描述模型研究[J].计算机集成制造系统,2016,22(10):2275-2283.
[12] 黄学文,张晓彤,孙榕,等.基于遗传算法的工艺路径柔性调度算法[J].运筹与管理,2018,27(06):184-193.
[13] Zheng X, Wang L A. knowledge-guided fruit fly optimization algorithm for dual resource constrained flexible job-shop scheduling problem[J]. International Journal of Production Research, 2016, 54 (18): 1-13.
[14] 李兢尧,黄媛,王军强.基于压缩时窗的双资源约束作业车间调度策略[J].计算机集成制造系统,2016,22(12):2827-2835.
[15] 关叶青,朱颖,谢乃明.考虑多成本约束的柔性作业车间制造资源动态分配模型[J].控制与决策,2018,33(11):2037-2044.
[16] 周亚勤,杨长祺,吕佑龙,等.双资源约束的航天结构件车间生产调度方法[J].机械工程学报,2018,54(09):55-63.
[17] CIVICIAGLU P. Backtracking search optimization algorithm for optimization problems[J]. Applied Mathematics and Computation, 2013, 219(15): 8121-8144.
[18] 崔琪,吴秀丽,余建军.变邻域改进遗传算法求解混合流水车间调度问题[J].计算机集成制造系统,2017,23(09):1917-1927.
[19] Gong G, Deng Q, Gong X, et al. A new double flexible job-shop scheduling problem integrating processing time, green production, and human factor indicators[J]. Journal of cleaner production, 2018, 174: 560-576.
[20] 仇永涛,吉卫喜,张朝阳.结合混合进化算法和知识的多目标车间调度[J].中国机械工程,2020,31(24):2979-2987.
[21] 顾幸生,丁豪杰.面向柔性作业车间调度问题的改进博弈粒子群算法[J].同济大学学报(自然科学版),2020,48(12):1782-1789.
[22] 吴锐,郭顺生,李益兵,等.改进人工蜂群算法求解分布式柔性作业车间调度问题[J].控制与决策,2019,34(12):2527-2536.

离散回溯搜索算法求解多柔性作业车间调度

Solving Multi-flexible Job-shop Scheduling Problem by Discrete Backtracking Search Algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 2

编辑推荐

Metrics

[1]	景熠, 李琴. 多工厂环境下考虑个体利益的多目标协同生产计划模型及算法[J]. 运筹与管理, 2020, 29(2): 212-218.
[2]	田旻,张光军,刘人境. 粒子群遗传混合算法求解考虑传输时间的FJSP[J]. 运筹与管理, 2019, 28(4): 78-88.