考虑附加资源和学习效应的不相关并行机调度

doi:10.16182/j.issn1004731x.joss.22-0791

摘要/Abstract

摘要：

针对考虑附加资源和学习效应的不相关并行机调度问题(unrelated parallel machine scheduling problem， UPMSP)，提出一种动态人工蜂群算法(dynamical artificial bee colony， DABC)，实现最小化最大完成时间。给出一种新的编码方法和解码过程，并构建2个初始蜂群；提出一种蜂群评估策略，以动态确定雇佣蜂群和跟随蜂群；在雇佣蜂阶段和跟随蜂阶段采用不同搜索策略，以增强算法的探索能力。实验结果表明：DABC的新策略合理有效，且该算法在求解UPMSP时收敛性、平均值和稳定性更强，显示出较强的搜索性能。

关键词: 不相关并行机调度, 附加资源, 学习效应, 人工蜂群算法

Abstract:

To solve unrelated parallel machine scheduling problem(UPMSP) with additional resource and learning effect, a dynamical artificial bee colony(DABC) algorithm is proposed to minimize the makespan. A new representation and decoding process is given and two initial bee swarms are constructed. A swarm evaluation method is applied to dynamically decide employed bee swarms and onlooker bee swarms. Employed bee phase and onlooker bee phase are implemented in different ways to increase exploration ability. The experimental results show that the new strategies of DABC are effective and reasonable, and can obtain results with better convergence, average value and stability, which d has high search performance in solving the considered UPMSP.

Key words: unrelated parallel machine scheduling, additional resource, learning effect, artificial bee colony

中图分类号:

TP273

郑友莲,雷德明 . 考虑附加资源和学习效应的不相关并行机调度[J]. 系统仿真学报, 2023, 35(12): 2560-2569.

Zheng Youlian,Lei Deming . Unrelated Parallel Machine Scheduling with Additional Resource and Learning Effect[J]. Journal of System Simulation, 2023, 35(12): 2560-2569.

图/表 7

表1

参数及其水平

参数	水平
参数	1	2	3
P	40	50	60
L	10	15	20
$p ¯ e$	8	10	12
$p ¯ r$	30	35	40
$γ$	0.2	0.3	0.4

表1

图1

表2

5种算法关于min的计算结果

