求解一类无关并行机调度的遗传迭代贪心算法

doi:10.3969/j.issn.1007-7375.2021.02.014

工业工程 ›› 2021, Vol. 24 ›› Issue (2): 110-118.doi: 10.3969/j.issn.1007-7375.2021.02.014

求解一类无关并行机调度的遗传迭代贪心算法

曾创锋, 刘建军, 陈庆新, 毛宁

广东工业大学广东省计算机集成制造重点实验室，广东广州 510006

收稿日期:2019-10-28 发布日期:2021-04-25
通讯作者: 刘建军,刘建军(1982-)，男，江西省人，副教授，主要研究方向为工业工程、生产计划与控制等。E-mail：jianjun.liu@gdut.edu.cn E-mail:jianjun.liu@gdut.edu.cn
作者简介:曾创锋(1995-)，男，广东省人，硕士研究生，主要研究方向为智能优化算法、生产调度等
基金资助:
国家自然科学基金资助项目(51975129, 71572049, 61973089)；广东省自然科学基金资助项目(2019A1515012158)；广东省特支计划科技创新青年拔尖人才项目(2016TQ03X364)

A Genetic Algorithm-Iterative Greedy Algorithm for a Kind of Unrelated Parallel Machine Scheduling Problem

ZENG Chuangfeng, LIU Jianjun, CHEN Qingxin, MAO Ning

Guangdong CIM Provincial Key Lab, Guangdong University of Technology, Guangzhou 510006, China

Received:2019-10-28 Published:2021-04-25

摘要/Abstract

摘要： 以最小化最大完工时间为优化目标，建立带工单加工约束和序相关设置时间无关并行机调度问题的混合整数规划模型；考虑现实生产对求解算法在质量、收敛速度和鲁棒性等方面的较高要求，构建一种混合遗传-迭代贪心算法。在遗传变异操作中嵌入一种迭代贪心策略的破坏和构建机制，用于提高算法的种群多样性；引入基于破坏与构建操作设计而成的快速局部搜索算法来增强算法的局部开发能力；基于实际生产数据的相关特征随机生成了一系列计算案例，并通过实验说明所提新型混合算法相较于传统混合算法的优越性。

关键词: 无关并行机调度, 序相关设置时间, 遗传算法, 迭代贪心策略

Abstract: A deliberation is conducted on the unrelated parallel machine scheduling problem with job processing constraints and sequence-dependent setup times (UPMSP_JPCSST), that is, the same job has a number of alternative heterogeneous machines for processing, and the setup time of adjacent jobs on the same machine is determined by the product type and material type attributes. The objective is to minimize the total completion time and formulates a mixed integer programming model. Considering the higher requirements of practical production on the quality, convergence speed and robustness of the solution algorithm, a hybrid algorithm (genetic algorithm-iterated greedy algorithm, GAIG) is constructed. Firstly, the destruction and construction mechanism of an iterative greedy strategy is embedded in the genetic mutation operation to improve the population diversity of the algorithm. Secondly, a fast local search algorithm based on destruction and construction operation is introduced to enhance the local development ability of the algorithm; and finally, a series of calculation cases are generated randomly based on the relevant characteristics of actual production data, and the advantages of the proposed new hybrid algorithm over the traditional hybrid algorithm are illustrated through experiments.

Key words: unrelated parallel machine scheduling, sequence-dependent setup times, genetic algorithm, iterative greedy strategy

中图分类号:

F406

曾创锋, 刘建军, 陈庆新, 毛宁. 求解一类无关并行机调度的遗传迭代贪心算法[J]. 工业工程, 2021, 24(2): 110-118.

ZENG Chuangfeng, LIU Jianjun, CHEN Qingxin, MAO Ning. A Genetic Algorithm-Iterative Greedy Algorithm for a Kind of Unrelated Parallel Machine Scheduling Problem[J]. Industrial Engineering Journal, 2021, 24(2): 110-118.

参考文献

