A new composi e heu is ic o minimize he o al a diness o he single
machine scheduling p oblem wi h a iable and lexible main enance
An onio Cos a
a,*
, Robe o Rosa io Co sini
a
, Daniele Pagano
b
, Vic o Fe nandez-Viagas
c
a
DICAR Depa men , Uni e si y o Ca ania, Viale And ea Do ia 6, 95125 Ca ania, I aly
b
STMic oelec onics - S adale P imosole, 50, 95121 Ca ania, I aly
c
Uni e si y o Se ille, Depa men o Indus ial O ganiza ion and Business Managemen I, School o Enginee ing, Camino Descub imien os s/n, 41092 Se illa, Spain
ARTICLE INFO
Keywo ds:
Linea p og amming
Op imiza ion
P e en i e main enance
Se up imes
Release imes
ABSTRACT
Inspi ed by a eal-wo ld main enance/job scheduling issue coming om he semiconduc o indus y, he p esen
pape p oposes a new heu is ic algo i hm s uc u e o he single machine scheduling T-p oblem wi h lexible
and a iable main enance, job elease da es and sequence dependence se up imes. Conside ing he ypical sho -
e m p oduc ion planning needs, a single main enance p oblem has o be scheduled wi hin a ce ain ime in-
e al, along wi h a se o jobs so as o minimize he o al a diness. A wo old con ibu ion eme ges om he
p esen pape . Fi s , ou mixed-in ege linea p og amming models a e de eloped o he p oblem a hand and
compa ed in e ms o ime o con e gence and compu a ional complexi y. Second, a no el heu is ic algo i hm,
which has been con igu ed in o h ee dis inc a ian s, has been compa ed wi h 17 al e na i e heu is ics om he
ele an li e a u e based on a comp ehensi e expe imen al campaign. The nume ical esul s allow he selec ion
o he mos sui able MILP model and con i m he e ec i eness o he p oposed heu is ic app oach.
1. In oduc ion
In p oduc ion scheduling heo y, machines a e usually conside ed
a ailable p oduc ion esou ces. Howe e , hey o en need o be a bi-
a ily s opped because o p e en i e main enance ope a ions.
Add essing scheduling p oblems while being una ailable he p oduc ion
esou ces is a demanding issue ha has cap u ed he a en ion o bo h
academics and indus ial s akeholde s (Ma e al., 2010). Ac ually,
se e al kinds o main enance ac i i ies may be accomplished on he
manu ac u ing esou ces, such as cleaning, ool eplacemen , e illing,
echa ging, and o he planned ac i i ies ha make any job p ocessing
empo a ily blocked (Luo e al., 2015).
Whene e a main enance ac i i y and a se o jobs ha e o be
scheduled, wo p ima y in o ma ion a e needed, i.e., s a ing ime and
du a ion. None heless, mo i a ed by a mo e ealis ic pe spec i e, se e al
s udies cope wi h he scheduling p oblem wi h lexible main enance, in
which he main enance s a ing ime may all wi hin a ce ain ime
ange. In some eal-wo ld p oduc ion con ex s, he wo king condi ions
may bias he du a ion o he main enance ac i i y, which becomes a
a iable o he scheduling p oblem. Beyond he conside a ions o
s a ing ime and du a ion o p e en i e main enance, a wo old
esea ch s eam can be de ec ed in he li e a u e ha deals wi h he opic
a hand. The o me s udies he p oblem o scheduling jobs wi h a single
p e en i e main enance, while he la e conside s mul iple una ail-
abili y in e als, i.e., pe iodic main enance ac i i ies along he ime
ho izon. Al hough mos ecen s udies in es iga e scheduling p oblems
wi h pe iodic main enance, we belie e ha scheduling jobs wi h a single
main enance ac i i y simul aneously s ill cons i u e a alid challenge,
ypical o many eal-li e scena ios whe e he ime leng h o he machine
una ailabili y is consis en wi h he sho - e m planning ho izon. To
u he mo i a e he scien i ic alidi y o his issue, he seminal wo k o
Qi e al. (1999) demons a es ha e en minimizing he o al comple ion
ime o a single machine scheduling p oblem wi h p e en i e main e-
nance is NP-ha d in he s ong sense.
In his ega d, he p esen pape add esses he single machine
scheduling p oblem wi h a single una ailabili y in e al due o a lexible
and a iable p e en i e main enance ope a ion. I has been inspi ed by
a eal-li e semiconduc o manu ac u ing p oblem conce ning he silicon
ca bide (SiC) epi axial deposi ion, whe e a chemical apo deposi ion
(CVD) me hod is usually used o deposi a laye o single c ys al on he
wa e o o m an epi axial wa e . E e y week a highly skilled wo ke has
o accomplish a lexible and a iable main enance ope a ion. B ie ly, i
consis s o a wo old ime-consuming ac i i y: 1) s opping he eac o
and wai ing un il oom empe a u e and a mosphe ic p essu e in he
* Co esponding au ho .
E-mail add ess: [email p o ec ed] (A. Cos a).
Con en s lis s a ailable a ScienceDi ec
Compu e s and Ope a ions Resea ch
jou nal homepage: www.else ie .com/loca e/co
h ps://doi.o g/10.1016/j.co .2024.106849
Recei ed 21 No embe 2023; Recei ed in e ised o m 1 Augus 2024; Accep ed 8 Sep embe 2024
Compu e s & Ope a ions Resea ch 173 (2025) 106849
A ailable online 14 Sep embe 2024
0305-0548/© 2024 The Au ho (s). Published by Else ie L d. This is an open access a icle unde he CC BY-NC-ND license ( h p://c ea i ecommons.o g/licenses/by-
nc-nd/4.0/ ).
chambe a e achie ed; 2) mechanical cleaning o he chambe o a ime
anging in 2–3 h.
Since he machine a hand is dedica ed o high added- alue p oduc s
o op clien s, and he cus ome demand exceeds he p oduc ion
capabili y, an e ec i e scheduling s a egy is equi ed o minimize he
o al a diness. The e o e, he p oblem unde in es iga ion can be
con igu ed as a single machine scheduling p oblem wi h a lexible-
a iable main enance o be execu ed wi hin a speci ic ime window,
also including sequence dependen se up imes and non-ze o elease
imes, wi h he objec i e o minimize he o al a diness. Such a kind o
p oblem is s ongly NP-ha d as i can be educed o 1 j∑Tj o
1sij∑Tj, bo h o which a e s ongly NP-ha d (Lawle e al., 1982).
Compa ed wi h p e ious esea ch, he leading con ibu ions o he
p esen s udy a e he ollowing:
i) Th ee dis inc mixed-in ege linea p og amming models a e p o-
posed and compa ed in e ms o ime o con e gence and gap om
he op imali y.
ii) A new heu is ic algo i hm con igu ed in h ee dis inc a ian s is
de eloped and es ed by means o an ex ended expe imen al analysis
in ol ing 17 heu is ics om he ele an li e a u e.
Fo he sake o cla i y, he p esen pape can be con igu ed as he
de elopmen o ano he esea ch by Cos a and Fe nandez-Viagas
(2022), whe e he same single machine scheduling p oblem was in es-
iga ed by p oposing a MILP model and a modi ied ha mony sea ch
algo i hm.
The emainde o his pape is a anged as ollows. Sec ion 2 analyzes
he li e a y backg ound. Sec ion 3 p esen s he p oblem s a emen while
he ela ed MILP models a e in Sec ion 4. Sec ion 5 allows assessing he
compu a ional complexi y o he p oposed MILP models. The p oposed
heu is ic algo i hms a e in oduced in Sec ion 6. The way he es cases
ha e been cons uc ed is explained in Sec ion 7. Sec ion 8 p esen s and
discusses he nume ical esul s a ising om an ex ended expe imen al
campaign. Sec ion 9 epo s he inal conclusions on he esea ch wo k.
2. Re iew o li e a u e and con ibu ions
Two esea ch s eams on he single machine scheduling p oblem
wi h lexible- a iable p e en i e main enance (SMFVM) may be iden-
i ied in he li e a u e. The o me deals wi h a kind o p oblem whe e a
single main enance ac i i y mus be scheduled along wi h a se o jobs.
The la e ocuses on scheduling mul iple main enance ac i i ies on a
single machine o e a wide ime ho izon; hus, main enance ac i i ies
a e sp ead ou o e a longe ime ho izon (weeks, mon hs, yea s) ha , in
some cases, may esul inconsis en wi h he needs ypical o he sho -
e m p oduc ion planning. Mo i a ed by hese conside a ions, he li -
e a y backg ound is e iewed unde a wo old pe spec i e. Fi s , he
con ibu ions on he single machine scheduling p oblem wi h a single
main enance ac i i y a e explo ed. Then, we e iew he li e a u e on he
single machine scheduling p oblem wi h pe iodic main enance asks.
As o he i s kind o p oblem, mos con ibu ions on he SMFVM
p oblem copes wi h he so-called basic p oblem in which no es ic ion
conce ning se up imes and/o elease imes occu s. In his con ex ,
many au ho s jus de eloped polynomial ime algo i hms o op imize
di e en u na ound o imeliness pe o mance measu es. Chen (2006)
p oposed se e al bina y mixed in ege p og amming models o mini-
mize he o al a diness in he p esence o a lexible main enance
ope a ion. Mosheio and Sa ig (2009) de eloped a pseudo-dynamic
p og amming model o sol ing he o al weigh ed comple ion ime
SMFM p oblem, hus demons a ing he NP-ha dness o he p oblem
unde in es iga ion. Mosheio and Sidney (2010) demons a ed ha in
he SMVM p oblem whe ein he main enance du a ion is a non-
dec easing unc ion o he s a ing ime, some objec i es such as
makespan, low ime, maximum la eness, and numbe o a dy jobs, can
be op imally sol ed in a polynomial ime. Conside ing he single ma-
chine p oblem wi h a iable main enance o be s a ed ea lie han a
ce ain dead-line, Low e al. (2010) showed ha he o al weigh ed
comple ion ime is weakly NP-ha d and an app oxima e sol ing
app oach can be adop ed. La e , Luo e al. (2015) in es iga ed he same
scheduling p oblem and ound ou ha makespan, o al comple ion
ime, maximum la eness and numbe o a dy jobs can be op imized by
polynomial ime algo i hms. Luo and Ji (2015) add essed a a ian o
he p e ious scheduling p oblem wi h de e io a ing jobs and a iable
main enance, and p o ed ha bo h makespan and o al comple ion
imes can be minimized by ully polynomial ime app oxima ion
schemes. Some yea s la e , Luo and Liu (2017) de eloped a (2 +e)-
app oxima ion algo i hm o minimize he o al weigh ed comple ion
ime. De i e al. (2019) in oduced a u he es ic ion, i.e., a ime
window in which he a iable main enance ask mus be execu ed. The
mos ela ed esea ch co esponds o Cos a and Fe nandez-Viagas
(2022), which add esses he single machine scheduling p oblem wi h
a lexible- a iable main enance, and p opose a MILP model, se e al
heu is ics, and a modi ied ha mony sea ch.
Al hough se e al esea ch con ibu ions deal wi h he single ma-
chine scheduling p oblem wi h pe iodic main enance, i is wo h
poin ing ou ha all o hem ocus a kind o basic p oblem whe ein many
sou ces o complexi y such as sequence dependen se up imes, job
elease imes, and a iabili y o main enance ope a ions a e igno ed.
Sun and Geng (2019) cope wi h he op imiza ion o he o al
comple ion ime in he basic single-machine scheduling p oblem wi h
de e io a ing e ec s on he machine i sel , which can be esumed by a
p ope main enance ope a ion. Chen e al. (2020) es a se ies o as
heu is ics such as LPT, FFD, MW, LBI, o minimize makespan in a single-
machine scheduling p oblem wi h lexible main enance and non-
esumable jobs. Chen e al. (2021) in es iga e he single machine
scheduling p oblem in which bo h impe ec and pe ec main enance
ope a ions may be execu ed o minimize he o al a diness. They igno e
job elease imes and se up imes and, in case o ailu e, jobs will esume
a e epai wi h no ex a p ocessing ime. A simila s udy p oposes a
gene ic algo i hm o p oduc ion and main enance scheduling in a
deg ading mul i- ailu e modes single machine en i onmen (Sha i i and
Taghipou , 2021). Toua e al. (2022) p oposes a guided local sea ch
me aheu is ic o he single machine scheduling p oblem wi h lexible
main enance and human esou ce cons ain s wi h he aim o mini-
mizing a bic i e ia objec i e unc ion based on ea liness and a diness.
Yazdani e al. (2023) compa e di e en new me aheu is ic algo i hms
o he maximum ea liness and a diness minimiza ion in a single ma-
chine en i onmen whe e pe iodic main enance occu s. Penz e al.
(2023) in oduce wo mixed in ege p og amming models o minimize
he sum o comple ion imes in a single machine p oblem wi h job
amilies, machine de e io a ion, and lexible main enance ope a ions.
Speci ically, hey conside bo h he daily case p oblem in which he ime
ho izon is equal o one day and a single main enance mus be sequenced,
and he weekly case in which a mos wo main enance ope a ions ha e
o be scheduled. Con o ming o he p e ious con ibu ions, no elease
imes, a iable main enance, and se up imes a e included in he p ob-
lem complexi y.
3. P oblem s a emen
In he single machine scheduling p oblem unde in es iga ion a se o
n jobs (j =1,…,n) has o be p ocessed on a single machine, wi h p
j
being
he job p ocessing imes. P eemp ion is no allowed, and each job is
a ailable o be p ocessed a a di e en ime
j
. E e y job equi es an
a ached sequence dependen se up ime s
ij
. A p e en i e main enance
ask mus be accomplished wi hin a speci ic ime in e al [I
min
, I
max
],
known a-p io i. The main enance ac i i y is a iable so, he la e i s
s a ing ime, he longe i s du a ion. Howe e , bo h s a ing ime Z and
comple ion ime ZC o he main enance ac i i y (being Z<ZC) mus be
placed wi hin he allowed ime in e al. The main enance du a ion is
A. Cos a e al.
Compu e s and Ope a ions Resea ch 173 (2025) 106849
2
modelled as a combina ion o wo con ibu ions, he o me being a
cons an (γ), he la e a a iable λ = (Z), i.e., a posi i e non-dec easing
unc ion o he s a ing ime Z∈ [Imin,Imax]. In pa icula , he main e-
nance du a ion is designed as δ=γ+λ whe e λ=m• (Z−Imin)and m is
he slope o he linea unc ion. The objec i e unc ion is he o al
a diness T=∑n
j=1Tj, whe e Tj=max{0,Cj−dj}, being Cj and dj
comple ion ime and due da e o each job j, espec i ely. Acco ding o
he well-known h ee- ield classi ica ion ule (G aham e al., 1979), he
p oblem a hand can be coded as 1| j,sij,n , m, m|∑Tj, whe e n means
non- esumable jobs while m and m a iable and lexible main enance,
espec i ely. F om now on, he single machine scheduling p oblem wi h
lexible and a iable main enance will be deno ed by SMFVM. Fu he
de ails on he p oblem s a emen as well as an illus a i e example can
be e ie ed in Cos a and Fe nandez-Viagas (2022). A lis o no a ions
use ul o he eade s a e in he ollowing:
4. MILP models
MILP modelling has been used o op imally sol e a se ies o small-
sized scheduling p oblems, wi h he aim o p o iding a obus alida-
ion suppo o he heu is ic algo i hms o be compa ed. Mo e speci -
ically, ou MILP models a e desc ibed in his sec ion and all o hem a e
based on he p ecedence-decision a ionale. This choice is mo i a ed by
he ac ha his app oach assu es a be e pe o mance in e ms o
con e gence o global op ima and compu a ional imes han he
posi ion-based scheme (also called sequence-posi ion), e en in mo e
challenging scheduling p oblems (Demi and ˙
Is¸leyen, 2013, Meng e al.,
2022). The i s model (he eina e deno ed as MILP1) consis s o he
MILP model p oposed by Cos a and Fe nandez-Viagas (2022). Then,
h ee new models we e de eloped as a modi ica ion o he o me one.
Hence, o he sake o b e i y, no a ion, pa ame e s, and decisions
a iables common o all models a e in he ollowing pa ag aphs. Table 1
holds no a ion and pa ame e s common o all models, e en hough he
las column allows de ec ing how a speci ic MILP model uses he job
indices. As o example, as conce ns se up imes sij, h ee ou o ou
MILP models make use o a job index i s a ing om ze o (dummy job),
while only MILP3 employs he job index i s a ing om one. Fu he -
mo e, only MILP3 needs o sepa a ely un he se up ime o he job
p ocessed as i s (i.e., aj). Table 2 allows ma ching each decision a i-
able wi h he di e en MILP models. In e es ingly, all MILP models wi h
excep ion o MILP3 use a dummy job (i =0) o he decision a iable Yij,
while MILP1 is he only model in which he main enance ope a ion is
handled as an addi ional job, so n +1 jobs a e conside ed when
compu ing s a ing and comple ion imes. As expec ed, he objec i e
unc ion o be minimized, i.e., he o al a diness, is common o all MILP
models:
Objec i e
Min ∑
n
j=1
Tj(1)
Since he p oposed SMFVM p oblem unde in es iga ion is inspi ed
o a eal-li e issue o a semiconduc o manu ac u e , i is wo hy o
desc ibe how he MILP model cap u es he p ac ical ea u es o such eal
issue. The ime window anging in [I
min
, I
max
] ep esen s he ime in-
e al in which he machine can be s opped, and a skilled ope a o can
clean he eac o ’s chambe . In he eal p ac ice, he ime window goes
om 8:00 am o 6:00 pm, so op imizing he main enance scheduling
issue would mean o place he ope a o ’s s a ing ime (Z) in way ha
he main enance comple ion ime is lowe han I
max
and he o al
a diness is minimized as well. As he main enance ask basically con-
sis s o a cleaning ope a ion, he main enance du a ion was modeled as
an inc easing unc ion o he main enance s a ing ime.
4.1. MILP 1
This ma hema ical model was p oposed by Cos a and Fe nandez-
Viagas (2022). Beyond he job a diness Tj, wo con inuous decision
a iables (Cj,Ej) and one bina y a iable Yij a e conside ed. Looking a
he no a ion, a dummy job 0 is included in he se o he p eceding jobs.
In addi ion, no e ha he main enance ac i i y is handled as an added
job (i.e., job n +1).
Subjec o:
∑
n+1
i=0
Yij =1,j=1,⋯,n+1 (2)
∑
n+1
j=1
Yij ≤1,i=0,1,⋯,n+1 (3)
∑
n
j=1
Y0j=1 (4)
Ej≥ j+∑
n
i=0
Yij,j=1,⋯,n(5)
Table 1
No a ions and pa ame e s common o all MILP models.
Pa ame e De ini ion Models and Indices
i,j job indices All
nnumbe o jobs All
p
j
p ocessing ime o job jAll:j=1,⋯,n
j
elease ime o job jAll:j=1,⋯,n
d
j
due da e o job jAll:j=1,⋯,n
I
min
ea lies s a ing ime o main enance
in e al
All
I
max
la es comple ion ime o main enance
in e al
All
γmain enance base ime All
mslope o he linea ela ionship ela ed o
he a iable main enance du a ion
All
Ma big numbe All
sij se up ime o job j p ocessed a e job iMILP1/2/4: i=0,1,⋯,
n; j=1,⋯,n
MILP3: i=1,⋯,n; j=
1,⋯,n
ajse up ime o job j in case i is p ocessed as
i s
MILP3:j=1,⋯,n
No e: i=0 is a dummy job.
Table 2
Decisions a iables common o all MILP models.
Va iable De ini ion Models and Indices
Yij ∈ {0,1}Bina y decision a iable: 1 i job j is
p ocessed immedia ely a e job i,
0 o he wise.
MILP1/2/4: i=0,1,
⋯,n; j=1,⋯,n
MILP3: i=1,⋯,n;
j=1,⋯,n
Xj∈ {0,1}Bina y decision a iable: i job j is p ocessed
a some ime be o e he main enance
in e al, 0 o he wise
MILP2/3/4:j=1,⋯,
n
Wj∈ {0,1}Bina y decision a iable: 1 i job j is
p ocessed immedia ely a e he
main enance in e al, 0 o he wise
MILP3/4:j=1,⋯,n
Vj∈ {0,1}Bina y decision a iable: 1 i job i is
p ocessed as las , 0 o he wise
MILP3:j=1,⋯,n
Ejs a ing ime o job jMILP1:j=1,⋯,n+1
MILP2/4:j=1,⋯,n
Cjcomple ion ime o job jMILP1:j=1,⋯,n+1
MILP2/3/4:j=1,⋯,
n
Tj a diness o job jAll:j=1,⋯,n
Zmain enance s a ing ime MILP2/3/4
Rmain enance du a ion MILP2/4
ZC main enance comple ion ime MILP3
No e: i=0 is a dummy job; job n +1 in MILP1 is he main enance in e al.
A. Cos a e al.
Compu e s and Ope a ions Resea ch 173 (2025) 106849
3
Ej≥ j+∑
n
i=0
sij •Yi(n+1)−M•(1−Y(n+1)j),j=1,⋯,n(6)
Ej≥Ci+sij −M•(1−Yij),i=1,⋯,n,j=1,⋯,n(7)
Ej≥C(n+1)+∑
n
i=0
sij•Yi(n+1)−M•(1−Y(n+1)j),j=1,⋯,n(8)
Cj≥Ej+pjj=1,⋯,n(9)
C(n+1)≥E(n+1)+γ+m•(E(n+1)−Imin )(10)
E(n+1)≥Cj−M•(1−Yij)j=1,⋯,n(11)
E(n+1)≥Imin (12)
C(n+1)≤Imax (13)
Tj≥Cj−djj=1,⋯,n(14)
Y(n+1)(n+1)=0 (15)
Cons ain (2) s a es ha each job mus ha e a p edecesso . Ac-
co ding o cons ain (3), each job can p ecede one o he job a mos .
Cons ain (4) se s a leas one job o be p ocessed be o e he main e-
nance in e al. Cons ain s (5) and (6) s a e ha each job can be p o-
cessed a e i is eleased o he sys em. Speci ically, cons ain (5) e e s
o he case ha he job is p eceded by a eal job, while cons ain (6)
wo ks in he case ha he job a i es immedia ely a e he main enance
in e al. Simila ly, cons ain s (7) and (8) impose each job o s a a e
he p eceding job is comple ed, in case he p eceding job is eal o i
coincides wi h he main enance in e al, espec i ely. Cons ain (9)
links s a ing and comple ion ime o each job. Cons ain (10) calcula es
main enance comple ion ime. Cons ain (11) calcula es main enance
s a ing ime. Cons ain s (12) and (13) ix bounds o main enance
s a ing and comple ion ime, espec i ely. Cons ain (14) calcula es
a diness o jobs. Cons ain s (15) impose he main enance in e al no
o p ecede i sel .
4.2. MILP 2
Subjec o:
∑
n
i=1
Yij =1j=1,⋯,n(16)
∑
n
j=1
Yij ≤1i=0,1,⋯,n(17)
∑
n
j=1
Xj≥1 (18)
Ej≥Z+R+∑
n
i=0
sij •Yij −M•Xjj=1,⋯,n(19)
Cj≤Z+M•(1−Xj)j=1,⋯,n(20)
Z≥Imin (21)
Z+R≤Imax (22)
R≥γ+m• (Z−Imin)(23)
Addi ional cons ain s: 5, 7, 9, 14.
Cons ain (16) s a es ha each job mus ha e a p edecesso . Ac-
co ding o cons ain (17), each job can p ecede one o he job a mos .
Cons ain (18) se s a leas one job o be p ocessed be o e he main e-
nance in e al. In case a job is p ocessed a e he main enance in e al,
cons ain (19) s a es ha i s s a ing ime mus ollow he main enance
comple ion ime. Cons ain (20) s a es ha i s comple ion ime mus
p ecede he main enance s a ing ime. Cons ain s (21) and (22) ix
bounds o main enance s a ing and comple ion ime, espec i ely.
Cons ain (23) calcula es main enance du a ion.
4.3. MILP 3
Subjec o:
∑
n
j=1
Yij =1−Vii=1,⋯,n(24)
∑
n
j=1
Yij =1−Wij=1,⋯,n(25)
Cj≥Ci+sij +pj−M•(1−Yij)i=1,⋯,n;j=1,⋯,n(26)
Cj≥( j+aj+pj)•Wjj=1,⋯,n(27)
Cj≥( j+sij +pj)•Yij i=1,⋯,n;j=1,⋯,n(28)
Cj≥ZC+(sij +pj)•Yij −M•Xji=1,⋯,n;j=1,⋯,n(29)
ZC ≤Imax (30)
ZC ≥Z+γ+m• (Z−Imin)(31)
∑
n
i=1
Vi=1 (32)
∑
n
j=1
Wj=1 (33)
Addi ional cons ain s: 14, 18, 20, 21.
Cons ain (24) s a es ha each job mus p ecede ano he job, unless
i is p ocessed as he las . Cons ain (25) s a es ha each job mus be
p eceded by ano he job, unless i is p ocessed as he i s . Cons ain
(26) imposes each job o s a a e he p eceding job is comple ed.
Cons ain s (27) and (28) s a e ha each job can be p ocessed a e i is
eleased o he sys em. Speci ically, cons ain (27) is e e ed o he case
he job p ocessed as i s , while cons ain (28) wo ks o he wise. In case
a job is p ocessed a e he main enance in e al, cons ain (29) s a es
ha i s s a ing ime mus ollow he main enance comple ion ime.
Cons ain (30) ixes bounds o main enance s a ing and comple ion
ime, espec i ely. Cons ain (31) calcula es main enance du a ion.
Cons ain s (32) and (33) impose one only job o be p ocessed as i s
and as las , espec i ely.
4.4. MILP 4
Subjec o:
∑
n
i=1
Xi=1 (34)
Ej≥Z+R+∑
n
i=0
sij •Yij −M•(1−Wj)j=1,⋯,n(35)
Wj≥Yij +Xi−1i=1,⋯,n;j=1,⋯,n(36)
Addi ional cons ain s: 3, 5, 7, 9, 14, 16, 20, 21, 22, 23.
Cons ain (34) se s exac ly one job o be p ocessed immedia ely
A. Cos a e al.
Compu e s and Ope a ions Resea ch 173 (2025) 106849
4
be o e he main enance in e al. Cons ain (35) s a es ha i s s a ing
ime mus ollow he main enance comple ion ime. Cons ain (36)
iden i ies he couple o jobs be ween which main enance is pe o med.
Table 3 shows he numbe o cons ain s as well as cons ain
equa ions ela ed o all MILP models.
5. Complexi y o MILP models
MILP models can be e alua ed and compa ed in e ms o size
complexi y and compu a ional complexi y (Demi and ˙
Is¸leyen, 2013).
To assess he size complexi y o he p oposed MILP models, numbe o
bina y a iables (NBVs), numbe o con inuous a iables (NCVs), and
numbe o cons ain s (NCs) can be aken on as indica o s. Table 4 al-
lows compa ing he size complexi y o he p oposed MILP models, by
dis inguishing be ween bina y and con inuous a iables. Al hough
MILP1 adop s only a bina y a iable Yij, i uses a numbe o NBVs highe
han models 2–4. Such inding can be mo i a ed by he ac ha , in
MILP1, he job indices o Yij ake on alues om ze o o (n +1).
Howe e , MILP3 has he highes NBVs, likely due o he ou bina y
a iables i needs. As o he con inuous a iables, MILP1 needs only
h ee a iables, bu i equi es he highes NCVs, such as models 2–4. On
he o he hand, MILP3 has he leas NCVs since i dis ega ds he job
s a ing imes Ej as independen a iables. In conclusion, i can be no ed
ha MILP2 is he model adop ing he leas NBVs, while MILP 3 has he
leas NCVs. As a u he insigh , i is wo h no ing ha MILP2 and MILP3
ha e he leas and he mos NCs, espec i ely.
To u he e alua e he MILP models om he size complexi y
iewpoin , Fig. 1 shows how NCs, NBVs, NCVs and he numbe o non-
ze o coe icien s (NZCs) as he p oblem size anges in s ep wo in [8, 16].
The choice o such p oblem sizes is mo i a ed by he i s pa o he
expe imen al analysis (See Sec. 8) in which all MILP models a e sol ed
by IBM ILOG CPLEX® V20.1 and compa ed in e ms o e icacy/e i-
ciency ela ed pe o mance indica o s. Fig. 1a) con i ms ha MILP2
makes use o he leas NCs, while MILP3 holds a ema kably highe
numbe o cons ain s. Fig. 1b) highligh s he e iciency o MILP2 in
e ms o NZCs. In gene al, educing he numbe o non-ze os coe icien s
can be pa icula ly use ul because he un- ime o many sub- ou ines in a
MIP sol e depends on his numbe . Unde he numbe o bina y a i-
ables iewpoin , no signi ican di e ence eme ges (Fig. 1c), e en hough
MILP 2 and MILP3 appea less in need o in ege a iables, which make
any model mo e complex and challenging o sol e. Ins ead, a no able
di e ence can be obse ed in Fig. 1d) as MILP3 assu es a signi ican ly
lowe NCVs han he o he models.
6. P oposed heu is ics
This sec ion ho oughly explains he h ee p oposed heu is ics
de eloped o sol e he SMFVM p oblem a hand. The i s heu is ic,
deno ed as BCH, is a cons uc i e heu is ic which ob ains a good solu-
ion in sho CPU ime. This heu is ic is explained in Sec ion 6.1. This
solu ion can be used as ini ial solu ion o mo e complex heu is ics and
me aheu is ics. In ac , his is he idea o ou second p oposal, deno ed as
composi e heu is ic NCH, and he basis o he las composi e heu is ic,
deno ed by MCH. Bo h heu is ics a e de ailed in Sec ions 6.2 and 6.3,
espec i ely. Finally, in Sec ion 6.4 we enume a e he heu is ics ha a e
eimplemen ed and adap ed o be compa ed wi h he p oposals.
6.1. Basic cons uc i e heu is ic, BCH
S a ing wi h he i s p oposal, BCH cons uc s a solu ion by
inse ing jobs, one by one, a he end o an ini ially emp y pa ial
sequence (Π). Once a job has been inse ed a he end o he sequence,
his job is emo ed om he se o unscheduled jobs, and a new job is
selec ed o be placed again a he end o he sequence. The p ocedu e is
epea ed un il n jobs ha e been placed and hen he e is no job in he se
o unsequenced jobs. In o de o selec he bes job in each i e a ion,
many ad ances ha e been achie ed in he li e a u e by using ailo ed
indica o s which do no depend on he objec i e unc ion o he p ob-
lem, bu on he cha ac e is ics o he job ha is in oduced (see in his
ega d e.g., Fe nandez-Viagas e al., 2016). Following hese ecom-
menda ions, in he p oposed heu is ic, we selec job
α
o be placed,
acco ding o he ollowing indica o :
δj=⎧
⎪
⎪
⎨
⎪
⎪
⎩
−pmax +pj
2+n⋅(s
π
k−1,j−smin)+n⋅max( j−C
π
k−1,0),i Tj>0
Ej+pj
2+n⋅(s
π
k−1,j−smin) + n⋅max( j−C
π
k−1,0),o he wise
Being j an unscheduled job o he pa ial solu ion Π in i e a ion k,
wi h Π= (
π
1,⋯,
π
k−1).Then, in each i e a ion k, job j wi h minimal δj is
placed a he end o Π. This indica o conside s he ollowing elemen s o
selec he jobs:
- Ea liness o he new job, Ej: Fo a job j, i s ea liness can be de ined by
Ej=max(0,dj−Cj). I is indi ec ly ela ed wi h he objec i e
Table 3
Cons ain equa ions ela ed o each MILP model.
MILP1 MILP2 MILP3 MILP4
Cons . n. Cons . Eq. Cons . n. Cons . Eq. Cons . n. Cons . Eq. Cons . n. Cons . Eq.
1 (2) 1 (4) 1 (13) 1 (2)
2 (3) 2 (6) 2 (18) 2 (4)
3 (4) 3 (8) 3 (20) 3 (6)
4 (5) 4 (13) 4 (21) 4 (8)
5 (6) 5 (16) 5 (24) 5 (13)
6 (7) 6 (17) 6 (25) 6 (16)
7 (8) 7 (18) 7 (26) 7 (20)
8 (9) 8 (19) 8 (27) 8 (21)
9 (10) 9 (20) 9 (28) 9 (22)
10 (11) 10 (21) 10 (29) 10 (23)
11 (12) 11 (22) 11 (30) 11 (34)
12 (13) 12 (23) 12 (31) 12 (35)
13 (14) 13 (32) 13 (36)
14 (15) 14 (33)
Table 4
Numbe o bina y and con inuous a iables o all milp models.
Models Bina y
a iable
NBVs Con inuous
a iable
NCVs NCs
MILP1 Yij n2+
3n
Cj,Ej,Tj3n+
2
n2+8n+8
MILP2 Yij, Xjn2+
2n
Cj,Ej,Tj,Z,R3n+
2
n2+7n+
5
MILP3 Yij, Xj,Wj,Vjn2+
3n
Cj,Tj,Z,ZC 2n+
2
3n2+5n+
6
MILP4 Yij, Xj,Wjn2+
3n
Cj,Ej,Tj,Z,R3n+
2
2n2+7n+
5
A. Cos a e al.
Compu e s and Ope a ions Resea ch 173 (2025) 106849
5
unc ion, since jobs wi h sho ea liness imes in an i e a ion k will
p obably ha e a diness in he ollowing i e a ions, i hey a e no
placed in ha i e a ion.
- P ocessing ime o he new job, pj: I has an in luence on bo h he
comple ion ime o he new job o be inse ed and he comple ion
imes o he ollowing inse ed jobs.
- Se -up ime incu ed by he new job, s
π
k−1,j: As in he p e ious case, i
in luences he comple ion imes o job j and o he ollowing jobs.
Then, (s
π
k−1,j−smin)indica es he di e ence be ween i s se up ime
and he minimal se up ime in he shop, de ined by smin (i.e., smin =
min
∀j,ksjk wi h j,k∈ {1,⋯,n}).
- Ta diness o he jobs, Tj. The indica o p io i izes jobs wi h a diness
g ea e han 0 by sub ac ing pmax (being pmax he maximum p o-
cessing ime in he shop, i.e. pmax =max
∀i,jpij wi h i∈ {1,⋯,m},j∈ {1,
⋯,n}), since no placing hem will di ec ly inc ease he objec i e
unc ion in he ollowing i e a ions.
- Idle ime. The idle ime has a di ec in luence on he comple ion ime
o he new job and consequen ly on he comple ion imes o he
ollowing jobs. As his idle ime could be educed by selec ing a
di e en job, he indic o ies o minimize i . The idle ime is
measu ed by max( j−C
π
k−1,0).
The complexi y o BCH is O(n2) as n i e a ions a e pe o med and a
job is selec ed in each i e a ion om he se o unscheduled jobs. This se
has a size o n−k+1 in i e a ion k.
6.2. Neighbo hood composi e heu is ic, NCH
A e a as solu ion has been achie ed by BCH, he composi e heu-
is ic NCH ies o ob ain he bes solu ion in i s neighbo hood. Mo e
speci ically, he ollowing h ee speci ic local sea ches a e applied o he
solu ion ob ained by BCH:
•Inse ion local sea ch, LS1. This local sea ch is applied o he solu ion
Π ob ained in BCH. Each job o his sequence is i e a i ely emo ed
and es ed in each posi ion o he sequence. The job is inse ed in he
posi ion yielding he bes objec i e unc ion alue and he new
sequence eplaces he i e a ion sequence. Once all jobs a e ein-
se ed, he comple e sea ch is epea ed un il he e is no u he
imp o emen . Le Π2 deno e he sequence ob ained by using his
p ocedu e.
•Pai wise inse ion local sea ch, LS2. This local sea ch is applied o
he solu ion Π2 ob ained a e applying LS1. This p ocedu e is
analogous o LS1, bu conside ing pai s o wo consecu i e jobs, i.e.,
each pai o wo consecu i e jobs is emo ed and einse ed in he
bes posi ion. Again, he comple e sea ch is epea ed un il he e is no
mo e imp o emen . Le Π3 deno e he sequence ob ained using his
p ocedu e.
•In e change local sea ch, LS3. This local sea ch is applied o he
solu ion Π3 ob ained a e applying LS2. In his local sea ch, each job
is in e changed wi h each o he job in he sequence, and he mo e-
men yielding he minimal o al a diness is selec ed. In his case, he
p ocedu e is comple ed when all jobs a e es ed and Πʹ deno e he
inal ob ained sequence.
The complexi y o NCH is he maximum complexi y be ween BCH,
LS1, LS2, and LS3. BCH has a complexi y o O(n2), while LS1, LS2 and
LS3 has he same complexi y equals o O(k⋅n4), being k he numbe o
i e a ions wi hou imp o emen s. Hence, he complexi y o NCH is O
(k⋅n4).
6.3. Mul i-s a composi e heu is ic, MCH(λ)
Based on NCH, composi e heu is ic MCH(λ) cons uc s solu ions
epea ing a p ocedu e simila o NCH. Mo e speci ically, he heu is ic
andomizes he p ocedu e o gene a e a solu ion om he BCH heu is ic
and he LS1, LS2 and LS3 local sea ches a e applied a e ha . In o de o
andomize he solu ion cons uc ed be o e he local sea ches, he p o-
cedu e BCH is applied, bu selec ing a andom job in each i e a ion
among he wo jobs wi h he lowes δj alue (ins ead o selec ing he job
yielding he lowes δj alue). This p ocedu e is epea ed λ imes, and he
bes solu ion is e u ned. As a consequence, he complexi y o MCH(λ)is
O(k⋅λ⋅n4). A mo e de ailed explana ion o his cons uc i e heu is ic
MCH(λ) is p esen below:
Πb:= {∅}
Fo each i e a ion i∈ {1,⋯,λ}
Ini ializa ion o he ini ial emp y pa ial sequence and he se o
unscheduled jobs: Π:= {∅}and ℧:= {1,2,⋯,n}.
NCs
NBVs
NVCs
NZCs
Fig. 1. Plo s o cons ain s and a iables o he MILP models.
A. Cos a e al.
Compu e s and Ope a ions Resea ch 173 (2025) 106849
6
Fo each posi ion k∈ {1,⋯,n}
Calcula e δj, ∀j∈ {1,⋯,|℧|}.
α
1:=Job wi h minimal δj, ∀j∈ {1,⋯,|℧|}.
α
2:=Job wi h he second smalles alue o δj, ∀j∈ {1,⋯,|℧|}.
α
:=Random job be ween
α
1 and
α
2.
Inse
α
in he las posi ion o Π (posi ion k) and emo e i
om ℧.
Π2:=LS1(Π)
Π3:=LS2(Π2)
Πʹ:=LS3(Π3)
I i=0 o Tmax(Πʹ)<Tmax(Πb), hen Πb=Πʹ
Re u n Πb
6.4. Implemen ed heu is ics
To alida e he e iciency o he p oposals, we compa e hem wi h
he mos p omising heu is ics in he ela ed li e a u e. To deal wi h ha ,
he ollowing heu is ics a e e-implemen ed and adap ed o he p oblem
unde conside a ion:
•ERD: Es ablished as he bes s a ic dispa ching ule by Cos a and
Fe nandez-Viagas (2022) o he p oblem unde conside a ion
(compa ed wi h SPT, LPT, EDD and LPT).
•MDD: Es ablished as he bes dynamic dispa ching ule by Cos a and
Fe nandez-Viagas (2022) o he p oblem unde conside a ion. I
places he job wi h lowes d*=max(dj, +pj), wi h =max( j,Cj−1).
•MDD2: P oposed a ian o adap MDD o he p oblem. I places he
job wi h lowes d*=max(dj, +pj+s
π
j−1,j), wi h =max( j,Cj−1).
•MWSPT: P oposed o 1 j,sij∑wjCj by Chou e al. (2009). To adap
i o he p oblem, we conside wj=1.
•NEHedd. Es ablished as he bes NEH heu is ic by Cos a and
Fe nandez-Viagas (2022) o he p oblem unde conside a ion.
•NEHedd(TB
IT1
). The heu is ic p oposed by Fe nandez-Viagas and
F aminan (2015) o he Fm|p mu|∑Tj.
•NEHedd(TB
IT2
). The heu is ic p oposed by Fe nandez-Viagas and
F aminan (2015) o he Fm|p mu|∑Tj.
•CH_i (∀i∈ {1,⋯,6}): The heu is ics p oposed by Li e al. (2015) o
Fm|p mu|∑Tj.
•RI: P oposed by Mon oya-To es e al. (2012) o he 1 j,sijCmax
p oblem.
•ATCS: The heu is ic p oposed by Lee e al. (1997) o he 1sij∑Tj
p oblem.
•MATCS: The heu is ic p oposed by Shin e al. (2002) o he 1 j,
sij∑Lmax p oblem.
7. Benchma k o es cases
To gene a e he benchma k o es cases, he wo-phase compu a-
ional p ocedu e p oposed in Cos a and Fe nandez-Viagas (2022) has
been used. In b ie , du ing he i s phase, he majo job desc ip o s (i.e.,
elease imes, sequence-dependen se up imes, p ocessing imes, and
due da es) a e gene a ed h ough a se ies o pa ame e s in acco dance
wi h O acik and Uzsoy (1994). In he second phase, da a ega ding he
main enance issue (i.e., Imax,Imin,γ) a e yielded by s a ing om he
ea lies elease da es (ERD) schedule. As he p esen pape ocuses on
e alua ing bo h e iciency and e icacy o se e al heu is ic algo i hms
o sol ing he SMFVM p oblem wi h sequence-dependen se up imes
and non-ze o job elease imes, he wo-phase p ocedu e was ca ied ou
by conside ing six con ol pa ame e s, ega dless o he p oblem size (i.
e., n). In gene al, he wo-phase p ocedu e makes use o a uni o m dis-
ibu ion U(1, s) o gene a e he se up imes. Release imes a e andomly
d awn in he ange [0, e•LB], whe e LB is a lowe bound on he
makespan. The ea lies main enance s a ing ime (Imin) is con olled by
pa ame e h. The la es main enance comple ion ime (Imax) depends on
pa ame e g, while he minimum main enance du a ion (i.e., γ) is a
unc ion o pa ame e l. Finally, he slope coe icien acco ding o which
main enance du a ion inc eases wi h i s s a ing ime, is con olled by
pa ame e m. In his pape , a wo old expe imen al analysis is p oposed.
The o me aims a compa ing a la ge se o heu is ic algo i hms, also
including he p oposed algo i hms, wi h he global op ima achie ed by
he p oposed MILP models. Indeed, such analysis e en allows he e al-
ua ion o bo h e icacy and compu a ional e iciency o he MILP models
by means o a se ies o pe o mance indica o s. To his end, a da a se o
500 small-sized es p oblems has been gene a ed as ollows. The
numbe o jobs was a ied a i e le els in he se {8, 10, 12, 14, 16}. Fo
each p oblem size, 100 ins ances ha e been andomly gene a ed by
means o he abo e-men ioned wo-phase p ocedu e, in which he six
con ol pa ame e s a e andomly selec ed in he ollowing se s: s∈ { U
(1,100), U(1,200)}, e∈ {0.6,1.0,1.4}, h∈{1
4,1
2}, g∈ {3,6}, l∈ {0.1,
0.3}, m∈ { an(1
8), an(1
4)}.
The la e e e s o he expe imen al analysis o la ge-sized in-
s ances, which aims o again compa e se e al heu is ics om he ele-
an li e a u e and he p oposals as well. In his con ex , a ull ac o ial
design o expe imen s (DOE) has been a anged, con o ming o he
con ol pa ame e alues men ioned in he p e ious analysis. Hence,
conside ing ha he p oblem size was a ied in {20, 50, 100, 150, 300}
jobs, i e con ol pa ame e s we e a ied a o le els and one a h ee
le els, as epo ed in Table 5. Since i e ins ances we e andomly
gene a ed o each pa ame e con igu a ion, a o al numbe o
5×2
5
×3×5 =2,400 ins ances was buil using he wo-phase benchma k
gene a ion p ocedu e.
Al hough he p esen pape is inspi ed by a eal-li e semiconduc o
manu ac u ing p oblem, mo i a ed by he non-disclosu e es ic ions
imposed by he company he a o emen ioned p oblem desc ip o s a e
sligh ly dissimila om he indus ial ones. Speci ically, he coe icien
o main enance a iabili y, i.e., “m” is usually smalle and se up imes
p ima ily ollow a no mal dis ibu ion wi h a smalle dispe sion han he
one used in he es bed. Howe e , i is wo h poin ing ou ha a se ies o
es uns pe o med on he ac ual p oblem ha e e ealed he quali y o
he p oposed app oach.
8. Expe imen al esul s and analysis
8.1. Small-sized p oblems
The expe imen al analysis p esen ed in his sec ion in ol es 500
small-sized es p oblems wi h a wo old objec i e. Fi s , we e alua e he
e icacy and compu a ional e iciency o he p oposed MILP models.
Second, we use he global op ima achie ed by he MILP models o
alida e he se en een heu is ics om he ele an li e a u e and ou
new p oposals.
8.1.1. Compa ing MILP models
Con o ming o Sec. 7, 100 ins ances we e andomly gene a ed o
i e classes o p oblems in ol ing a numbe o jobs a ying om 8 o 16
jobs and sol ed by IBM ILOG CPLEX V13® comme cial so wa e on a
Wo ks a ion equipped wi h Win11 OS, In el i9 X-co e p ocesso s and 32
Table 5
DOE. Fac o s and le els o he ull ac o ial design o expe imen s.
Fac o Le els
sU(1,100) U(1,200)
e0.6 1.0 1.4
h1/4 1/2
g3 6
l0.1 0.3
m an(1/8) an(1/4)
A. Cos a e al.
Compu e s and Ope a ions Resea ch 173 (2025) 106849
7
Gb RAM. Fig. 2a shows he a e age compu a ional ime (ACT) in sec-
onds equi ed by each MILP model as he p oblem size changes and
clea ly p o es ha MILP2 and MILP3 ou pe o m he o he models as he
p oblems size is g ea e han 10. As expec ed, hough a ime limi o
1,000 s was se on he sol e , he a e age compu a ional ime g ows
mo e han exponen ially and abou 400 s on he a e age a e equi ed o
con e ge o he global op imum o a 16-jobs p oblem, a leas . Fig. 2b
depic s how he compu a ional ime a ies in e ms o ela i e pe -
cen age de ia ion o e he bes esul (RPD_ ime) o each class o
p oblem. I e eals ha he e iciency o he MILP model is almos he
same un il 12 jobs, while an inc easing de ia ion among he models
eme ges as he p oblem size g ows. Again, MILP 2 and MILP3 can be
conside ed as he mos e icien models, while MILP1 appea s o be he
slowes in sol ing he scheduling p oblem a hand. Due o he ime limi
on he sol ing ime, he gap om he lowe bound a con e gence was
aken on as a u he KPI o compa ison pu poses. The gap is an indi-
ca o o assess i he op imal solu ion is achie ed o no , as any solu ion
wi h ze o gap is a global op imum. Fig. 2c shows ha 1,000 s is enough
o achie e he global op imum when he p oblem size is 8 o 10,
ega dless o he speci ic MILP model. When he p oblem size inc eases
om 12 o 16 he numbe o heu is ic solu ions ises up as well (see also
N_heu in Fig. 2d) along wi h he a e age pe cen age gap (Gap_a e)
om he lowe bound. Bo h Fig. 2c and d con i m he highe e icacy o
MILP3 and MILP2 in sol ing he p oblem unde in es iga ion han
MILP4 and e en mo e MILP1, which appea s o be he leas sui able
model unde all he p o ided KPIs.
In e es ingly, he wo mos pe o ming models, i.e., MILP2 and
MILP3, holds di e en ea u es in e ms o modelling s uc u e. Mo e
p ecisely, MILP2 is he model assu ing he leas numbe o bina y a -
iables, while MILP3 needs he leas numbe o con inuous a iables (see
bold alues in Table 4). Unde hese pe spec i es, NBVs would jus i y
he ou pe o mance o MILP2 in e ms o a e age ime o con e gence
and numbe o global op ima o e he o he models. Howe e , a coun-
e in ui i e inding ega ds he numbe o cons ain s o MILP2 and
MILP3, as he o me equi es he smalles NCs while he la e he
la ges one o e all models; hus, i can be s a ed ha he p oposed MILP
models a e no sensi i e o NCs. In conclusion, i can be asse ed ha
MILP2 and MILP 3 a e he mos p e e able models o be conside ed o
sol ing he complex single machine scheduling p oblem unde in es i-
ga ion. Fig. 3 e eals ha MILP2 and MILP 3 ou pe o m he o he
models unde e e y pe o mance indica o , unde quali y o solu ions
and compu a ional ime pe spec i es. No ably, MILP2 achie es a be e
sco e when he ime o con e gence is c aken on as a KPI. Besides, he
ad an age o MILP 2 and MILP3 o e he di ec compe i o s g ows as
much as he p oblem size inc eases and a clea inc emen al alue o o e
he MILP1 model om Cos a and Fe nandez-Viagas (2022) eme ges in
e ms o compu a ional e iciency, numbe o heu is ics solu ions and
a e age gap om he lowe bound. Al hough he complexi y o he
scheduling p oblem in he eal-li e con ex does no allow o use any
MILP model, i is wo h poin ing ou ha global and/o nea -op imal
solu ions p o ided by a MILP model su ely ep esen a alid suppo
o heu is ic algo i hms alida ion. Hence, MILP3 and e en mo e MILP2,
which assu es a lowe compu a ional ime in sol ing he 16-jobs
scheduling p oblem, can be deployed o alida ion pu poses o heu-
is ic and me aheu is ic algo i hms.
Fo he sake o cla i y, he ollowing pa ag aphs deal wi h an illus-
a i e example o emphasize he di e ence o pe o mance be ween
MILP and a well-es ablished heu is ic ule o dynamic scheduling
p oblems, i.e., ERD. Le ’s conside a SMFVM p oblem wi h n =10 jobs,
allowed main enance ime in e al [I
min
, I
max
] =[763, 1963], main e-
nance basic du a ion γ =360, and slope o a iable main enance du a-
ion m = an(0.3). Being he p oblem da a epo ed in Table 6, MILP and
ERD schedules a e S
1
=[1 3 9 2 10 4 M 6 7 8 5] and S
2
=[1 2 3 9 4 M 10
6 7 8 5], espec i ely; M means he main enance ask. The o al a diness
ela ed o S
1
is 1,140.14 ime uni s, while he one ela ed o S
2
is equal o
1,314.01 ime uni s. Howe e , he di e ence be ween he wo solu ions
can be app ecia ed by Fig. 3 ha depic s he Gan diag ams o bo h
MILP solu ion (a) and ERD solu ion (b), being he g ey blocks he
Fig. 2. G aphs o compa e MILP models.
A. Cos a e al.
Compu e s and Ope a ions Resea ch 173 (2025) 106849
8
sequence dependen se up imes equi ed by each job. In e es ingly,
hough he main enance du a ion o he MILP solu ion is longe han he
ERD one, he way he jobs a e sequenced assu es a be e o al a diness
han ERD.
8.1.2. Compa ing heu is ics
To alida e and assess he pe o mance o he p oposed composi e
heu is ics, an ex ended compa ison analysis was ca ied ou by using he
same da ase men ioned in he p e ious sub-sec ion. In pa icula , he
ou p oposals a e compa ed wi h he MILP models and se en een well-
known heu is ics om he ele an li e a u e. Table 7 epo s he alues
o ou pe o mance indica o s o each op imiza ion me hod and o
each class o p oblems, depending on he p oblem size. The i s KPI is
he median ela i e pe cen age de ia ion (MRPD), i.e., he median o he
pe cen age de ia ions o he o al a diness achie ed by each me hod
om he bes alue, o e he p o ided 100 ins ances o each class o
p oblems. Then, he numbe o heu is ic solu ions ( ela ed o MILP
models no con e ging in 1,000 s) and he numbe o un easible solu-
ions ( ela ed o heu is ics yielding solu ions no sa is ying he p o ided
main enance cons ain s) a e conside ed as ano he indica o o e icacy.
N_op means he imes each me hod eaches he minimum o al a di-
ness, while ACT is he a e age compu a ional ime (in seconds) o each
me hod o e 100 ins ances. Bold MRPD alues a e equal o ze o and
indica e he mos pe o ming me hods unde he quali y o solu ions
iewpoin . As he eade can no ice, ega dless o he MILP models, h ee
o he p oposed composi e heu is ics (namely NCH, MCH(10) and MCH
(20)) assu e he leas MRPD alues, wi h he excep ion o NCH o he
la ges scena io p oblem wi h 16 jobs. Fo he smalles class o p oblems,
CH algo i hms a e capable o gua an eeing MRPDs equal o ze o, while
RI p o ides MRPD pe o mances compa able o he bes p oposed al-
go i hms o each class o p oblems. All es ed heu is ics con e ge o
easible solu ions, hus demons a ing ha all o hose a e sui able o
sol ing he p oblem unde in es iga ion. On he o he hand, as expec ed,
o all MILP models he N_heu indica o inc eases as much as he
p oblem size inc eases oo. Howe e , MILP2 and MILP3 appea s again as
he bes models i N_heu is aken on as pe o mance indica o . Simila
conside a ions o he MILP models can be done whe he N_op indica o
is obse ed. As expec ed, i educes wi h he p oblem size and s ill
MILP2 and MILP3 ensu e he highes alues o each scena io p oblem.
Looking a he heu is ics, MCH(10) and MCH(20) show he bes esul s
in e ms o N_op , along wi h he RI heu is ic, ega dless o he speci ic
p oblem size. NCH eme ges as a good heu is ic i compa ed wi h he es
o he es ed me hods, bu N_op alues con i m a lowe e icacy han
MCH a ian s and RI as well o all class o p oblems. Conside ing he
ACT pe o mance measu e, such indica o inc eases as much as he
p oblem size g ows, e en i such a endency comes ou only o he MILP
Fig. 3. Gan diag am o a 10-job SMFVM p oblem: a) S
1
-MILP solu ion; b) S
2
-ERD solu ion.
Table 6
Illus a i e example: job desc ip o s.
j1 2 3 4 5 6 7 8 9 10
j
47 62 67 576 2011 1260 1293 1969 291 653
p
j
84 145 2 61 30 19 38 70 80 108
d
j
372 1178 71 466 2192 1267 1524 2101 822 1244
s
ij
83 191 189 156 97 106 183 191 1 197
135 62 106 21 11 131 69 131 122 34
41 137 137 89 114 102 148 123 65 28
173 173 63 179 29 187 144 23 104 184
6 177 136 58 117 116 175 188 175 138
133 17 165 57 138 178 123 89 71 14
83 8 4 26 21 28 148 114 179 149
111 34 148 4 82 28 69 81 123 149
28 173 195 134 137 160 54 47 4 182
40 20 148 42 82 79 177 178 184 141
158 83 56 53 10 33 85 114 137 25
A. Cos a e al.
Compu e s and Ope a ions Resea ch 173 (2025) 106849
9