实例	DABC	ABC	TAFOA	HPSOGA	MPH	实例	DABC	ABC	TAFOA	HPSOGA	MPH
$8 × 2 × 1$	210.5	210.5	237.9	290.8	210.5	$30 × 2 × 1$	800.3	854.1	845.8	1 012.6	876.1
$8 × 2 × 2$	246.2	246.2	246.3	253.5	246.2	$30 × 2 × 2$	643.2	668.5	656.1	713.0	663.4
$8 × 4 × 1$	114.3	114.3	120.3	129.1	126.0	$30 × 4 × 1$	354.2	380.0	375.5	410.1	416.1
$8 × 4 × 2$	114.8	114.8	133.4	146.1	135.7	$30 × 4 × 2$	326.6	370.2	348.5	363.4	316.7
$8 × 6 × 1$	103.0	103.0	103.0	103.0	103.0	$30 × 6 × 1$	292.1	319.2	317.8	341.3	343.9
$8 × 6 × 2$	106.0	106.0	106.0	106.0	106.0	$30 × 6 × 2$	246.5	260.7	261.4	285.4	267.0
$12 × 2 × 1$	228.2	230.2	257.4	288.6	241.6	$50 × 2 × 1$	266.8	306.4	296.6	339.8	289.4
$12 × 2 × 2$	401.9	478.5	428.0	443.5	402.1	$50 × 2 × 2$	260.2	287.6	281.1	311.5	287.8
$12 × 4 × 1$	209.6	252.2	215.5	231.8	236.5	$50 × 4 × 1$	191.0	222.6	213.5	249.8	222.6
$12 × 4 × 2$	186.0	209.0	195.2	204.6	185.5	$50 × 4 × 2$	149.8	177.7	163.5	202.3	170.6
$12 × 6 × 1$	140.0	143.0	149.3	217.6	152.3	$50 × 6 × 1$	122.0	144.5	133.9	194.8	142.8
$12 × 6 × 2$	139.3	141.1	155.5	212.6	153.3	$50 × 6 × 2$	115.2	143.8	140.1	208.6	143.4
$16 × 2 × 1$	390.3	493.7	391.8	503.7	407.5	$150 × 2 × 1$	822.1	901.2	882.7	1 047.2	1 000.5
$16 × 2 × 2$	422.4	451.4	422.4	507.9	432.9	$150 × 2 × 2$	721.9	775.4	730.6	869.8	730.7
$16 × 4 × 1$	265.3	337.8	274.1	339.1	318.2	$150 × 4 × 1$	484.7	494.1	446.8	587.3	502.9
$16 × 4 × 2$	195.3	210.5	198.2	221.1	196.8	$150 × 4 × 2$	424.9	446.9	440.1	523.2	553.0
$16 × 6 × 1$	133.5	154.4	147.7	159.7	140.1	$150 × 6 × 1$	331.2	347.8	334.5	482.9	470.8
$16 × 6 × 2$	141.9	163.3	159.4	165.8	147.5	$150 × 6 × 2$	275.1	352.8	307.0	427.4	515.4
$20 × 2 × 1$	451.2	547.9	502.2	500.4	453.2	$250 × 2 × 1$	1 283.6	1 521.3	1 373.1	1 615.2	1 400.2
$20 × 2 × 2$	463.4	496.5	465.7	539.1	529.7	$250 × 2 × 2$	1 173.6	1 263.1	1 248.3	1 420.5	1 561.5
$20 × 4 × 1$	322.3	422.3	334.7	399.7	386.7	$250 × 4 × 1$	746.4	835.2	725.8	860.0	945.1
$20 × 4 × 2$	263.3	290.3	276.6	290.3	287.8	$250 × 4 × 2$	728.7	884.2	863.4	868.6	743.3
$20 × 6 × 1$	199.3	209.2	210.1	239.3	207.9	$250 × 6 × 1$	592.8	784.3	648.5	801.7	614.6
$20 × 6 × 2$	186.3	197.7	178.2	198.1	194.3	$250 × 6 × 2$	561.3	642.6	581.2	721.8	745.7
$25 × 2 × 1$	573.4	720.2	593.1	685.6	592.1	$350 × 2 × 1$	1 923.2	2 263.8	2 031.1	2 334.9	2 139.3
$25 × 2 × 2$	581.2	589.6	587.0	600.7	624.5	$350 × 2 × 2$	1 786.0	1 980.5	1 874.2	2 257.2	1 854.7
$25 × 4 × 1$	305.3	430.1	369.7	363.8	352.9	$350 × 4 × 1$	1 078.8	1 305.3	1 154.1	1 341.6	1 052.0
$25 × 4 × 2$	362.2	398.6	389.5	374.3	378.3	$350 × 4 × 2$	947.1	1 156.1	1 013.2	1 083.2	1 337.1
$25 × 6 × 1$	211.2	241.3	221.3	260.3	246.8	$350 × 6 × 1$	782.4	1 266.5	866.7	1 038.7	899.4
$25 × 6 × 2$	194.0	208.0	215.0	237.3	216.9	$350 × 6 × 2$	675.8	914.6	780.1	861.6	834.0

表2

表3

5种算法关于avg的计算结果

