改进遗传算法求解多时间约束的柔性作业车间调度问题

doi:10.3969/j.issn.1007-7375.2020.02.003

工业工程 ›› 2020, Vol. 23 ›› Issue (2): 19-25,48.doi: 10.3969/j.issn.1007-7375.2020.02.003

改进遗传算法求解多时间约束的柔性作业车间调度问题

张国辉, 胡一凡, 孙靖贺

郑州航空工业管理学院管理工程学院，河南郑州 450015

收稿日期:2019-12-12 发布日期:2020-04-22
作者简介:张国辉(1980-)，男，河南省人，教授，博士，主要研究方向为车间调度、智能优化算法
基金资助:
国家自然科学基金资助项目（U1904167， 51705472）；教育部人文社科研究规划基金资助项目（18YJAZH125）；河南省科技创新杰出青年资助项目（184100510001）

An Improved Genetic Algorithm for Flexible Job Shop Scheduling Problem with Multiple Time Constraints

ZHANG Guohui, HU Yifan, SUN Jinghe

School of Management Engineering, Zhengzhou University of Aeronautics, Zhengzhou 450015, China

Received:2019-12-12 Published:2020-04-22

摘要/Abstract

摘要： 将加工时间、调整时间和移动时间分别作为独立时间因素考虑到柔性作业车间调度模型中，建立以最大完工时间最小、总调整时间最小、总移动时间最小为目标的考虑多时间约束的柔性作业车间调度模型，并提出改进的遗传算法求解该模型。通过测试标准数据集，并对比其他文献算法，验证了改进的遗传算法的可行性和有效性。

关键词: 柔性作业车间调度, 遗传算法, 调整时间, 移动时间, 最大完工时间

Abstract: The processing time, set-up time and transport time are considered as independent time factors in the flexible job shop scheduling model. A flexible job shop scheduling model considering multiple time constraints is established with the goal of minimum makespan, minimum total set-up time and minimum total transport time. An improved genetic algorithm is proposed to solve the model. By testing the standard data set and comparing with other literature algorithms, the feasibility and effectiveness of the improved genetic algorithm are verified.

Key words: flexible job shop scheduling, genetic algorithm, set-up time, transport time, makespan

中图分类号:

TP301

张国辉, 胡一凡, 孙靖贺. 改进遗传算法求解多时间约束的柔性作业车间调度问题[J]. 工业工程, 2020, 23(2): 19-25,48.

ZHANG Guohui, HU Yifan, SUN Jinghe. An Improved Genetic Algorithm for Flexible Job Shop Scheduling Problem with Multiple Time Constraints[J]. Industrial Engineering Journal, 2020, 23(2): 19-25,48.

参考文献

[1] SHEN L, DAUZÈRE-PÉRÈS S, NEUFELD J S. Solving the flexible job shop scheduling problem with sequence-dependent setup times[J]. European Journal of Operational Research, 2017, 265(2): 503-516
[2] ROSSI A, DINI G. Flexible job-shop scheduling with routing flexibility and separable setup times using ant colony optimisation method[J]. Robotics and Computer-Integrated Manufacturing, 2007, 23(5): 503-516
[3] 杨立熙, 余慧慧. 考虑运输时间的柔性作业车间调度问题研究[J]. 武汉理工大学学报(信息与管理工程版), 2017, 39(1): 608-613
YANG Lixi, YU Huihui. Research on flexible job-shop scheduling problem with transport time consideration[J]. Journal of Wuhan University of Technology (Information & Management Engineering), 2017, 39(1): 608-613
[4] 赵宁, 李开典, 田青, 等. 考虑运输时间柔性作业车间调度问题的快速寻优方法[J]. 计算机集成制造系统, 2015, 21(3): 724-732
ZHAO Ning, LI Kaidian, TIAN Qing, et al. Fast optimization approach of flexible job shop scheduling with transport time consideration[J]. Computer Integrated Manufacturing Systems, 2015, 21(3): 724-732
[5] 朱伟. 基于规则导向的柔性作业车间多目标动态调度算法[J]. 系统工程理论与实践, 2017, 37(10): 2690-2699
ZHU Wei. Multi-objective dynamic scheduling algorithm for flexible job-shop problem based on rule orientation[J]. Systems Engineering—Theory & Practice, 2017, 37(10): 2690-2699
[6] NOURI H E, DRISS O B, GHÉDIRA K. Solving the flexible job shop problem by hybrid metaheuristics-based multiagent model[J]. Journal of Industrial Engineering International, 2018, 14(1): 1-14
[7] ZHANG G H, SHAO X Y, LI P G, et al. An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem[J]. Computers & Industrial Engineering, 2009, 56(4): 1309-1318
[8] 余璇, 梁工谦, 董仲慧. 基于混合遗传禁忌搜索算法的多目标柔性作业车间调度[J]. 机械制造, 2016, 54(8): 90-93
[9] 余建军, 孙树栋, 郝京辉. 免疫算法求解多目标柔性作业车间调度研究[J]. 计算机集成制造系统, 2006, 12(10): 1643-1650
YU Jianjun, SUN Shudong, HAO Jinghui. Multi-objective flexible job-shop scheduling based on immune algorithm[J]. Computer Integrated Manufacturing Systems, 2006, 12(10): 1643-1650
[10] 李明, 雷德明. 基于新型帝国竞争算法的高维多目标柔性作业车间调度[J]. 控制理论与应用, 2019, 36(6): 893-901
LI Ming, LEI Deming. Novel imperialist competitive algorithm for many-objective flexible job shop scheduling[J]. Control Theory & Applications, 2019, 36(6): 893-901
[11] 林震, 帅剑平, 袁煜. 多目标柔性作业车间调度的多交叉策略元胞进化算法[J]. 科学技术与工程, 2017, 17(7): 74-81
LIN Zhen, SHUAI Jianping, YUAN Yu. Multi-crossover strategy of multi-objective cellular genetic algorithm research on flexible job-shop scheduling problem[J]. Science Technology and Engineering, 2017, 17(7): 74-81
[12] 张国辉, 张海军, 张理涛, 等. 改进遗传算法求解低碳约束的柔性车间调度问题[J]. 组合机床与自动化加工技术, 2018(6): 180-184
ZHANG Guohui, ZHANG Haijun, ZHANG Litao, et al. Solving the flexible job shop scheduling problem under the restriction of low carbon based on improved genetic algorithm[J]. Modular Machine Tool & Automatic Manufacturing Technique, 2018(6): 180-184
[13] BRANDIMARTE P. Routing and scheduling in a flexible job shop by tabu search[J]. Annals of Operations Research, 1993, 41(3): 157-183

