Co esponding au ho : Sundus Al ai ou i
Copy igh © 2025 Au ho (s) e ain he copy igh o his a icle. This a icle is published unde he e ms o he C ea i e Commons A ibu ion Liscense 4.0.
Compa a i e Analysis o Heu is ic Rules o Flow Shop Scheduling Using ANOVA
Sundus Al ai ou i
Depa men o Indus ial and Manu ac u ing Sys em Enginee ing, Facul y o Enginee ing, Uni e si y o Benghazi,
Benghazi, Libya.
Wo ld Jou nal o Ad anced Resea ch and Re iews, 2025, 27(02), 2084-2094
Publica ion his o y: Recei ed on 18 July 2025; e ised on 26 Augus 2025; accep ed on 28 Augus 2025
A icle DOI: h ps://doi.o g/10.30574/wja .2025.27.2.3048
Abs ac
This pape compa es he pe o mance o i e heu is ic ules wi h he objec i e o minimizing he makespan ime. The
selec ed heu is ics a e namely SAI, Palme , Gup a, RA and CDS. The heu is ics a e es ed on wel e low shop p oblems
o di e en sizes using a MATLAB p og am. The compa ison was made by using he Analysis o Va iance (ANOVA) unde
Comple ely Randomized Block Design (CRBD), whe e he p oblem size was conside ed as a blocking ac o and he
heu is ic ule as he main ac o . Makespan ime was used as he esponse a iable, wi h a signi icance le el o α = 0.05.
The indings indica ed signi ican di e ences be ween he CDS, SAI, and Palme heu is ics, as he mean makespan
achie ed by he CDS heu is ic is lowe han ha o he SAI and Palme heu is ics, while i s pe o mance was no
signi ican ly di e en om ha o RA and Gup a.
Keywo ds: Flow shop scheduling; Heu is ics; Makespan; ANOVA
1. In oduc ion
P oduc ion Scheduling is a undamen al decision-making p ocess in manu ac u ing and ope a ions managemen . I
in ol es alloca ing a ailable esou ces (machines, wo ke s, ma e ials) o e ime o pe o m a collec ion o asks (jobs,
ope a ions) o op imize one o mo e objec i es while sa is ying cons ain s [ .1 ]
Scheduling p oblems a e cha ac e ized by machine layou s: single machine, iden ical pa allel machines, low shops and
job shops [.2 ]
Flow Shop Scheduling (FSS) ep esen s one o he mos impo an and widely s udied machine en i onmen s wi hin
p oduc ion scheduling. I models p oduc ion sys ems whe e a se o n jobs mus be p ocessed sequen ially on a se o m
machines (o s ages) in he same echnological o de [ .3 ]
Gene ally, he e a e wo classes o me hods o sol ing low shop scheduling p oblem (FSSP); exac and heu is ic
me hods. The i s -class me hods include: in ege p og amming, dynamic p og amming, b anch and bound, e c. Ano he
class is called heu is ic algo i hms such as Gup a, Palme , CDS, RA, SAI, e c. Al hough hose me hods do no gua an ee
he inding o an op imal solu ion, hose ha e been epo ed use ul in sol ing many challenging op imiza ion p oblems
wi hin a easonable compu a ional ime.
The main objec i e o FSSP is o de e mine he bes machine schedule o do all job wi h he bes objec i e alue, i.e.,
minimizing makespan (Cmax), mean low ime, mean a diness, ea liness, maximum la eness, e c.
Fo sol ing FSSP wi h he objec i e o minimizing makespan, se e al esea che s ha e epo ed he obus ness o
heu is ic me hods. These include Gup a and Ali [4], Gup a and Chauhan [5], Sya i e . al. [3], Sule [6], Dannenb ing [7],
Wo ld Jou nal o Ad anced Resea ch and Re iews, 2025, 27(02), 2084-2094
2085
Nawaz e al. [8], Gup a [9] and so on. Despi e hese in e es s, howe e , no esea che said he bes me hod o sol e FSSP
all- ime op imally. This ac shows ha esea ches on he pe o mance e alua ion o he heu is ic ules o FSSP a e
e y c ucial.
P e ious esea ch has consis en ly compa ed heu is ic pe o mance o low shop scheduling. Fo ins ance, Hossain S.
e al. [10] applied he Palme , CDS, and NEH heu is ics o a 4-job and 10-machine p oblem aimed a makespan
minimiza ion. In e es ingly, all h ee me hods yielded iden ical esul s o his speci ic ins ance. In a mo e a ge ed
compa ison o small-scale p oblems (5 jobs, 5 machines), Rayhan and Chakma [11] ound ha he NEH heu is ic
ou pe o med bo h Palme 's and CDS's me hods by a ma gin o 3–5%. Scaling up he analysis, Gup a & Chauhan [5]
de eloped a weigh age-based heu is ic es ed on la ge-scale Tailla d benchma ks (up o 500 jobs). Thei app oach
educed he a e age makespan gap o bes -known solu ions by 8%, demons a ing supe io pe o mance o e he
Palme , CDS, and RA heu is ics.
While hese s udies p o ide aluable pai wise compa isons, a signi ican gap emains in he applica ion o obus
s a is ical me hods o mul i-heu is ic e alua ion. This pape is mo i a ed by he no able absence o Analysis o Va iance
(ANOVA) in his con ex . ANOVA o e s a c i ical ad an age: i e icien ly manages compa isons ac oss mul iple
heu is ics while accoun ing o he inhe en a iabili y in oduced by di e en p oblem ins ances. This me hodology
con ols s a is ical e o a es and, when combined wi h pos -hoc es s, p o ides a igo ous ounda ion o iden i ying
uly supe io algo i hms. We a gue ha his leads o mo e eliable, objec i e, and insigh ul conclusions on algo i hmic
pe o mance, which a e essen ial o bo h ad ancing esea ch and guiding p ac ical implemen a ion.
1.1. P oblem S a emen
The assump ions ega ding FSSP in his s udy a e gene al and common in na u e. The same a e adap ed om Bake
[12], Ruiz and Ma o o [13] and o he s.
• Each job i can be p ocessed a mos on one machine j a he same ime.
• Each machine m can p ocess only one job i a a ime.
• No p eemp ion is allowed, i.e. he p ocessing o a job i on a machine j canno be in e up ed.
• All jobs a e independen and a e a ailable o p ocessing a ime 0.
• The se -up imes o he jobs on machines a e al eady included wi hin he p ocessing imes.
• The machines a e con inuously a ailable.
• In-p ocess in en o y is allowed. I he nex machine on he sequence needed by a job is no a ailable, he job
can wai and joins he queue a ha machine.
• All machines p ocess jobs in he same o de (pe mu a ion low shops).
2. Heu is ic Rules o FSSP
In his sec ion, he selec ed heu is ic algo i hms o sol ing low shop scheduling p oblem a e p esen ed.
2.1. SAI Heu is ic
SAI me hod is used o ame a sequence o jobs o p ocessing he n-jobs on m-machines in such a way ha he o al
elapsed ime is minimized. The s eps o his me hod, as s a ed by Gup a and Ali [4], a e as ollow:
• S ep 1: Examine he jobs and selec he leas job p ocessing ime among all n jobs o each machine and hen
ma ked i wi h (−) sign
• S ep 2: Simila ly, selec he leas p ocessing ime among all m machines o each job and hen ma ked i wi h
(+) sign .
• S ep 3: Again, examine he ows and columns o able, selec he cell wi h (∓) sign and is placed in he op imal
job sequence .
• S ep 4: S ep 1 o 3 a e epea ed un il all he jobs a e placed in he op imal job sequence .
The e may be a si ua ion whe e a ie has occu ed :
• I (∓) occu s a mo e han one place, hen he job wi h leas p ocessing ime is selec ed and is placed in he
op imal job sequence .
Wo ld Jou nal o Ad anced Resea ch and Re iews, 2025, 27(02), 2084-2094
2086
• I (∓) occu s a mo e han one place and he p ocessing ime o he alloca ed jobs is same. Then he job which
will p ocess on he lowe o de posi ional machine is selec ed ha is by igno ing he o he highe o de o
machines .
S ep 5: Las ly, we calcula e he ideal ime and o al elapsed ime o machines.
2.2. Palme ’s Heu is ic
To minimize he makespan in s a ic low shop, palme has de eloped a heu is ic which is known as he Palme ’s
Heu is ic. This heu is ic ule some imes gi es op imal solu ion (Makespan) bu no gua an ee o gi e op imal solu ion
o all he ime. Palme has de eloped a concep o slope o compu e he op imum makespan and job sequence in low
shop. Based on his slope (Aj), his heu is ic can e alua e only one op imal sequence o job.
Palme heu is ics comp ises wo ollowing s eps (Sya i e . al. [3]):
S ep1: I he numbe o jobs is n and machine is m, hen he slope Aj o j h job is compu ed as ollows;
𝐴𝑗=∑{𝑚−(2𝑖−1)}𝑃𝑖𝑗
𝑚
𝑖=1
Whe e, 𝑃𝑖𝑗 deno es he p ocessing ime o he job.
S ep 2: Jobs a e a anged in he sequence acco ding o hei descending (dec easing) o de o slope Aj alue.
2.3. CDS Heu is ic
The me hod gene a es m - 1 sequences, one o each alue o I, whe e i = 1,2,...m-1. om which he bes is chosen. The
sequence numbe 1 is cons uc ed by sol ing a wo-machine p oblem using Johnson's ule whe e he wo pseudo ac o s
Ail and Bil a e gene a ed using he ollowing exp essions (Sule [6]):
𝐴𝑖𝑙 =∑𝑃𝑖.𝑗
𝑙
𝑗=1 , 𝐵𝑖𝑙 =∑𝑃𝑖,𝑚−𝑗+1
𝑙
𝑗=1
𝐴𝑖𝑙: The sum o p ocessing imes o job 𝑖 on machines om 1 o j.
𝑃𝑖.𝑗 : is he p ocessing ime o job 𝑖 on machine j.
𝐵𝑖𝑙: The sum o p ocessing imes o job 𝑖 on machines om 𝑚 down o 𝑚 – j +1.
𝑃𝑖,𝑚−𝑗+1 ∶ is he p ocessing ime o job 𝑖 on machine 𝑚 – j +1 coun ed in e e se o de .
The s eps o Johnson's ule a e desc ibed as ollowing (Johnson [14]):
S ep 1: Fi s o all, he di e en p ocessing imes o all di e en jobs a e assigned o bo h machines.
S ep 2: The leas /smalles p ocessing imes o each job om all he jobs is no iced and i he minimum p ocessing ime
o he pa icula job is on machine 1, hen he job is pu in o he i s sequence o he wise i he minimum p ocessing
ime is on machine 2, hen i is pu in o he las place o he sequence.
S ep 3: The selec ed job is hen emo ed om he sequence.
S ep 4: Then again, he minimum p ocessing ime o any job om he lis o jobs is de ec ed and i he leas p ocessing
ime is on machine 1, and hen i is pu acco dingly in he second posi ion i he p e ious job is in is posi ion o in he
i s posi ion i he p e ious job is in las posi ion. While i he leas p ocessing Ume is on machine 2, hen i is pu
acco dingly in he las posi ion i he p e ious Job is in he i s posi ion o he wise in he second las posi ion.
S ep 5: Acco dingly, all he jobs a e sequenced in he abo e-men ioned p ocedu e.
Wo ld Jou nal o Ad anced Resea ch and Re iews, 2025, 27(02), 2084-2094
2087
2.4. Gup a’s Heu is ic
Gup a hough a ansi i e job o de ing in he o m o ollows ha would p oduce good schedules (Gup a [9]). Whe e m
> 3, a ange he jobs in descending o de o he Sj.
Whe e:
jm is he p ocessing ime o job j on machine m.
2.5. Rapid Access (RA) Heu is ic
The Rapid Access P ocedu e (RA), as p esen ed by Dannenb ing [7], uses a weigh ing scheme simila o ha o he
Slope O de and Campbell, Dudek and Smi h me hods. A single, wo-machine subp oblem is o med whe e he
p ocessing imes a e de e mined om he weigh ing scheme, and he subp oblem is sol ed using Johnson’s wo-
machine algo i hm.
The weigh ing scheme chosen was selec ed o i s simplici y.
Whe e 𝑡𝑖𝑗 is he p ocessing ime o he 𝑖𝑡ℎ job on he 𝑗𝑡ℎ machine in he main p oblem, and 𝑝𝑖𝑗 is he subp oblem
p ocessing ime o he 𝑖𝑡ℎ job on he 𝑗𝑡ℎ machine (𝑖 = 1, 2, ..., n and j = 1, 2).
𝑃𝑖1 =∑(𝑚−𝑗+1)𝑡𝑖𝑗′ 𝑝𝑖2 = ∑(𝑗)𝑡𝑖𝑗
𝑚
𝑗=1
𝑚
𝑗=1 .
S ep 1: Calcula e U = { i│Pi1’ < Pi2’ } and V = { i│Pi1’ ≥ Pi2’ }
S ep 2: So jobs in U wi h ascending o de o Pil’.
S ep 3: So jobs in V wi h descending o de o Pil’.
S ep 4: Op imal sequence is ob ained as schedule S by U and V. S={U,V}
3. Resul s
3.1. Compu a ional Resul s
To e alua e and compa e he pe o mance o heu is ic ules, wel e FSSP ( om able1 o able 12), we e sol ed by using
i e heu is ics namely SAI, Palme , Gup a, RA and CDS. Table 13 summa izes he esul s by p esen ing he makespan
(Cmax) o each p oblem by using he selec ed heu is ic ules.
Table 1 P oblem 1 (3jobs and 3machines)
MC/Jobs
1
2
3
M1
4
3
6
M2
6
7
2
M3
2
1
5
Wo ld Jou nal o Ad anced Resea ch and Re iews, 2025, 27(02), 2084-2094
2088
Table 2 P oblem 2 (4jobs and 3machines)
MC/ Jobs
1
2
3
4
M1
6
8
3
4
M2
5
1
5
4
M3
4
4
4
2
Table 3 P oblem 3 (5jobs and 3machines)
MC/Jobs
1
2
3
4
5
M1
3
8
7
5
2
M2
3
4
2
1
5
M3
5
8
10
7
6
Table 4 P oblem 4 (3jobs and 4machines)
MC / Jobs
1
2
3
M1
20
19
20
M2
20
19
20
M3
5
1
5
M4
5
2
5
Table 5 P oblem 5 (4jobs and 4machines)
MC / Jobs
1
2
3
4
M1
20
17
21
25
M2
10
7
8
5
M3
9
15
10
9
M4
20
17
21
25
Table 6 P oblem 6 (5jobs and 4machines)
MC / Jobs
1
2
3
4
5
M1
7
11
2
14
18
M2
15
18
13
4
11
M3
14
18
11
27
32
M4
21
6
16
14
16
Table 7 P oblem 7 (3jobs and 5machines)
MC/Job
1
2
3
M1
6
5
4
M2
4
5
3
M3
1
3
4
Wo ld Jou nal o Ad anced Resea ch and Re iews, 2025, 27(02), 2084-2094
2089
M4
2
4
5
M5
8
9
7
Table 8 P oblem 8 (4jobs and 5machines)
MC/Job
1
2
3
4
M1
6
5
4
7
M2
4
5
3
2
M3
1
3
4
2
M4
2
4
5
1
M5
8
9
7
5
Table 9 P oblem 9 (5jobs and 5machines)
MC/Job
1
2
3
4
5
M1
5
9
9
4
3
M2
9
3
4
8
5
M3
8
10
5
8
6
M4
10
1
8
7
3
M5
1
8
6
2
7
Table 10 P oblem 10 (4jobs and 6machines)
MC/Job
1
2
3
4
M1
15
17
21
18
M2
8
7
7
6
M3
6
9
12
11
M4
14
10
9
12
M5
6
15
11
14
M6
26
22
19
17
Table 11 P oblem 11 (5jobs and 6machines)
MC/Job
1
2
3
4
5
M1
1
5
5
1
1
M2
5
75
75
5
5
M3
5
1
5
5
5
M4
5
1
5
5
5
M5
1
5
2
1
1
M6
2
3
3
1
1
Wo ld Jou nal o Ad anced Resea ch and Re iews, 2025, 27(02), 2084-2094
2090
Table 12 P oblem 12 (6jobs and 6machines)
MC/ Job
1
2
3
4
5
6
M1
12
25
10
15
20
18
M2
18
10
20
12
15
22
M3
22
14
25
30
10
12
M4
15
30
12
20
25
10
M5
20
12
18
10
15
25
M6
10
18
15
25
12
20
Table 13 Compa a i e esul s o he makespan.
P oblem size (n*m)
Algo i hm
3*3
4*3
5*3
3*4
4*4
5*4
3*5
4*5
5*5
4*6
5*6
6*6
SAI
23
30
42
89
122
133
38
45
65
134
181
213
Palme
24
26
43
82
122
130
39
45
61
133
181
223
Gup a
24
26
42
82
122
127
38
43
64
133
178
216
RA
24
27
42
82
122
127
38
43
58
133
182
214
CDS
23
26
42
82
122
123
38
43
59
133
176
212
I can be no iced ha he minimum makespan can be achie ed by mo e han one heu is ic ule. Also, CDS p oduced he
minimum makespan o almos all he p oblems, bu i could no be conside ed as he bes heu is ic un il a s a is ical
es was made o ensu e ha he di e ences be ween he heu is ics a e s a is ically signi ican and no om a chance
o andom e o .
3.2. The Analysis o Va iance
3.2.1. The s a is ical model and hypo hesis
Randomized Comple e Block Design (RCBD) was used o compa e he pe o mance o he selec ed heu is ics by
conside ing he size o p oblems used in he es as a blocking ac o . Tha would sepa a e he a iance be ween
di e en p oblems' size (blocking e ec ) om he a iance be ween heu is ics. This educes noise and p o ides a
clea e pic u e o ue heu is ics di e ences. The s a is ical model o he RCBD can be w i en in se e al ways. The
adi ional model is an e ec s model:
yij = µ + τi + βj + ɛij
Whe e µ is an o e all mean, τi is he e ec o he i h heu is ic algo i hm, βj is he e ec o he j h p oblem ins ance, and
ɛij is he usual NID (0, σ2) andom e o e m. [i=1,2,…,5 and j=1,2,….,12].
In RCBD, we a e in e es ed in es ing he equali y o he ea men means. Thus, he hypo heses o in e es a e:
H0: µ1 = µ2 = µ3 = µ4 = µ5
H1: a leas one µi ≠ µj
3.2.2. Model adequacy checking
The use o ANOVA equi es ha ce ain assump ions be sa is ied. Speci ically, hese assump ions a e ha he
obse a ions a e adequa ely desc ibed by he model and ha he e o s a e no mally and independen ly dis ibu ed
wi h mean ze o and cons an bu unknown a iance. I hese assump ions a e alid, he analysis o he a iance
p ocedu e is an exac es o he hypo hesis o no di e ence in ea men means.
Wo ld Jou nal o Ad anced Resea ch and Re iews, 2025, 27(02), 2084-2094
2091
In o de o check hese assump ions, plo s o esiduals a e cons uc ed using Mini ab17. Figu e 1 shows he no mal
p obabili y plo o hese esiduals. The gene al imp ession om examining his display is ha he e o dis ibu ion is
app oxima ely no mal.
A plo o esiduals e sus heu is ic ules is shown in Figu e 2. The e is no eason o suspec any iola ion o he
independence o cons an a iance assump ions (see igu es 2 and 3).
Figu e 1 No mal p obabili y plo o esidual.
Figu e 2 Plo o esidual e sus heu is ic algo i hm.
Wo ld Jou nal o Ad anced Resea ch and Re iews, 2025, 27(02), 2084-2094
2092
Figu e 3 Plo o esidual e sus obse a ion o de .
3.2.3. Resul s o ANOVA
Table 14 p esen s he esul s o he analysis o a iance, om hese esul s i can be concluded ha he e is a signi ican
di e ence be ween he heu is ic ules co e ed by his s udy, since he mean makespan o hese heu is ics di e
signi ican ly (p- alue = 0.003 less han 0.05).
Table 14 The esul s o ANOVA.
Sou ce o
a ia ion
Deg ees o
eedom
Sum o
squa es
Mean o
squa es
F0
P- alue
Heu is ic ule
4
63
15.4
4.62
0.003
P oblem size
11
221274
20115.8
6018.33
E o
44
147
3.3
To al
59
221483
A pos -hoc analysis (Tukey’s es ) was conduc ed o de e mine which heu is ics di e ed om each o he . The indings
indica ed ha he CDS heu is ics is signi ican ly di e en om he SAI and Palme heu is ics bu does no di e
signi ican ly om he RA and Gup a heu is ics (see Table 15).
Table 15 G ouping in o ma ion using he Tukey me hod and 95% con idence.
Heu is ic algo i hm
N
Mean
G ouping
SAI
12
92.91
A
Palme
12
92.17
A
Gup a
12
91.25
A
B
RA
12
91.00
A
B
CDS
12
89.91
B
4. Discussion
Resul s o he p esen s udy p o ide a s a is ically sound compa ison be ween i e heu is ic ules (SAI, Palme , Gup a,
RA and CDS) o low shop makespan. Based on he indings ha he CDS heu is ics is signi ican ly di e en om he
SAI and Palme heu is ics bu do no di e signi ican ly om he RA and Gup a heu is ics. While he p esen s udy
e eals signi ican pe o mance a ia ions, ea lie esea ch by Hossain e .al. [10] ound Palme , CDS, and NEH equally