实例	DABC	ABC	TAFOA	HPSOGA	MPH	实例	DABC	ABC	TAFOA	HPSOGA	MPH
$8 × 2 × 1$	210.5	211.0	239.8	300.9	216.2	$30 × 2 × 1$	813.3	893.6	858.6	1 020.1	879.5
$8 × 2 × 2$	246.2	246.2	248.2	261.5	246.2	$30 × 2 × 2$	652.6	681.6	664.2	720.2	680.7
$8 × 4 × 1$	114.3	114.8	132.3	131.1	126.0	$30 × 4 × 1$	362.1	390.3	388.9	430.9	439.1
$8 × 4 × 2$	114.8	114.8	148.1	148.0	144.9	$30 × 4 × 2$	331.9	377.6	353.5	370.9	329.0
$8 × 6 × 1$	103.0	103.0	108.2	104.8	104.2	$30 × 6 × 1$	299.0	335.2	327.8	359.2	368.7
$8 × 6 × 2$	106.0	106.0	106.2	106.5	106.3	$30 × 6 × 2$	248.7	271.8	281.7	288.2	284.9
$12 × 2 × 1$	228.6	235.3	264.8	295.7	260.3	$50 × 2 × 1$	286.8	320.3	308.0	361.9	306.3
$12 × 2 × 2$	408.4	481.2	431.8	452.3	404.8	$50 × 2 × 2$	265.3	295.3	290.0	313.3	293.8
$12 × 4 × 1$	215.3	264.2	222.4	246.3	243.9	$50 × 4 × 1$	199.6	230.0	222.5	262.2	228.8
$12 × 4 × 2$	187.9	216.2	207.4	209.4	191.0	$50 × 4 × 2$	159.2	187.4	178.2	216.9	180.0
$12 × 6 × 1$	142.1	145.5	158.1	229.0	159.4	$50 × 6 × 1$	125.7	150.3	145.0	211.1	148.6
$12 × 6 × 2$	141.9	147.8	164.0	217.0	161.7	$50 × 6 × 2$	121.1	148.6	146.8	222.9	150.2
$16 × 2 × 1$	394.8	498.3	397.3	516.5	421.6	$150 × 2 × 1$	829.9	918.5	901.9	1 055.7	1 004.1
$16 × 2 × 2$	424.2	455.1	428.5	512.1	438.4	$150 × 2 × 2$	737.7	788.8	746.0	875.2	754.4
$16 × 4 × 1$	273.1	347.9	287.8	347.0	335.6	$150 × 4 × 1$	495.0	507.3	455.5	591.2	507.5
$16 × 4 × 2$	198.1	222.8	205.4	231.5	205.4	$150 × 4 × 2$	426.9	470.0	441.8	544.0	561.5
$16 × 6 × 1$	139.1	165.2	162.9	168.7	150.2	$150 × 6 × 1$	337.9	364.0	345.8	487.2	485.2
$16 × 6 × 2$	143.7	170.0	169.3	173.2	151.6	$150 × 6 × 2$	285.3	357.3	322.8	437.3	524.8
$20 × 2 × 1$	455.0	551.6	517.4	503.3	463.6	$250 × 2 × 1$	1 288.9	1 552.1	1 397.5	1 624.8	1 406.5
$20 × 2 × 2$	467.4	510.8	477.8	544.2	538.3	$250 × 2 × 2$	1 178.6	1 267.9	1 252.2	1 427.2	1 569.3
$20 × 4 × 1$	330.7	429.1	345.7	421.0	388.1	$250 × 4 × 1$	755.0	841.0	739.5	863.5	952.8
$20 × 4 × 2$	266.6	309.1	280.1	299.3	310.9	$250 × 4 × 2$	735.7	888.6	867.6	874.7	752.9
$20 × 6 × 1$	201.3	216.9	240.5	259.2	217.4	$250 × 6 × 1$	597.2	790.4	651.3	808.8	620.4
$20 × 6 × 2$	189.4	202.5	183.1	204.0	202.8	$250 × 6 × 2$	565.2	649.8	591.4	745.3	757.7
$25 × 2 × 1$	582.2	740.0	600.7	693.3	601.7	$350 × 2 × 1$	1 929.7	2 275.8	2 052.2	2 340.9	2 144.7
$25 × 2 × 2$	584.6	596.2	593.7	608.9	649.2	$350 × 2 × 2$	1 819.3	1 985.2	1 882.6	2 264.8	1 861.6
$25 × 4 × 1$	310.6	440.5	391.3	376.1	363.6	$350 × 4 × 1$	1 084.5	1 310.9	1 158.2	1 346.7	1 055.7
$25 × 4 × 2$	369.1	405.5	398.4	383.2	389.9	$350 × 4 × 2$	959.8	1 167.3	1 022.0	1 089.2	1 346.9
$25 × 6 × 1$	216.9	252.9	230.7	266.0	253.9	$350 × 6 × 1$	790.6	1 271.7	870.3	1 048.9	908.4
$25 × 6 × 2$	198.1	211.9	227.7	244.6	229.8	$350 × 6 × 2$	683.4	919.6	792.2	870.2	839.4

