IMODE Algorithm for Solving Cigarette Product Production Scheduling Problems Based on Lot-size Splitting Mechanism

doi:10.3969/j.issn.1004-132X.2025.08.024

Abstract

Abstract:

To address the production scheduling problem of cigarette products， the tobacco packing workshop responsible for the production tasks was taken as the research object， considering the actual production conditions of cigarette enterprises. This problem was transformed into a unrelated parallel machines lot-size scheduling problems. An optimization model was established to simulate the production conditions of cigarette products， with the total number of switches of tobacco packing machines and the comprehensive evaluation time of simultaneous stoppage as the objectives. An improved multi-objective differential evolution （IMODE） algorithm was designed to solve the problems based on a lot-size splitting mechanism. To accommodate lot-size production characteristics， the algorithm used an irregular matrix encoding method to represent feasible solutions， generated the initial population based on a reverse lot-size learning strategy， updated population individuals through differential operations between matrix vectors， and performed detailed neighborhood searches of the child individuals by splitting lot-size into smaller ones， an improved elitism retention strategy was introduced during the selection processes to enhance the algorithm's optimization capability. Finally， experiments based on production instances of cigarette enterprises of different orders and workshop scales demonstrate the performance of IMODE and the effectiveness in solving the scheduling problems of cigarette products production.

Key words: unrelated parallel machine, lot-size splitting, total number of switches, comprehensive evaluation time of simultaneous stoppage, multi-objects differential evolution （MODE）algorithm

摘要：

针对成品卷烟生产调度问题，结合卷烟企业生产实际，以承担成品卷烟生产任务的卷包车间为研究对象，将其转换为异构并行机分批调度问题，以卷包机组的总切换次数和同停综合评价时间为目标建立符合成品卷烟生产工况的仿真优化模型，并设计一种基于批次拆分机制的改进多目标差分进化（IMODE）算法进行求解。为满足分批生产特点，该算法采用一种不规则的矩阵编码方式表示可行解，基于反向批次学习策略生成初始种群，通过矩阵向量间的差分运算更新种群个体，采用批次拆分机制详细划分批次批量，并对子代个体进行邻域搜索，在选择操作中引入改进精英保留策略，以提高算法的寻优能力。最后基于不同订单量和车间规模的卷烟企业生产实例进行实验对比，验证了IMODE算法的性能及其在解决成品卷烟生产调度问题上的有效性。

关键词: 异构并行机, 批次拆分, 总切换次数, 同停综合评价时间, 多目标差分进化算法

CLC Number:

TS452

Yuqiang AN, Yuan ZHANG, Ping ZOU, Yifei TAO. IMODE Algorithm for Solving Cigarette Product Production Scheduling Problems Based on Lot-size Splitting Mechanism[J]. China Mechanical Engineering, 2025, 36(8): 1893-1903.

安裕强, 张源, 邹平, 陶翼飞. 基于批次拆分机制的IMODE算法求解成品卷烟生产调度问题[J]. 中国机械工程, 2025, 36(8): 1893-1903.

Figures/Tables 16

References 31

[1]	欧阳世波，张淼寒，谢俊明，等. 计及多目标约束的成品卷烟销售订单配送调度优化［J］. 中国烟草学报， 2024， 30（2）： 80-91.
	OUYANG Shibo， ZHANG Miaohan， XIE Junming， et al. Optimization of Multi-objective Constrained Distribution Scheduling of Finished Cigarette Sales Orders［J］. Acta Tabacaria Sinica， 2024， 30（2）： 80-91.
[2]	GAO Mengxing， LIU Chenguang， LIU Zigui， et al. A Tabu Search Algorithm for the Unrelated Parallel Machine Scheduling Problem with Varied Carbon Emission Constraints in Different Time Intervals［J］. Journal of the Operational Research Society， 2024， 75（6）： 1111-1125.
[3]	李丹，周延辉，周明，等. 基于遗传算法的卷烟换牌排产与优化设计［J］. 烟草科技， 2019， 52（5）： 94-99.
	LI Dan， ZHOU Yanhui， ZHOU Ming， et al. Scheduling of Cigarette Brand Change and Its Optimization Based on Genetic Algorithm［J］. Tobacco Science & Technology， 2019， 52（5）： 94-99.
