Unrelated Parallel Machine Scheduling with Additional Resource and Learning Effect

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

Abstract

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

CLC Number:

TP273

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

Figures/Tables 7

Table 1

Parameters and their levels

参数	水平
参数	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

Table 1

Fig. 1

Table 2

Computational results of five algorithms on 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

Table 2

Table 3

Computational results of five algorithms on 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

Table 3

Table 4

Computational results of five algorithms on 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

Table 4

Fig. 2

Fig. 3

References 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]	Chuandong Qin, Baosheng Li, Baole Han. Multi-strategy Hybrid ABC for Microarray High-Dimensional Feature Selection [J]. Journal of System Simulation, 2023, 35(3): 515-524.
[2]	Qing Dongsheng, Zhang Xiaofang, Li Jianjun, Guo Rui, Deng Qiaoling. Spatial Structure Optimization of Natural Forest Based on Bee Colony-particle Swarm Algorithm [J]. Journal of System Simulation, 2020, 32(3): 371-381.
[3]	Guo Xudong, Lu Zhengping, Jiang Qinfen, Wang Shuyi, Cui Haipo. Algorithm for Tracking Position and Orientation of Drug Delivery Capsules in Gastrointestinal Tract [J]. Journal of System Simulation, 2018, 30(6): 2288-2294.
[4]	Yang Xiaojian, Dong Yiwei. Adaptive Quick Artificial Bee Colony Algorithm Based on Opposition Learning [J]. Journal of System Simulation, 2016, 28(11): 2684-2692.
[5]	Zhang Ming, Tian Na, Ji Zhicheng. Balanced Bee Colony Algorithm Based on Fitness Euclidean-distance Ratio [J]. Journal of System Simulation, 2015, 27(5): 980-989.