多目标下航天产品生产车间柔性资源配置与调度集成优化

doi:10.16381/j.cnki.issn1003-207x.2021.1831

摘要/Abstract

摘要：

航天产品的生产具有多品种、小批量特点，根据生产计划进行柔性资源配置与调度，对生产效率和响应能力都有重要影响。考虑了生产资源投入量可变、生产中存在准备加工运输等多种时间、生产资源性能差异等情况，本文以最小化超期交付天数、生产成本和总投入资源数量为目标，进行了柔性资源配置与调度集成优化问题的研究。首先，本文对研究问题进行了界定和详细描述，建立了多目标规划模型。其次，鉴于该问题的NP-hard特点，设计了基于Pareto优化的改进多目标差分进化算法，通过启发式染色体生成策略得到高质量的初始解集，结合快速非支配排序方法对个体进行排序，利用差分策略进行迭代优化，最终获得满意的解集。最后，通过算例分析将本文算法与两种常用算法进行了对比分析，验证了算法的有效性，并得出：当任务量多生产资源不足时，增加资源数量可以减少超期时间和生产成本；但当任务量少生产资源充足时，即使投入更多资源，也不会使得超期时间和生产成本进一步减少，还可能会带来资源浪费。

关键词: 柔性资源配置与调度, 多目标优化, 自适应差分进化算法, 快速非支配排序, 启发式策略

Abstract:

To cater to the multi-variety and small-batch characteristics of aerospace product manufacturing， flexible allocation and scheduling of resources in production workshops based on production planning is key to maintaining efficiency and response capability. In particular， an integrated optimization problem of resource allocation and scheduling is formulated and solved to minimize production delay， manufacturing costs， and total resources across multiple scenarios with various production resources， in-workshop transportation， and resource availability. A multi-objective programming model is first formulated based on a detailed delineation of our research questions. An improved multi-objective differential evolution （IMODE） algorithm is then put forward based on Pareto optimization to solve such an NP-hard problem efficiently. Upon obtaining a high-quality set of initial chromosomes based on heuristic search， the final solution of a Pareto set is derived from fast non-dominated sorting followed by iterative optimization through a differential evolution algorithm. Based on 11 scenarios with different combinations of job numbers and due dates generated from empirical data， IMODE on average outperforms NSGA-II and MOPSO， two widely-adopted algorithms for multi-objective optimization. Furthermore， our additional analyses identify a ceiling effect of resource quantity on overdue days and manufacturing costs. When there is a large number of jobs with insufficient resources， on the one hand， increasing the number of resources can mitigate production delays and costs. On the other hand， the allocation of more resources is unable to shorten overdue days or bring down costs in the context of a small job number with adequate production resources. In sum， flexible integrated resource allocation and scheduling through IMODE enhance resource utilization and manufacturing efficiency in the face of dynamic production demands.

Key words: flexible resource allocation and scheduling, multi-objective optimization, adaptive differential evolution algorithm, fast non-dominated sorting, heuristic strategy

中图分类号:

F273

李惠,王熙,左治亚. 多目标下航天产品生产车间柔性资源配置与调度集成优化[J]. 中国管理科学, 2024, 32(10): 146-155.

Hui Li,Xi Wang,Zhiya Zuo. Multi-objective Integrated Optimization of Flexible Resource Allocation and Scheduling in the Aerospace Production Workshop[J]. Chinese Journal of Management Science, 2024, 32(10): 146-155.

图/表 9

图1

图2

图3

表1

算例的Pareto解集"

算例	工序总数	超期时间 $f 1$ (天)	总成本 $f 2$ (千元)	资源投入数量 $f 3$
1	200	16	1911	47
		113	1893	45
		89	1900	36
2	221	5	2823	46
		126	2796	47
		44	2809	37
3	238	4	3339	46
		95	3319	46
		96	3331	35
4	262	0	3881	47
		86	3861	45
		23	3881	38
5	282	0	3901	42
		43	3889	48
		80	3907	37
6	300	0	4229	43
		48	4219	52
		226	4228	39