[4]	郑堃，练志伟，顾新艳，等. 采用改进两点交叉算子的改进自适应遗传算法求解不相关并行机混合流水车间调度问题［J］. 中国机械工程， 2023， 34（14）： 1647-1658.
	ZHENG Kun， LIAN Zhiwei， GU Xinyan， et al. Hybrid Flow Shop Scheduling Problems with Unrelated Parallel Machine Solved by Improved Adaptive Genetic Algorithm（IAGA） with ITPX［J］. China Mechanical Engineering， 2023， 34（14）： 1647-1658.
[5]	金剑，金钊，祁跃东. 卷烟生产计划排产模型建立与优化［J］. 计算机工程与应用， 2013， 49（18）： 253-259.
	JIN Jian， JIN Zhao， QI Yuedong. Cigarette Production Scheduling Modeling and Optimization［J］. Computer Engineering and Applications， 2013， 49（18）： 253-259.
[6]	沈倩，管在林，张正敏，等. 面向卷烟生产调度的集成产能过滤算法与仿真技术的优化框架［J］. 计算机集成制造系统， 2022， 28（5）： 1462-1471.
	SHEN Qian， GUAN Zailin， ZHANG Zhengmin， et al. Optimization Framework Based on Simulation Integrated Capacity Filtering Algorithm for Cigarette Production Scheduling［J］. Computer Integrated Manufacturing Systems， 2022， 28（5）： 1462-1471.
[7]	柴剑彬，刘赫，贝晓强. 考虑机器调整次数和产品质量的卷烟批量计划和柔性流水车间调度集成问题［J］. 运筹与管理， 2019， 28（10）： 165-174.
	CHAI Jianbin， LIU He， BEI Xiaoqiang. Integrated Problem for Lot Sizing and Flexible Flow Shop Scheduling Problem in the Tobacco Industry Considering Setup Times and Cigarette Quality［J］. Operations Research and Management Science， 2019， 28（10）： 165-174.
[8]	王伟玲，王晶. 卷烟多目标柔性流水调度问题［J］. 机械设计与研究， 2014， 30（3）： 97-99.
	WANG Weiling， WANG Jing. Study on Scheduling Problem Multi-objective Flexible Flow Ling for of Cigarette［J］. Machine Design & Research， 2014， 30（3）： 97-99.
[9]	荀洪凯，陶翼飞，张源，等. 多目标启发式狼群算法求解不相关并行机分批调度问题［J］. 信息与控制， 2023， 52（1）： 93-103.
	XUN Hongkai， TAO Yifei， ZHANG Yuan， et al. Multi-objective Heuristic Wolf Pack Algorithm for Unrelated Parallel Machine Batch Scheduling Problem［J］. Information and Control， 2023， 52（1）： 93-103.
[10]	KORDMOSTAFAPOUR A， REZAEIAN J， MAHDAVI I， et al. Scheduling Unrelated Parallel Machine Problem with Multi-mode Processing Times and Batch Delivery Cost［J］. OPSEARCH， 2022， 59（4）： 1438-1470.
[11]	TREMBLET D， THEVENIN S， DOLGUI A. Makespan Estimation in a Flexible Job-shop Scheduling Environment Using Machine Learning［J］. International Journal of Production Research， 2024， 62（10）： 3654-3670.
[12]	朱颖颖，吴正佳，唐秋华，等. 批次受限的双目标并行机等量分批调度［J］. 计算机集成制造系统， 2022， 28（11）： 3379-3390.
	ZHU Yingying， WU Zhengjia， TANG Qiuhua， et al. Bi-objective Parallel Machine Equally Lot-sizing and Scheduling Problem under Limited Number of Sublots［J］. Computer Integrated Manufacturing Systems， 2022， 28（11）： 3379-3390.
