面向医疗器械企业灭菌工艺的不同容量平行机批调度

doi:10.3969/j.issn.1007-7375.2021.01.011

摘要/Abstract

摘要： 针对医疗器械企业灭菌工艺生产过程的调度问题，提出面向灭菌工艺的不同容量平行机批调度方法，建立以最小化总延迟时长、最小化总加工能耗和最大化灭菌柜装载率为目标的不同容量平行机批调度模型。并针对模型的求解提出一种改进的NSGA-III算法(Improved NSGA-III，INSGA-III)。为了获得更高质量的批调度解，采用EDT+MLC启发式规则生成INSGA-III初始种群，并设计一种局部搜索策略以改进算法迭代后期的搜索能力。最后，通过算例仿真与传统调度方法进行对比分析，验证了该模型和算法的有效性和可行性。结果表明，该模型和算法较传统调度方法有明显的优势，可为医疗企业实际生产调度提供新思路。

关键词: 灭菌工艺, 不同容量平行机, 多目标优化, NSGA-III算法

Abstract: Aiming at the scheduling problem of sterilization process in medical equipment enterprises, a batch scheduling method of parallel machines with different capacities for sterilization process was proposed, and a batch scheduling model of parallel machines with different capacities was established, which aims to minimize the total delay time, minimize the total processing energy consumption and maximize the loading rate of sterilization cabinet. An improved NSGA-III algorithm was proposed to solve the model. In order to obtain a higher quality batch scheduling solution, EDT+MLC heuristic rules were used to generate the initial population in INSGA-III, and a local search strategy was designed to improve the search capability of the algorithm at the later stage of iteration. Finally, in order to verify the effectiveness and feasibility of the model and method, a comparative analysis was conducted between the simulation and the traditional scheduling method, and the results show that the model and algorithm have obvious advantages over the traditional scheduling method, which can provide a new idea for the actual production scheduling of medical enterprises.

Key words: sterilization process, parallel machine with different capacity, multi-objective optimization, NSGA-III

中图分类号:

TP301

刘雪红, 张涛, 彭兆, 王磊. 面向医疗器械企业灭菌工艺的不同容量平行机批调度[J]. 工业工程, 2021, 24(1): 82-89.

LIU Xuehong, ZHANG Tao, PENG Zhao, WANG Lei. Batch Scheduling of Parallel Machines with Different Capacity for Sterilization Process in Medical Equipment Enterprises[J]. Industrial Engineering Journal, 2021, 24(1): 82-89.

参考文献