[1] GRAHAM R L, LAWLER E L, LENSTRA J K, et al. Optimization and approximation in deterministic sequencing and scheduling: a survey[J]. Annals of Discrete Mathematics, 1979, 5: 287-326
[2] 唐恒永, 赵传立. 排序引论[M]. 北京: 科学出版社, 2002.
[3] VALLADA E, RUIZ R. A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times[J]. European Journal of Operational Research, 2011, 211(3): 612-622
[4] LIN Y K, LIN C W. Dispatching rules for unrelated parallel machine scheduling with release dates[J]. The International Journal of Advanced Manufacturing Technology, 2013, 67: 269-279
[5] 邓冠龙, 顾幸生, 崔喆. 基于群智能优化的车间调度方法[M]. 北京: 清华大学出版社, 2016.
[6] EZUGWU A E, ADELEKE O J, VIRIRI S. Symbiotic organisms search algorithm for the unrelated parallel machines scheduling with sequence-dependent setup times[J]. Plos One, 2018, 13(7): e0200030_1-e0200030_23
[7] KIM D W, KIM K H, JANG W, et al. Unrelated parallel machine scheduling with setup times using simulated annealing[J]. Robotics and Computer-Integrated Manufacturing, 2002, 18(3-4): 223-231
[8] ZEIDI J R, MOHAMMADHOSSEINI S. Scheduling unrelated parallel machines with sequence-dependent setup times[J]. International Journal of Advanced Manufacturing Technology, 2015, 81: 1487-1496
[9] 王凌, 郑大钟. 一种GASA混合优化策略[J]. 控制理论与应用, 2008, 18(4): 552-554
WANG Ling, ZHENG Dazhong. A kind of GASA hybrid optimization strategy[J]. Control Theory and Applications, 2008, 18(4): 552-554
[10] 李作成, 钱斌, 胡蓉, 等. 遗传-分布估计算法求解化工生产中一类带多工序的异构并行机调度问题[J]. 化工学报, 2014, 65(3): 981-992
LI Zuocheng, QIAN Bing, HU Rong, et al. A genetic algorithm-estimation of distribution algorithm for a kind of heterogeneous parallel machine scheduling problem with multiple operations in chemical production[J]. CIESC Journal, 2014, 65(3): 981-992
[11] JOO C M, KIM B S. Hybrid genetic algorithms with dispatching rules for unrelated parallel machine scheduling with setup time and production availability[J]. Computers & Industrial Engineering, 2015, 85: 102-109
[12] AFZALIRAD M, SHAFIPOUR M. Design of an efficient genetic algorithm for resource-constrained unrelated parallel machine scheduling problem with machine eligibility restrictions[J]. Journal of Intelligent Manufacturing, 2015, 29: 423-437
[13] RUIZ R, STUTZLE T. A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem[J]. European Journal of Operational Research, 2007, 177(3): 2033-2049
[14] RODRIGUEZ F, LOZANO M, BLUM C, et al. An iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problem[J]. Computers & Operations Research, 2013, 40(7): 1829-1841
[15] FRAMINAN J M, LEISTEN R, RAJENDRAN C. Different initial sequences for the heuristic of NAWAZ, ENSCORE and HAM to minimize makespan, idletime or flowtime in the static permutation flowshop sequencing problem[J]. International Journal of Production Research, 2003, 41(1): 121-148
[16] HOLLAND J H. Adaptation in natural and artificial systems[M]. Boston, USA: MIT Press, 1992.
[17] 王凌. 车间调度及其遗传算法[M]. 北京: 清华大学出版社, 2003.
[18] DURASEVIC M, JAKOBOVIC D. A survey of dispatching rules for the dynamic unrelated machines environment[J]. Expert Systems with Applications, 2018, 113: 555-569

求解一类无关并行机调度的遗传迭代贪心算法

A Genetic Algorithm-Iterative Greedy Algorithm for a Kind of Unrelated Parallel Machine Scheduling Problem

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[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): 141-147.
[5]	王冰怡, 张锦. 考虑网点共享与变更的多级快递网点选址问题[J]. 工业工程, 2021, 24(2): 155-165.
[6]	马跃如, 文铮, 易丹. 考虑老年人满意度的多目标居家养老护理员路径优化[J]. 工业工程, 2021, 24(1): 74-81,103.
[7]	王玖河, 高辉, 刘欢. 基于遗传算法的共享助力车调度问题研究[J]. 工业工程, 2021, 24(1): 90-96.
[8]	吴斌, 宋琰, 程晶, 董敏. 基于密度峰值聚类的VRPTW问题研究[J]. 工业工程, 2020, 23(5): 58-66,74.
[9]	王苏林, 邱菲尔, 陈凡, 刘川昆, 鹿腾, 王芷芸. 基于贪心遗传的地下物流节点选择规划研究[J]. 工业工程, 2020, 23(5): 88-95.
[10]	侯艳, 黄康焕, 张亿仙, 伍乃骐. 原油一次加工过程的多目标调度优化[J]. 工业工程, 2020, 23(4): 131-139.
[11]	王泽, 杨信丰, 刘兰芬. 考虑电量消耗的车辆调度优化研究[J]. 工业工程, 2020, 23(4): 140-147.
[12]	曾垂飞, 刘建军, 陈庆新, 毛宁. 装配作业车间分批调度问题的算法对比[J]. 工业工程, 2020, 23(4): 174-182.
[13]	张巍, 李鹏翔, 仝自强, 岳毅蒙. 基于损坏车辆分布预测与损益阈值分析下的共享单车回收研究[J]. 工业工程, 2020, 23(3): 132-137.
[14]	张国辉, 胡一凡, 孙靖贺. 改进遗传算法求解多时间约束的柔性作业车间调度问题[J]. 工业工程, 2020, 23(2): 19-25,48.
[15]	李腾, 冯珊. 面向“货到人”拣选系统的一种随机调度策略[J]. 工业工程, 2020, 23(2): 59-66.