[13]	EREMEEV A V， KOVALYOV M Y， KUZNET-SOV P M. Lot-size Scheduling of a Single Product on Unrelated Parallel Machines［J］. Optimization Letters， 2020， 14（3）： 557-568.
[14]	宋君乐，陶翼飞，可晓东，等. 分区编码HBGWO算法求解并行机分批调度问题［J］. 机械设计， 2022， 39（10）： 48-59.
	SONG Junle， TAO Yifei， KE Xiaodong， et al. Partition-encoding HBGWO Algorithm for Lot-sizing Scheduling Problem of Unrelated Parallel Machines［J］. Journal of Machine Design， 2022， 39（10）： 48-59.
[15]	刘东洋，余军合，战洪飞，等. 基于改进双层遗传算法的模块化批量装配生产分批调度［J］. 机械制造， 2023， 61（6）： 84-91.
	LIU Dongyang， YU Junhe， ZHAN Hongfei， et al. Modular Batch Assembly Production Scheduling Based on Improved Bi-level Genetic Algorithm［J］. Machinery， 2023， 61（6）： 84-91.
[16]	谢法吾，李玲玲，李丽，等. 基于多目标混合进化算法的作业车间混排可变分批节能调度方法［J］. 中国机械工程， 2023， 34（13）： 1576-1588.
	XIE Fawu， LI Lingling， LI Li， et al. Energy-efficient Job Shop Scheduling with Variable Lot Splitting and Sublots Intermingling Based on Multi-objective Hybrid Evolutionary Algorithm［J］. China Mechanical Engineering， 2023， 34（13）： 1576-1588.
[17]	FALLAHI A， SHAHIDI-ZADEH B， NIAKI S T A. Unrelated Parallel Batch Processing Machine Scheduling for Production Systems under Carbon Reduction Policies： NSGA-II and MOGWO Metaheuristics［J］. Soft Computing， 2023， 27（22）： 17063-17091.
[18]	魏书鹏，唐红涛，李西兴，等. 考虑双资源约束的柔性机械加工车间逆调度问题研究［J］. 中国机械工程， 2024， 35（3）： 457-471.
	WEI Shupeng， TANG Hongtao， LI Xixing， et al. Dual-resource Constrained Flexible Machining Workshop Inverse Scheduling Problem［J］. China Mechanical Engineering， 2024， 35（3）： 457-471.
[19]	WANG Tianyu， CAI Changbing， GAO Yulei， et al. Adaptive Online Learning for System Identification and In-advance Optimization under Long Feedback Delay and Concept Drift in Cigarette Production［J］. Drying Technology， 2022， 40（15）： 3340-3356.
[20]	ZHAO Fuqing， ZHANG Hui， WANG Ling， et al. A Multi-objective Discrete Differential Evolution Algorithm for Energy-efficient Distributed Blocking Flow Shop Scheduling Problem［J］. International Journal of Production Research， 2024， 62（12）： 4226-4244.
[21]	SINGH M K， VERMA Y K. Refraction Reverse Learning Based Hybrid Namib Antenna Beetle Optimization for Resource Allocation in NB-IoT Platform［J］. Multimedia Tools and Applications， 2024， 83（18）： 53687-53713.
[22]	HOSSEINI S E， KARIMI O， MALI ASEMANBAKH-SH. Experimental Investigation and Multi-objective Optimization of Savonius Wind Turbine Based on Modified Non-dominated Sorting Genetic Algorithm-II［J］. Wind Engineering， 2024， 48（3）： 446-467.
[23]	HARIZAN S， KUILA P， KUMAR A， et al. Multi-objective Evolutionary Algorithms for Coverage and Connectivity Aware Relay Node Placement in Cluster-based Wireless Sensor Networks［J］. Wireless Personal Communications， 2024， 135（2）： 979-1008.
[24]	BRAUN M， SHUKLA P. On Cone-based Decompositions of Proper Pareto-optimality in Multi-objective Optimization［J］. European Journal of Operational Research， 2024， 317（2）： 592-602.
[25]	HAGHGOEI A， IRAJPOUR A， HAMIDI N. A Multi-objective Optimization Model of Truck Scheduling Problem Using Cross-dock in Supply Chain Management： NSGA-II and NRGA［J］. Journal of Modelling in Management， 2024， 19（4）： 1155-1179.
[26]	KABIRI E， MAFTOUNI N. Multiple Objective Energy Optimization of a Trade Center Building Based on Genetic Algorithm Using Ecological Materials［J］. Scientific Reports， 2024， 14： 9366.
[27]	CUI Hanghao， LI Xinyu， GAO Liang， et al. Multi-population Genetic Algorithm with Greedy Job Insertion Inter-factory Neighbourhoods for Multi-objective Distributed Hybrid Flow-shop Scheduling with Unrelated-parallel Machines Considering Tardiness［J］. International Journal of Production Research， 2024， 62（12）： 4427-4445.
[28]	何文婕，许玉江，闫浩峰，等. 一种面向卷烟混合生产线的优化调度模型研究［J］. 包装工程， 2022， 43（17）： 298-307.
	HE Wenjie， XU Yujiang， YAN Haofeng， et al. Optimization Scheduling Model for Hybrid Production Line of Cigarette［J］. Packaging Engineering， 2022， 43（17）： 298-307.