7	314	0	4308	44
		98	4302	51
		15	4324	37
8	345	0	4470	42
		20	4453	47
		56	4465	40
9	362	0	4536	51
		58	4531	47
		44	4546	40
10	401	0	4950	46
		78	4940	53
		278	4954	39
11	416	0	5471	45
		109	5466	52
		16	5485	41

表1

图4

图5

表2

表3

图6

参考文献 27

1	Chaudhry I A， Khan A A. A research survey： Review of flexible job shop scheduling techniques［J］. International Transactions in Operational Research， 2016， 23（3）： 551-591.
2	Kress D， Müller D， Nossack J. A worker constrained flexible job shop scheduling problem with sequence-dependent setup times［J］. OR Spectrum， 2019， 41（1）： 179-217.
3	仇永涛. 离散智能车间扰动预测与高效运行管控方法研究［D］. 无锡：江南大学， 2020.
	Qiu Y T. Research on disturbance prediction and efficientoperation control of intelligent job shop［D］. Wuxi： Jiangnan University， 2020.
4	Dai M， Tang D B， Giret A， et al. Multi-objective optimization for energy-efficient flexible job shop scheduling problem with transportation constraints［J］. Robotics and Computer-Integrated Manufacturing，2019，59： 143-157.
5	Zhang G H， Hu Y F， Sun J H， et al. An improved genetic algorithm for the flexible job shop scheduling problem with multiple time constraints［J］. Swarm and Evolutionary Computation， 2020， 54： 100664.
6	陈勇，王昊天，易文超，等. 基于元胞机与强化学习的多扰动车间调度算法［J］. 计算机集成制造系统， 2021，27（12）：3536-3549.
	Chen Y， Wang H T， Yi W C， et al. Algorithm of scheduling for multi-disturbance job-shop based oncellular automata and reinforcement learning［J］. Computer Integrated Manufacturing Systems， 2021，27（12）：3536-3549.
7	刘雪红，段程，王磊. 基于改进候鸟算法的柔性作业车间分批调度问题［J］. 计算机集成制造系统， 2021，27（11）：3185-3195.
	Liu X H， Duan C， Wang L. Flexible job shop scheduling with lot streaming based on improvedmigrating birds optimization algorithm［J］. Computer Integrated Manufacturing Systems， 2021，27（11）：3185-3195.
8	Zheng X L， Wang L. A knowledge-guided fruit fly optimization algorithm for dual resource constrained flexible job-shop scheduling problem［J］. International Journal of Production Research， 2016， 54（18）： 5554-5566.
9	Frihat M B， Hadj-Alouane A， Sadfi C. Optimization of the integrated problem of employee timetabling and job shop scheduling［J］. Computers & Operations Research， 2022， 137： 105332.
10	Lei D M， Guo X P. Variable neighbourhood search for dual-resource constrained flexible job shop scheduling［J］. International Journal of Production Research， 2014， 52（9）： 2519-2529.
11	Gong G L， Chiong R， Deng Q W， et al. Energy-efficient flexible flow shop scheduling with worker flexibility［J］. Expert Systems with Applications， 2020， 141： 112902.
12	Luo Q， Deng Q W， Gong G L， et al. An efficient memetic algorithm for distributed flexible job shop scheduling problem with transfers［J］. Expert Systems with Applications， 2020， 160： 113721.
13	刘强. 复杂产品总装生产线资源配置优化研究［D］. 北京：北京化工大学， 2020.
	Liu Q. Research on resource allocation optimization of complex product assembly line［D］. Beijing： Beijing University of Chemical Technology， 2020.