[1]	张正敏, 管在林, 岳磊. 基于Lévy Flight的混合GA在柔性作业车间调度问题中的性能分析[J]. 工业工程, 2021, 24(4): 83-92.
[2]	王晓军, 王博, 晋民杰, 杨春霞, 白新利. 改进多种群遗传算法的AutoStore系统多AGV调度优化[J]. 工业工程, 2021, 24(4): 112-118,167.
[3]	王莹莹, 吴立云. 基于改进NSGA-II的多项目多技能人力资源调度研究[J]. 工业工程, 2021, 24(3): 130-138.
[4]	曾创锋, 刘建军, 陈庆新, 毛宁. 求解一类无关并行机调度的遗传迭代贪心算法[J]. 工业工程, 2021, 24(2): 110-118.
[5]	黄露, 纪延光. 考虑顾客延误损失的配送中心选址双层规划问题研究[J]. 工业工程, 2021, 24(2): 141-147.
[6]	王冰怡, 张锦. 考虑网点共享与变更的多级快递网点选址问题[J]. 工业工程, 2021, 24(2): 155-165.
[7]	马跃如, 文铮, 易丹. 考虑老年人满意度的多目标居家养老护理员路径优化[J]. 工业工程, 2021, 24(1): 74-81,103.
[8]	王玖河, 高辉, 刘欢. 基于遗传算法的共享助力车调度问题研究[J]. 工业工程, 2021, 24(1): 90-96.
[9]	吴斌, 宋琰, 程晶, 董敏. 基于密度峰值聚类的VRPTW问题研究[J]. 工业工程, 2020, 23(5): 58-66,74.
[10]	王苏林, 邱菲尔, 陈凡, 刘川昆, 鹿腾, 王芷芸. 基于贪心遗传的地下物流节点选择规划研究[J]. 工业工程, 2020, 23(5): 88-95.
[11]	侯艳, 黄康焕, 张亿仙, 伍乃骐. 原油一次加工过程的多目标调度优化[J]. 工业工程, 2020, 23(4): 131-139.
[12]	王泽, 杨信丰, 刘兰芬. 考虑电量消耗的车辆调度优化研究[J]. 工业工程, 2020, 23(4): 140-147.
[13]	曾垂飞, 刘建军, 陈庆新, 毛宁. 装配作业车间分批调度问题的算法对比[J]. 工业工程, 2020, 23(4): 174-182.
[14]	张巍, 李鹏翔, 仝自强, 岳毅蒙. 基于损坏车辆分布预测与损益阈值分析下的共享单车回收研究[J]. 工业工程, 2020, 23(3): 132-137.
[15]	李峥峰, 于小忠, 张国辉, 崔陆军. 考虑生产过程时间的柔性作业车间调度优化[J]. 工业工程, 2020, 23(2): 26-33,123.

改进遗传算法求解多时间约束的柔性作业车间调度问题

An Improved Genetic Algorithm for Flexible Job Shop Scheduling Problem with Multiple Time Constraints

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价