[29]	张源，陶翼飞，王加冕. 改进差分进化算法求解混合流水车间调度问题［J］. 中国机械工程， 2021， 32（6）： 714-720.
	ZHANG Yuan， TAO Yifei， WANG Jiamian. An Improved DE Algorithm for Solving Hybrid Flow-shop Scheduling Problems［J］. China Mechanical Engineering， 2021， 32（6）： 714-720.
[30]	NIU Wei， LI Junqing， JIN Hui， et al. Bi-objective Optimization Using an Improved NSGA-II for Energy-efficient Scheduling of a Distributed Assembly Blocking Flowshop［J］. Engineering Optimization， 2023， 55（5）： 719-740.
[31]	何李，陶翼飞，罗俊斌，等. 基于两阶段狼群算法的自动化立体仓库作业集成优化［J］. 中国机械工程， 2022， 33（21）： 2538-2546.
	HE Li， TAO Yifei， LUO Junbin， et al. Job Integrated Optimization of Automated Storage/Retrieval Systems Based on Two-stage Wolf Pack Algorithm［J］. China Mechanical Engineering， 2022， 33（21）： 2538-2546.

	N1	N2	N3	N4	N5	N6	N7	N8	N9	N10
M1	√	×	×	×	×	×	×	×	×	×
M2	√	×	×	×	×	×	×	×	×	×
M3	√	×	×	×	×	×	×	×	×	×
M4	√	×	×	×	×	×	×	×	×	×
M5	√	×	×	×	√	×	×	×	×	×
M6	√	×	×	×	√	×	×	×	×	×
M7	√	×	×	×	√	×	×	×	×	×
M8	√	×	×	×	√	×	×	×	×	×
M9	√	×	×	×	√	×	×	×	×	×
M10	√	×	×	×	√	×	×	×	×	×
M11	√	×	×	×	√	×	×	×	×	×
M12	×	√	×	×	×	×	×	×	×	×
M13	×	√	×	×	×	×	×	×	×	×
M14	×	√	×	×	×	×	×	×	×	×
M15	×	√	×	×	×	×	×	×	×	×
M16	×	√	×	×	×	×	×	×	×	×
M17	×	√	×	×	×	×	×	×	×	×
M18	×	√	×	×	×	×	×	×	×	×
M19	×	√	×	×	×	×	×	×	×	×
M20	×	√	×	×	×	×	×	×	×	×
M21	×	√	×	×	×	×	×	×	×	×
M22	×	√	×	×	×	×	×	×	×	×
M23	×	√	×	×	×	√	×	×	√	×
M24	×	√	×	√	×	√	×	√	√	×
M25	×	√	×	×	×	√	×	×	√	×
M26	×	√	√	√	×	×	×	√	×	×
M27	×	×	×	×	×	×	√	×	×	√

	N1	N2	N3	N4	N5	N6	N7	N8	N9	N10
