带准备时间的异构并行机调度规则自动设计方法

doi:10.3969/j.issn.1007-7375.220061

工业工程 ›› 2024, Vol. 27 ›› Issue (2): 87-97.doi: 10.3969/j.issn.1007-7375.220061

• 工业互联与制造服务管理 • 上一篇下一篇

带准备时间的异构并行机调度规则自动设计方法

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

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

收稿日期:2022-04-22 发布日期:2024-04-29
作者简介:钟宏扬(1993-),男,江西省人,博士研究生,主要研究方向为生产计划与控制、车间动态调度等
基金资助:
国家自然科学基金资助项目 (51975129, 61973089)；广东省自然科学基金资助项目 (2019A1515012158)

Automatic Designing of Scheduling Rules for Heterogenous Parallel Machines with Setup Time

ZHONG Hongyang, LIU Jianjun, ZENG Chuangfeng, CHEN Qingxin, MAO Ning

Key Laboratory of Computer Integrated Manufacturing System of Guangdong Province, Guangdong University of Technology, Guangzhou 510006, China

Received:2022-04-22 Published:2024-04-29

摘要/Abstract

摘要： 以大规模定制化的家电行业生产为背景，将家电总装产线的投产排序决策抽象成为一类带准备时间的异构并行机动态调度问题。针对人工调度规则解决动态调度问题简单高效，但场景适应性弱的特点，引入了基于遗传规划 (genetic programming, GP) 的规则自动设计框架。首先，通过分析家电总装产线生产特征以及优化需求，以最小化平均拖期为优化目标，建立异构并行机调度模型；随后，针对问题特征，构建线体指派-工单排序规则对协同进化的改进型GP算法，并提取线体、工单的特征属性输入GP算法框架以自动设计调度规则。最后，基于某家电企业实际案例数据设计大量算例测试集，通过对比GP算法与人工设计规则在差异化工况场景的实验结果，验证GP算法有效性，并进一步分析了GP算法构造规则受不同生产环境参数的影响。

关键词: 异构并行机, 动态调度, 启发式规则, 遗传规划

Abstract: Taking massive customized production of home appliance as the research background, the scheduling of home appliance manufacturing is abstracted as a problem of dynamic heterogenous parallel machine scheduling with sequence-dependent setup time (HPMS-SST). Manual scheduling rules are simple and efficient in solving dynamic scheduling problems, but their adaptability to different scenarios is weak. To this end, an automatic design framework for rules based on genetic programming (GP) is introduced. First, by analyzing the features and optimization requirements of home appliance production, a model of HPMS-SST is established with the objective of minimizing the mean product tardiness. Subsequently, based on the characteristics of this problem, an improved GP algorithm is proposed for the coevolution of machine assignment and queue sequencing rules; Also, the feature attributes of machines and orders are extracted and input into the GP algorithm framework to automatically design scheduling rules; Finally, a number of test cases are generated from the real production data of a home appliance manufacturer. By comparing the experimental results of the proposed algorithm and manual designed rules in various conditions, the effectiveness of the GP algorithm is verified. Besides, sensitive analysis is conducted to evaluate the influence of parameters for different production conditions on the generated GP-based rules.

Key words: heterogenous parallel machines, dynamic scheduling, heuristic rules, genetic programming

中图分类号:

F406

钟宏扬, 刘建军, 曾创锋, 陈庆新, 毛宁. 带准备时间的异构并行机调度规则自动设计方法[J]. 工业工程, 2024, 27(2): 87-97.

ZHONG Hongyang, LIU Jianjun, ZENG Chuangfeng, CHEN Qingxin, MAO Ning. Automatic Designing of Scheduling Rules for Heterogenous Parallel Machines with Setup Time[J]. Industrial Engineering Journal, 2024, 27(2): 87-97.

参考文献

