Intelligent optimization for multiprocessor systems: hybrid algorithmic strategies for scheduling and load balancing

Figures & data

Figure 1. Components in multi-processor operating system.

Figure 2. Process of beam search.

Figure 3. Integrated algorithm in multi-processor system.

Table 1. Displays a typical job set comprising its operations and corresponding node codes.

Job. No	1			2			3			4		5
Operation number with node code	1	2	3	4	5	6	7	8	9	10	11	12	13
	0	0	0	1	1	1	2	2	2	3	3	4	4
Machine number	M1	M2	M4	M1	M3	M2	M3	M4	M1	M4	M2	M3	M1

Figure 4. Visualization of nodes within the beam.

Table 2. Neighboring nodes in a beam with width 2 and branching factor 2.

Node No.	Node operations	OCT
1	[4, 2, 0, 3, 1, 0, 1, 2, 3, 2, 0, 4, 1]	112
2	[2, 0, 3, 2, 4, 1, 0, 4, 3, 1, 1, 2, 0]	120
3	[2, 0, 3, 2, 1, 4, 0, 1, 3, 0, 1, 4, 2]	142
4	[2, 0, 3, 2, 4, 1, 0, 4, 3, 1, 1, 2, 0]	106
5	[2, 0, 3, 2, 1, 4, 0, 1, 3, 0, 1, 4, 2]	111
6	[0, 2, 0, 3, 1, 4, 1, 2, 3, 2, 0, 4, 1]]	121
7	[2, 0, 3, 2, 4, 1, 0, 4, 3, 1, 1, 2, 0]	114
8	[2, 0, 3, 2, 1, 4, 0, 1, 3, 0, 1, 4, 2]	106
9	[0, 2, 0, 3, 1, 4, 1, 2, 3, 2, 0, 4, 1]	109
10	[2, 0, 3, 2, 1, 4, 0, 1, 3, 0, 1, 4, 2]	110
11	[0, 2, 0, 3, 1, 4, 1, 2, 3, 2, 0, 4, 1]	109
12	[0, 2, 1, 3, 0, 4, 1, 2, 3, 2, 0, 4, 1]	121
13	[3, 0, 2, 3, 1, 4, 2, 0, 2, 1, 1, 4, 0]	106

Table 3. The computation of the cost function for J2 and L2.

OP.no	Mac.no	Veh.no	Veh Prev Loc	Prev Ope Mac no	Veh ready time	Pre Op Comp time	Veh empty travel	Mac ready time	Veh loaded travel	Proc time	Make span
3	M4	1	LU	LU	0	0	0	0	6	12	18
0	M1	2	LU	LU	0	0	0	0	3	12	15
2	M3	1	M4	LU	6	0	9	0	14	18	32
3	M2	2	M1	M4	3	18	18	0	22	30	52
1	M1	1	M3	LU	14	0	18	15	21	36	57
4	M3	1	M1	LU	21	0	27	32	32	6	38
2	M4	2	M2	M3	22	32	32	18	35	6	41
0	M2	1	M3	M1	32	15	36	52	52	24	76
2	M1	2	M4	M4	35	41	41	57	57	24	81
1	M3	1	M2	M1	52	57	57	38	61	12	73
1	M2	1	M3	M3	61	73	73	76	76	30	106
4	M1	2	M1	M3	57	38	61	81	81	18	99
0	M4	1	M2	M2	76	76	76	41	80	18	98

Table 4. The computation of the cost function for J5 and L1.