表3

表4

5种算法关于max的计算结果

实例	DABC	ABC	TAFOA	HPSOGA	MPH	实例	DABC	ABC	TAFOA	HPSOGA	MPH
$8 × 2 × 1$	210.5	211.2	240.2	310.2	220.3	$30 × 2 × 1$	831.1	917.3	1 003.0	1 089.4	1 176.8
$8 × 2 × 2$	246.2	246.2	249.3	263.0	246.2	$30 × 2 × 2$	655.3	685.9	716.0	746.8	778.6
$8 × 4 × 1$	114.3	115.9	140.3	165.4	126.0	$30 × 4 × 1$	364.2	395.7	426.7	458.4	491.1
$8 × 4 × 2$	114.8	114.8	155.9	197.7	240.5	$30 × 4 × 2$	335.3	385.3	434.8	485.0	334.9
$8 × 6 × 1$	103.0	103.0	111.1	119.9	129.7	$30 × 6 × 1$	305.2	353.9	402.1	451.0	500.9
$8 × 6 × 2$	106.0	106.0	106.8	108.3	110.8	$30 × 6 × 2$	249.3	280.5	311.2	342.6	375.0
$12 × 2 × 1$	229.0	239.7	277.3	315.6	354.9	$50 × 2 × 1$	299.2	334.2	368.7	403.9	440.1
$12 × 2 × 2$	412.9	485.5	557.6	630.4	704.2	$50 × 2 × 2$	270.5	300.9	330.8	361.4	393.0
$12 × 4 × 1$	218.3	269.3	319.8	371.0	423.2	$50 × 4 × 1$	203.2	237.7	271.7	306.4	342.1
$12 × 4 × 2$	188.9	220.1	250.8	282.2	314.6	$50 × 4 × 2$	162.3	195.9	229.0	262.8	297.6
$12 × 6 × 1$	144.3	148.3	151.8	156.0	161.2	$50 × 6 × 1$	130.7	155.3	179.4	204.2	230.0
$12 × 6 × 2$	143.6	150.3	156.5	163.4	171.3	$50 × 6 × 2$	124.8	153.7	182.1	211.2	241.3
$16 × 2 × 1$	398.3	500.2	601.6	703.7	806.8	$150 × 2 × 1$	837.5	926.3	1 014.6	1 103.6	1 193.6
$16 × 2 × 2$	425.9	459.3	492.2	525.8	560.4	$150 × 2 × 2$	750.3	803.5	856.2	909.6	964.0
$16 × 4 × 1$	277.3	356.1	434.4	513.4	593.4	$150 × 4 × 1$	506.1	511.9	517.2	523.2	530.2
$16 × 4 × 2$	200.7	232.4	263.6	295.5	328.4	$150 × 4 × 2$	429.3	482.3	534.8	588.0	642.2
$16 × 6 × 1$	142.7	169.9	196.6	224.0	252.4	$150 × 6 × 1$	340.2	377.3	413.9	451.2	489.5
$16 × 6 × 2$	145.2	180.8	215.9	251.7	288.5	$150 × 6 × 2$	295.3	362.8	429.8	497.5	566.2
$20 × 2 × 1$	456.0	556.3	656.1	756.6	858.1	$250 × 2 × 1$	1 299.8	1 578.1	1 855.9	2 134.4	2 413.9
$20 × 2 × 2$	469.1	515.1	560.6	606.8	654.0	$250 × 2 × 2$	1 182.2	1 280.0	1 377.3	1 475.3	15 74.3
$20 × 4 × 1$	335.2	533.2	730.7	928.9	1 128.1	$250 × 4 × 1$	759.6	855.1	950.1	1 045.8	1 142.5
$20 × 4 × 2$	268.7	319.2	369.2	419.9	471.6	$250 × 4 × 2$	743.2	899.3	1 054.9	1 211.2	1 368.5
$20 × 6 × 1$	203.6	221.8	239.5	257.9	277.3	$250 × 6 × 1$	599.9	799.1	997.8	1 197.2	1 397.6
$20 × 6 × 2$	193.7	208.7	223.2	238.4	254.6	$250 × 6 × 2$	567.8	657.3	746.3	836.0	926.7
$25 × 2 × 1$	585.3	766.3	946.8	1 128.0	1 310.2	$350 × 2 × 1$	1 935.2	2 288.2	2 640.7	2 993.9	3 348.1
$25 × 2 × 2$	588.3	600.3	611.8	624.0	637.2	$350 × 2 × 2$	1 840.9	1 990.5	2 139.6	2 289.4	2 440.2
$25 × 4 × 1$	320.6	453.2	585.3	718.1	851.9	$350 × 4 × 1$	1 095.0	1 314.9	1 534.3	1 754.4	1 975.5
$25 × 4 × 2$	375.2	411.1	446.5	482.6	519.7	$350 × 4 × 2$	968.1	1 177.6	1 386.6	1 596.3	1 807.0
$25 × 6 × 1$	220.3	262.3	303.8	346.0	389.2	$350 × 6 × 1$	800.1	1 277.2	1 753.8	2 231.1	2 709.4
$25 × 6 × 2$	199.3	213.4	227.0	241.3	256.6	$350 × 6 × 2$	689.4	922.3	1 154.7	1 387.8	1 621.9