[1] ZHOU J, LI P, ZHOU Y, et al. Toward new-generation intelligent manufacturing[J]. Engineering, 2018, 4(4): 11-20
[2] BOZORGIRAD M A, LOGENDRAN R. Sequence-dependent group scheduling problem on unrelated-parallel machines[J]. Expert Systems with Applications., 2012, 39(10): 9021-9030
[3] WANG W, WANG H, ZHAO Y, et al. Parallel machine scheduling with splitting jobs by a hybrid differential evolution algorithm[J]. Computers & Operations Research, 2013, 40(5): 1196-1206
[4] 唐万和, 杨海东, 黎展滔, 等. 考虑能耗成本和拖期成本的非同等并行机调度[J]. 软件, 2014, 35(3): 52-57
TANG Wanhe, YANG Haidong, LI Zhantao, et al. Non-identical parallel machine scheduling problem with energy and tardiness cost[J]. Software, 2014, 35(3): 52-57
[5] LEE J Y, KIM Y D. A branch and bound algorithm to minimize total tardiness of jobs in a two identical-parallel-machine scheduling problem with a machine availability constraint[J]. Journal of the Operational Research Society, 2015, 66(9): 1542-1554
[6] 吴楚格, 王凌, 郑晓龙. 求解不相关并行机调度的一种自适应分布估计算法[J]. 控制与决策, 2016, 31(12): 2177-2182
WU Chuge, WANG Ling, ZHENG Xiaolong. An adaptive estimation of distribution algorithm for solving the unrelated parallel machine scheduling[J]. Control and Decision, 2016, 31(12): 2177-2182
[7] LI N, GAO L, LI P, et al. A GEP-based reactive scheduling policies constructing approach for dynamic flexible job shop scheduling problem with job release dates[J]. Journal of Intelligent Manufacturing, 2013, 24(4): 763-774
[8] 杨小佳, 刘建军, 陈庆新, 等. 变扰动强度下柔性装配作业车间调度性能分析[J]. 计算机集成制造系统, 2021, 27(3): 800-814
YANG Xiaojia, LIU Jianjun, CHEN Qingxin, et al. Performance analysis of flexible assembly job shop scheduling under variable disturbance intensity[J]. Computer Integrated Manufacturing Systems, 2021, 27(3): 800-814
[9] 吴秀丽, 孙琳. 智能制造系统基于数据驱动的车间实时调度[J]. 控制与决策, 2020, 35(3): 523-535
WU Xiuli, SUN Lin. Data-based real-time scheduling in smart manufacturing[J]. Control and Decision, 2020, 35(3): 523-535
[10] NGUYEN S, MEI Y, ZHANGg M. Genetic programming for production scheduling: a survey with a unified framework[J]. Complex & Intelligent Systems, 2017(3): 41-66
[11] 范华丽, 熊禾根, 蒋国璋, 等. 基于遗传规划的动态作业车间调度规则生成[J]. 计算机集成制造系统, 2018, 24(4): 876-885
FAN Huali, XIONG Hegen, JIANG Guozhang, et al. Generation of dispatching rules for dynamic jop shop scheduling problem based on genetic programming algorithm[J]. Computer Integrated Manufacturing Systems, 2018, 24(4): 876-885
[12] 马丽萌, 乔非, 马玉敏, 等. 基于SO-GP的智能车间组合调度规则挖掘[J]. 计算机集成制造系统, 2021, 27 (5) : 1351-1360.
MA Limeng, QIAO Fei, MA Yumin, et al. Mining of composite dispatching rules for smart workshop based on SO-GP[J]. Computer Integrated Manufacturing Systems, 2021, 27 (5) : 1351-1360.
[13] 张苏雨, 王艳, 纪志成. 基于超启发式遗传规划的动态车间调度方法[J]. 系统仿真学报, 2020, 32(12): 2494-2506
ZHANG Suyu, WANG Yan, JI Zhicheng. Automatic discovery method of dynamic jop shop dispatching rules based on hype-heuristic genetic programming[J]. Journal of System Simulation, 2020, 32(12): 2494-2506
[14] BRANKE J, NGUYEN S, PICKARDT C W, et al. Automated design of production scheduling heuristics: a review[J]. IEEE Transactions on Evolutionary Computation, 2016, 20(1): 110-124
[15] DURASEVIC M, JAKOBOVIC D. A survey of dispatching rules for the dynamic unrelated machines environment[J]. Expert Systems with Applications, 2018, 113: 555-569
[16] D. H. Wolpert, W. G. Macready. No free lunch theorems for optimization[J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1): 67-82

带准备时间的异构并行机调度规则自动设计方法

Automatic Designing of Scheduling Rules for Heterogenous Parallel Machines with Setup Time

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

本文评价

[1]	秦红斌, 孔仁杰, 常永顺, 李晨晓. 基于混合平衡优化器算法的多目标柔性作业车间多重动态调度研究[J]. 工业工程, 2023, 26(5): 78-88.
[2]	彭乘风, 黎展滔, 陈庆新, 赖辉辉. 复杂型面智能生产单元任务−刀具联合动态调度策略[J]. 工业工程, 2023, 26(1): 170-181.
[3]	鄢敏杰, 王小明, 朱松平, 陈庆新, 毛宁. 面向印制电路板钻孔任务动态调度的短视策略[J]. 工业工程, 2021, 24(6): 18-24,56.
[4]	张国晨, 孙超利, 石慧, 李晓波. 结合车辆日检的混凝土罐车调度问题研究[J]. 工业工程, 2020, 23(2): 67-75.
[5]	吴正佳, 涂晶鑫, 华露, 白炜铖, 刘秀凤. 基于本体案例匹配的扰动作业车间智能调度辅助决策[J]. 工业工程, 2018, 21(6): 7-15,22.
[6]	帅旗1，2, 姚锡凡2. 面向柔性作业调度问题的启发性规则改进遗传算法[J]. 工业工程, 2013, 16(1): 31-37.