OP no.	Mac no.	Veh no.	Veh Prev Loc	Prev Ope Mac no	Veh ready time	Pre Op Comp time	Veh empty travel	Mac ready time	Veh loaded travel	Proc time	Make span
0	M1	1	LU	LU	0	0	0	0	3	12	15
3	M4	2	LU	LU	0	0	0	0	6	12	18
1	M1	1	M1	LU	3	0	9	15	15	36	51
4	M3	2	M4	LU	6	0	9	0	14	6	20
2	M3	2	M3	LU	14	0	18	20	23	18	41
0	M2	1	M1	M1	15	15	15	0	18	24	42
3	M2	1	M2	M4	18	18	22	42	42	30	72
1	M3	2	M3	M1	23	51	51	41	55	12	67
4	M1	1	M2	M3	42	20	45	51	51	18	69
1	M2	1	M1	M3	51	67	67	72	72	30	102
2	M4	2	M3	M3	55	41	55	18	58	6	64
2	M1	2	M4	M4	58	64	64	69	69	24	93
0	M4	1	M2	M2	72	42	72	64	76	18	94

The table above illustrates the completion time achieved using the hybrid beam search algorithm.

Table 5. Performance strategies and improvement.

Job. No	SPT	Gupta	Jaya	BS DE	% of Improvement
4.20	312	340	116	114	198.25
4.30	317	339	117	114	197.37
4.10	328	352	123	119	195.80
4.40	336	353	127	162	177.95
1.40	255	277	124	124	123.39
1.30	239	271	122	122	122.13
9.40	379	388	182	175	121.71
1.10	248	279	126	126	121.43
1.20	238	272	123	123	121.14
3.40	330	303	162	151	118.54
3.10	327	299	158	150	118.00
9.10	367	382	182	176	117.05
9.20	355	372	179	173	115.03
3.20	311	285	154	145	114.48
9.30	356	373	180	174	114.37
3.30	312	284	146	146	113.70
5.40	197	216	102	122	111.76
5.30	181	208	99	99	110.10
5.10	190	213	102	102	108.82
5.20	180	207	100	100	107.00
10.40	445	430	271	240	85.42
7.40	251	240	144	137	83.21
10.10	429	420	262	238	80.25
10.30	426	419	260	237	79.75
10.20	423	416	255	236	79.24
7.10	240	233	137	137	75.18
7.30	221	217	137	137	61.31
7.20	218	216	136	136	60.29
6.40	288	270	205	184	56.52
6.10	281	267	200	186	51.08
2.40	221	224	149	178	50.34
2.10	217	217	148	148	46.62
6.20	260	243	187	181	43.65
6.30	261	244	199	182	43.41
2.20	194	200	143	143	39.86
2.30	197	203	146	146	39.04
8.40	343	343	293	293	17.06
8.10	338	338	292	292	15.75
8.20	319	319	287	287	11.15
8.30	320	320	288	288	11.11

Figure 5. Load balancing of AMRs.

Figure 6. Load balancing of SMPs.

Figure 7. Comparative results of multi-processor.

Table

	SPT	Gupta	Jaya	BS DE
Mean	291.25	294.8	171.58	168.08
Std. deviation	73.74	70.31	59.93	55.3
Minimum	180	200	99	99
Maximum	445	430	293	293
Range	265	230	194	194

Table

Null hypothesis	Alternative hypothesis
There is no difference between the dependent variables SPT, Gupta, Jaya and BS DE.	There is a difference between the dependent variables SPT, Gupta,Jaya and BS DE.

Table

	Type III sum of squares	df	Mean squares	F	p	η^2
Treatment	607626.65	3	202542.22	170.85	<.001	0.81
Residual	138704.85	117	1185.51	–	–	–

Table

		Mean diff	Std. Error	p	95% CI lower limit	95% CI upper limit
SPT	Gupta	−3.55	2.912	−1.219	1	−9.44	2.34
SPT	Jaya	119.68	8.708	13.744	<.001	102.06	137.29
SPT	BS DE	123.18	9.238	13.333	<.001	104.48	141.87
Gupta	Jaya	123.23	9.421	13.079	<.001	104.16	142.29
Gupta	BS DE	126.73	9.668	13.107	<.001	107.17	146.28
Jaya	BS DE	3.5	1.939	1.805	.473	−0.42	7.42

Table

Model	df	F	p
Regression	3	430.9	<0.001

Data availability statement

The original contributions presented in the study are included in the article; further inquiries can be directed to the corresponding author.