表4

图2

图3

参考文献 20

1	Cheng T C E, Sin C C S. A State-of-the-art Review of Parallel-machine Scheduling Research[J]. European Journal of Operational Research, 1990, 47(3): 271-292.
2	Zheng Xiaolong, Wang Ling. A Two-stage Adaptive Fruit Fly Optimization Algorithm for Unrelated Parallel Machine Scheduling Problem with Additional Resource Constraints[J]. Expert Systems with Applications, 2016, 65: 28-39.
3	Fanjul-Peyro L, Perea F, Ruiz Rubén. Models and Matheuristics for the Unrelated Parallel Machine Scheduling Problem with Additional Resources[J]. European Journal of Operational Research, 2017, 260(2): 482-493.
4	Yepes-Borrero J C, Villa F, Perea F, et al. GRASP Algorithm for the Unrelated Parallel Machine Scheduling Problem with Setup Times and Additional Resources[J]. Expert Systems with Applications, 2020, 141: 112959.
5	Lei Deming, He Shaosi. An Adaptive Artificial Bee Colony for Unrelated Parallel Machine Scheduling with Additional Resource and Maintenance[J]. Expert Systems with Applications, 2022, 205: 117577.
6	Soleimani H, Ghaderi H, Tsai P W, et al. Scheduling of Unrelated Parallel Machines Considering Sequence-related Setup Time, Start Time-dependent Deterioration, Position-dependent Learning and Power Consumption Minimization[J]. Journal of Cleaner Production, 2020, 249: 119428.
7	Zhang Like, Deng Qianwang, Lin Ruihang, et al. A Combinatorial Evolutionary Algorithm for Unrelated Parallel Machine Scheduling Problem with Sequence and Machine-dependent Setup Times, Limited Worker Resources and Learning Effect[J]. Expert Systems with Applications, 2021, 175: 114843.
8	轩华, 张寒, 王薛苑. 带恶化和学习效应的不相关并行机调度优化[J]. 控制工程, 2023, 30(5): 769-778.
	Xuan Hua, Zhang Han, Wang Xueyuan. Optimization on Unrelated Parallel Machine Scheduling with Deteriorating and Learning Effects[J]. Control Engineering of China, 2023, 30(5): 769-778.