[1] 刘建军, 陈庆新, 毛宁. 基于滚动调度的模具热处理车间负荷控制算法[J]. 机械工程学报, 2010, 46(20): 125-133
LIU Jianjun, CHEN Qingxin, MAO Ning. Rolling-scheduling-based workload control for mould heat-treatment shop floor[J]. Journal of Mechanical Engineering, 2010, 46(20): 125-133
[2] 贾兆红, 李晓浩, 温婷婷, 等. 不同容量平行机下差异工件尺寸的批调度算法[J]. 控制与决策, 2015, 30(12): 2145-2152
JIA Zhaohong, LI Xiaohao, WEN Tingting, et al. Algorithms for scheduling on parallel batch machines with non-identical capacities and non-identical job sizes[J]. Control and Decision, 2015, 30(12): 2145-2152
[3] DAMODARAN P, CHANG P. Heuristics to minimize makespan of parallel batch processing machines[J]. The International Journal of Advanced Manufacturing Technology, 2008, 37: 1005-1013
[4] CHEN H, DU B, HUANG G Q. Metaheuristics to minimise makespan on parallel batch processing machines with dynamic job arrivals[J]. International Journal of Computer Integrated Manufacturing, 2010, 23(10): 942-956
[5] WANG H, CHOU F. Solving the parallel batch-processing machines with different release times, job sizes, and capacity limits by metaheuristics[J]. Expert Systems with Applications, 2010, 37(2): 1510-1521
[6] 李小林, 杜冰, 许瑞, 等. 同类机环境下不同尺寸工件的分批调度问题[J]. 计算机集成制造系统, 2012, 18(1): 102-110
LI Xiaolin, DU Bing, XU Rui, et al. Batch scheduling on uniform parallel machines with non-identical job sizes[J]. Computer Integrated Manufacturing Systems, 2012, 18(1): 102-110
[7] 刘建军, 陈庆新, 毛宁, 等. 事件驱动的并行多机模具热处理生产调度[J]. 计算机集成制造系统, 2015, 21(4): 1013-1022
LIU Jianjun, CHEN Qingxin, MAO Ning, et al. Event-drivernmould heat-treatment production scheduling with parallel batch processors[J]. Computer Integrated Manufacturing Systems, 2015, 21(4): 1013-1022
[8] LI Z, YANG H, ZHANG S, et al. Unrelated parallel machine scheduling problem with energy and tardiness cost[J]. The International Journal of Advanced Manufacturing Technology, 2016, 84: 213-226
[9] 李国臣, 乔非, 王俊凯, 等. 考虑能耗约束的并行机组批调度[J]. 中南大学学报(自然科学版), 2017, 48(8): 2063-2072
LI Guochen, QIAO Fei, WANG Junkai, et al. Parallel machine batching scheduling considering energy constraints[J]. Journal of Central South University (Science and Technology), 2017, 48(8): 2063-2072
[10] 雷德明, 潘子肖, 张清勇. 多目标低碳并行机调度研究[J]. 华中科技大学学报(自然科学版), 2018, 46(8): 104-109
LEI Deming, PAN Zixiao, ZHANG Qingyong. Researches on multi-objective low carbon parallel machines scheduling[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2018, 46(8): 104-109
[11] DAMODARAN P, DIYADAWAGAMAGE D A, GHRAYEB O, et al. A particle swarm optimization algorithm for minimizing makespan of nonidentical parallel batch processing machines[J]. International Journal of Advanced Manufacturing Technology, 2012, 58: 1131-1140
[12] ZHOU S, LIU M, CHEN H, et al. An effective discrete differential evolution algorithm for scheduling uniform parallel batch processing machines with non-identical capacities and arbitrary job sizes[J]. International Journal of Production Economics, 2016: 1-11
[13] JIA Z, LI X, LEUNG J Y T. Minimizing makespan for arbitrary size jobs with release times on P-batch machines with arbitrary capacities[J]. Future Generation Computer Systems, 2017, 67: 22-34
[14] 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(1): 287-326
[15] UZSOY R. Scheduling a single batch processing machine with non-identical job sizes[J]. International Journal of Production Research, 1994, 32(7): 1615-1635
[16] DEB K, JAIN H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(4): 577-601
[17] JAIN H, DEB K. An evolutionary many-objective optimization algorithm using reference-point based non-dominated sorting approach, part II: handling constraints and extending to an adaptive approach[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(4): 602-622
[18] 陈立鹏. 基于NSGA-III改进的动态多目标优化算法及其应用[D]. 沈阳: 东北大学, 2015.
CHEN Lipeng. An improved dynamic multiobjective optimization algorithm based on NSGA-III and it's application[D]. Shenyang: Northeastern University, 2015.
[19] 袁源. 基于分解的多目标进化算法及其应用[D]. 北京: 清华大学, 2015.
YUAN Yuan. Decomposition-based multi-objective evolutionary algorithms and their applications[D]. Beijing: Tsinghua University, 2015.
[20] 付亚平, 黄敏, 王洪峰, 等. 混合并行机调度问题的多目标优化模型及算法[J]. 控制理论与应用, 2014, 31(11): 1510-1516
FU Yaping, HUANG Min, WANG Hongfeng, et al. Multi-objective optimization model and algorithm for hybrid parallel machine scheduling problem[J]. Control Theory & Applications, 2014, 31(11): 1510-1516
[21] PINEDO M, HADAVI K. Scheduling: theory, algorithms, and systems[J]. IIE Transactions, 1996, 28(8): 695-697