M1	√	×	×	×	×	×	×	×	×	×
M2	√	×	×	×	×	×	×	×	×	×
M3	√	×	×	×	×	×	×	×	×	×
M4	√	×	×	×	×	×	×	×	×	×
M5	√	×	×	×	√	×	×	×	×	×
M6	√	×	×	×	√	×	×	×	×	×
M7	√	×	×	×	√	×	×	×	×	×
M8	√	×	×	×	√	×	×	×	×	×
M9	√	×	×	×	√	×	×	×	×	×
M10	√	×	×	×	√	×	×	×	×	×
M11	√	×	×	×	√	×	×	×	×	×
M12	×	√	×	×	×	×	×	×	×	×
M13	×	√	×	×	×	×	×	×	×	×
M14	×	√	×	×	×	×	×	×	×	×
M15	×	√	×	×	×	×	×	×	×	×
M16	×	√	×	×	×	×	×	×	×	×
M17	×	√	×	×	×	×	×	×	×	×
M18	×	√	×	×	×	×	×	×	×	×
M19	×	√	×	×	×	×	×	×	×	×
M20	×	√	×	×	×	×	×	×	×	×
M21	×	√	×	×	×	×	×	×	×	×
M22	×	√	×	×	×	×	×	×	×	×
M23	×	√	×	×	×	√	×	×	√	×
M24	×	√	×	√	×	√	×	√	√	×
M25	×	√	×	×	×	√	×	×	√	×
M26	×	√	√	√	×	×	×	√	×	×
M27	×	×	×	×	×	×	√	×	×	√

组合	F	CR	L_min	平均值（HV）
1	0.1	0.3	3	0.477
2	0.1	0.5	5	0.482
3	0.1	0.6	8	0.475
4	0.5	0.3	5	0.549
5	0.5	0.5	8	0.507
6	0.5	0.6	3	0.516
7	0.9	0.3	8	0.489
8	0.9	0.5	3	0.493
9	0.9	0.6	5	0.501

组合	F	CR	L_min	平均值（HV）
1	0.1	0.3	3	0.477
2	0.1	0.5	5	0.482
3	0.1	0.6	8	0.475
4	0.5	0.3	5	0.549
5	0.5	0.5	8	0.507
6	0.5	0.6	3	0.516
7	0.9	0.3	8	0.489
8	0.9	0.5	3	0.493
9	0.9	0.6	5	0.501

订单类型	规模	NSGA-II			MOWPA			MODE			IMODE
订单类型	规模	NS	IGD	HV	NS	IGD	HV	NS	IGD	HV	NS	IGD	HV
A类	小	4	0.234	0.315	4	0.106	0.378	4	0.138	0.351	4	0.095	0.543
	中	5	0.1	0.503	5	0.068	0.465	5	0.072	0.446	5	0.069	0.549
	大	5	0.071	0.37	6	0.036	0.455	6	0.076	0.327	6	0.036	0.471
B类	小	3	0.081	0.551	3	0.091	0.552	4	0.086	0.497	3	0.075	0.553
	中	2	0.306	0.285	4	0.083	0.359	4	0.06	0.395	4	0.034	0.397
	大	4	0.305	0.316	5	0.133	0.344	3	0.169	0.289	5	0.087	0.413
C类	小	3	0.11	0.314	5	0.106	0.416	4	0.125	0.355	4	0.069	0.421
	中	4	0.364	0.377	4	0.099	0.442	5	0.063	0.356	5	0.037	0.502
	大	5	0.269	0.317	6	0.081	0.491	6	0.144	0.371	6	0.079	0.489
	均值	3.89	0.204	0.372	4.67	0.089	0.434	4.56	0.104	0.376	4.67	0.065	0.482