9	Sharma N, Sharma H, Sharma A. Beer Froth Artificial Bee Colony Algorithm for Job-shop Scheduling Problem[J]. Applied Soft Computing, 2018, 68: 507-524.
10	Lin W C, Xu Jianyou, Bai Danyu, et al. Artificial Bee Colony Algorithms for the Order Scheduling with Release Dates[J]. Soft Computing, 2019, 23(18): 8677-8688.
11	Lei Deming, Yuan Yue, Cai Jingcao. An Improved Artificial Bee Colony for Multi-objective Distributed Unrelated Parallel Machine Scheduling[J]. International Journal of Production Research, 2021, 59(17): 5259-5271.
12	Zhang Rui, Chang P C, Song Shiji, et al. A Multi-objective Artificial Bee Colony Algorithm for Parallel Batch-processing Machine Scheduling in Fabric Dyeing Processes[J]. Knowledge-Based Systems, 2017, 116: 114-129.
13	Cao Yang, Shi Haibo. An Adaptive Multi-strategy Artificial Bee Colony Algorithm for Integrated Process Planning and Scheduling[J]. IEEE Access, 2021, 9: 65622-65637.
14	Liu Qihao, Li Xinyu, Gao Liang, et al. Mathematical Model and Discrete Artificial Bee Colony Algorithm for Distributed Integrated Process Planning and Scheduling[J]. Journal of Manufacturing Systems, 2021, 61: 300-310.
15	Ying K C, Lin S W. Unrelated Parallel Machine Scheduling with Sequence-and Machine-dependent Setup Times and Due Date Constraints[J]. International Journal of Innovative Computing, Information & Control, 2012, 8(5): 3279-3297.
16	Lin S W, Ying K C. ABC-based Manufacturing Scheduling for Unrelated Parallel Machines with Machine-dependent and Job Sequence-dependent Setup Times[J]. Computers & Operations Research, 2014, 51: 172-181.
17	雷德明, 杨海. 求解多目标不相关并行机调度问题的多群体人工蜂群算法[J]. 控制与决策, 2022, 37(5): 1174-1182.
	Lei Deming, Yang Hai. Multi-colony Artificial Bee Colony Algorithm for Multi-objective Unrelated Parallel Machine Scheduling Problem[J]. Control and Decision, 2022, 37(5): 1174-1182.
18	Lu Shaojun, Liu Xinbao, Pei Jun, et al. A Hybrid ABC-TS Algorithm for the Unrelated Parallel-batching Machines Scheduling Problem with Deteriorating Jobs and Maintenance Activity[J]. Applied Soft Computing, 2018, 66: 168-182.
19	Villa F, Vallada E, Fanjul-Peyro L. Heuristic Algorithms for the Unrelated Parallel Machine Scheduling Problem with One Scarce Additional Resource[J]. Expert Systems with Applications, 2018, 93: 28-38.
20	Salehi Mir M S, Rezaeian J. A Robust Hybrid Approach Based on Particle Swarm Optimization and Genetic Algorithm to Minimize the Total Machine Load on Unrelated Parallel Machines[J]. Applied Soft Computing, 2016, 41: 488-504.

[1]	秦传东, 李宝胜, 韩宝乐. 微阵列高维特征选择的多策略混合人工蜂群算法[J]. 系统仿真学报, 2023, 35(3): 515-524.
[2]	轩华, 秦莹莹, 王薛苑, 张百林. 带恶化工件的不相关并行机调度优化[J]. 系统仿真学报, 2019, 31(5): 919-924.
[3]	郭旭东, 鲁正平, 蒋琴芬, 王殊轶, 崔海坡. 胃肠道给药胶囊的方位跟踪求解算法[J]. 系统仿真学报, 2018, 30(6): 2288-2294.
[4]	崔秋丽. 基于人工蜂群算法的微网并网优化运行[J]. 系统仿真学报, 2018, 30(4): 1551-1559.
[5]	杨小健, 董毅伟. 基于反向学习的自适应快速人工蜂群算法[J]. 系统仿真学报, 2016, 28(11): 2684-2692.
[6]	张明, 田娜, 纪志成. 基于适应值欧式距离比的均衡蜂群算法[J]. 系统仿真学报, 2015, 27(5): 980-989.