14	Defersha F M， Rooyani D. An efficient two-stage genetic algorithm for a flexible job-shop scheduling problem with sequence dependent attached/detached setup， machine release date and lag-time［J］. Computers & Industrial Engineering， 2020， 147： 106605.
15	Zhang F F， Mei Y， Nguyen S， et al. Evolving scheduling heuristics via genetic programming with feature selection in dynamic flexible job-shop scheduling［J］. IEEE Transactions on Cybernetics， 2021， 51（4）： 1797-1811.
16	Chen R H， Yang B， Li S， et al. A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem［J］. Computers & Industrial Engineering， 2020， 149： 106778.
17	顾九春，姜天华，朱惠琦. 多目标离散灰狼优化算法求解作业车间节能调度问题［J］. 计算机集成制造系统， 2021，27（8）：2295-2306.
	Gu J C， Jiang T H， Zhu H Q. Energy-saving job shop scheduling problem with multi-objective discrete grey wolf optimization algorithm［J］.Computer Integrated Manufacturing Systems， 2021，27（8）：2295-2306.
18	Gong G L， Chiong R， Deng Q W， et al. A hybrid artificial bee colony algorithm for flexible job shop scheduling with worker flexibility［J］. International Journal of Production Research， 2020， 58（14）： 4406-4420.
19	Li Y B， Huang W X， Wu R， et al. An improved artificial bee colony algorithm for solving multi-objective low-carbon flexible job shop scheduling problem［J］. Applied Soft Computing， 2020， 95： 106544.
20	Gao D， Wang G G， Pedrycz W. Solving fuzzy job-shop scheduling problem using de algorithm improved by a selection mechanism［J］. IEEE Transactions on Fuzzy Systems， 2020， 28（12）： 3265-3275.
21	An Y J， Chen X H， Li Y H， et al. An improved non-dominated sorting biogeography-based optimization algorithm for the （hybrid） multi-objective flexible job-shop scheduling problem［J］. Applied Soft Computing， 2021， 99： 106869.
22	Ding H J， Gu X S. Improved particle swarm optimization algorithm based novel encoding and decoding schemes for flexible job shop scheduling problem［J］. Computers & Operations Research，2020，121： 104951.
23	Caldeira R H， Gnanavelbabu A. A Pareto based discrete Jaya algorithm for multi-objective flexible job shop scheduling problem［J］. Expert Systems with Applications， 2021， 170： 114567.
24	Wang X Z， Wang B， Zhang X X， et al. Two-objective robust job-shop scheduling with two problem-specific neighborhood structures［J］. Swarm and Evolutionary Computation， 2021， 61： 100805.
25	Akbar M， Irohara T. NSGA-II variants for solving a social-conscious dual resource-constrained scheduling problem［J］. Expert Systems with Applications， 2020， 162： 113754.
26	Tan W H， Yuan X F， Wang J L， et al. A fatigue-conscious dual resource constrained flexible job shop scheduling problem by enhanced NSGA-II： An application from casting workshop［J］. Computers & Industrial Engineering， 2021， 160： 107557.
27	徐小峰，林姿汝，周鹏. 多油品供给受限下多油库被动配送车辆路径问题研究［J］. 中国管理科学， 2021， 29（5）： 157-165.
	Xu X F， Lin Z R， Zhou P. Research on vehicle routing problem of multiple oil depot passive distribution undermulti oil supply constraints［J］.Chinese Journal of Management Science， 2021， 29（5）： 157-165.

算例	工序总数	A: IMODE B: NSGA-Ⅱ		A: IMODE B: MOPSO		A: NSGA-Ⅱ B: MOPSO		IGD
算例	工序总数	C(A,B)	C(B,A)	C(A,B)	C(B,A)	C(A,B)	C(B,A)	IMODE	NSGA-Ⅱ	MOPSO
1	200	0.892768	0.000000	0.485149	0.000000	0.297030	0.446384	0.014751	0.023054	0.032566
2	221	0.927374	0.000000	0.650000	0.000000	0.166667	0.505587	0.013363	0.028650	0.027697
3	238	0.994475	0.000000	0.583333	0.000000	0.250000	0.078729	0.014245	0.044035	0.058596
4	262	0.944112	0.000000	0.413793	0.000000	0.146552	0.057884	0.021410	0.046133	0.041833
5	282	1.000000	0.000000	0.404762	0.000000	0.285714	0.000000	0.017126	0.043978	0.065493
6	300	0.894428	0.000000	0.546763	0.000000	0.287770	0.388563	0.025469	0.037573	0.026460
7	314	1.000000	0.000000	0.848739	0.000000	0.168067	0.292308	0.015110	0.043681	0.058750
8	345	0.995792	0.000000	0.415929	0.000000	0.079646	0.683029	0.016943	0.041294	0.018143
9	362	1.000000	0.000000	0.772358	0.000000	0.333333	0.555556	0.010847	0.027219	0.035677
10	401	1.000000	0.000000	0.464789	0.000000	0.084507	0.432191	0.018521	0.044088	0.018947
11	416	1.000000	0.000000	0.581818	0.000000	0.218182	0.170732	0.034609	0.048620	0.063734

算例	工序总数	运行时间
算例	工序总数	IMODE	NSGA-Ⅱ	MOPSO
1	200	3102.6	5726.8	3408.4
2	221	3350.2	6290.8	3684.5
3	238	3520.7	6894.1	4051.9
4	262	3806.2	7591.0	4271.0
5	282	4119.3	8155.5	4559.7
6	300	4360.1	8513.7	4810.7
7	314	4521.4	8822.7	5009.2
8	345	4890.0	10140.9	5449.7
9	362	5129.1	10745.2	5671.4
10	401	5672.5	11967.3	6244.4
11	416	5780.6	12356.6	6463.6

[1]	李铁克,苏艺璇,张文新,王柏琳. 加工时间不确定的炼钢-连铸区间多目标优化调度[J]. 中国管理科学, 2024, 32(8): 95-106.
[2]	汪和平,赵登宇,陈梦凯,李艳. 基于MO-CGJaya/D算法的PC构件混流生产作业指派优化研究[J]. 中国管理科学, 2024, 32(7): 95-105.
[3]	王付宇,谢昊轩,林钟高,王骏. 突发事件下高铁站应急疏散多目标优化模型与自适应量子蚁群算法[J]. 中国管理科学, 2024, 32(3): 188-197.
[4]	王海宇. 基于简单检测方法的动态 $n p x$ 控制图的经济统计优化设计[J]. 中国管理科学, 2023, 31(9): 205-213.
[5]	单汩源, 王建江, 别黎. 基于自适应大邻域搜索的鲁棒多项目调度方法[J]. 中国管理科学, 2022, 30(9): 217-231.
[6]	牛奔, 郭晨, 唐恒. 基于多目标多元学习细菌觅食优化算法的混合数据聚类[J]. 中国管理科学, 2022, 30(12): 131-140.
[7]	徐小峰, 林姿汝, 周鹏. 多油品供给受限下多油库被动配送车辆路径问题研究[J]. 中国管理科学, 2021, 29(5): 157-165.
[8]	彭武良, 马小菁. 一种策略层项目计划的双目标优化方法[J]. 中国管理科学, 2021, 29(2): 69-77.
[9]	董雪璠, 刘怡君, 廉莹. 基于熵控原理的多目标第三产业结构优化模型——以北京市为例[J]. 中国管理科学, 2017, 25(9): 53-62.
[10]	吴志樵, 卢祥远, 牟立峰, 唐加福. 考虑采购成本与组合风险的构件优化选择方法[J]. 中国管理科学, 2017, 25(8): 158-165.
[11]	丁秋雷. 客户时间窗变化的物流配送干扰管理模型——基于行为的视角[J]. 中国管理科学, 2015, 23(5): 89-97.
[12]	葛怀志, 张金隆. 基于公理设计和功能过剩的公共住房撮合分配方法[J]. 中国管理科学, 2015, 23(1): 111-120.
[13]	李双琳, 马祖军, 郑斌, 代颖. 震后初期应急物资配送的模糊多目标选址-多式联运问题[J]. 中国管理科学, 2013, (2): 144-151.
[14]	王克喜, 袁际军, 黄敏镁, 陈为民. 多平台下的参数化产品族多目标智能优化[J]. 中国管理科学, 2011, 19(4): 111-119.
[15]	齐二石, 李辉, 刘亮. 基于遗传算法的虚拟企业协同资源优化问题研究[J]. 中国管理科学, 2011, 19(1): 77-83.