Lin, Meng-Ye; Kuo, Ya lin
A icle
E icien mixed in ege p og amming models o amily
scheduling p oblems
Ope a ions Resea ch Pe spec i es
P o ided in Coope a ion wi h:
Else ie
Sugges ed Ci a ion: Lin, Meng-Ye; Kuo, Ya lin (2017) : E icien mixed in ege p og amming models
o amily scheduling p oblems, Ope a ions Resea ch Pe spec i es, ISSN 2214-7160, Else ie ,
Ams e dam, Vol. 4, pp. 49-55,
h ps://doi.o g/10.1016/j.o p.2017.03.001
This Ve sion is a ailable a :
h ps://hdl.handle.ne /10419/178280
S anda d-Nu zungsbedingungen:
Die Dokumen e au EconS o dü en zu eigenen wissenscha lichen
Zwecken und zum P i a geb auch gespeiche und kopie we den.
Sie dü en die Dokumen e nich ü ö en liche ode komme zielle
Zwecke e iel äl igen, ö en lich auss ellen, ö en lich zugänglich
machen, e eiben ode ande wei ig nu zen.
So e n die Ve asse die Dokumen e un e Open-Con en -Lizenzen
(insbesonde e CC-Lizenzen) zu Ve ügung ges ell haben soll en,
gel en abweichend on diesen Nu zungsbedingungen die in de do
genann en Lizenz gewäh en Nu zungs ech e.
Te ms o use:
Documen s in EconS o may be sa ed and copied o you pe sonal
and schola ly pu poses.
You a e no o copy documen s o public o comme cial pu poses, o
exhibi he documen s publicly, o make hem publicly a ailable on he
in e ne , o o dis ibu e o o he wise use he documen s in public.
I he documen s ha e been made a ailable unde an Open Con en
Licence (especially C ea i e Commons Licences), you may exe cise
u he usage igh s as speci ied in he indica ed licence.
h p://c ea i ecommons.o g/licenses/by/4.0/
Ope a ions Resea ch Pe spec i es 4 (2017) 49–55
Con en s lis s a ailable a ScienceDi ec
Ope a ions Resea ch Pe spec i es
jou nal homepage: www.else ie .com/loca e/o p
Efficien mixed in ege p og amming models o amily scheduling
p oblems
Meng-Ye Lin, Ya lin Kuo
∗
Depa men o Indus ial Enginee ing and Managemen , Yunlin Uni e si y o Science and Technology, Yunlin, Taiwan
a i c l e i n o
A icle his o y:
Recei ed 9 No embe 2016
Re ised 3 Ma ch 2017
Accep ed 15 Ma ch 2017
A ailable online 23 Ma ch 2017
Keywo ds:
Family scheduling
Sequence independen se up
To al weigh ed comple ion ime
Maximum la eness
a b s a c
This pape p oposes se e al mixed in ege p og amming models which inco po a e op imal sequence
p ope ies in o he models, o sol e single machine amily scheduling p oblems. The objec i es a e o-
al weigh ed comple ion ime and maximum la eness, espec i ely. Expe imen esul s indica e ha he e
a e ema kable imp o emen s in compu a ional efficiency when op imal sequence p ope ies a e included
in he models. Fo he o al weigh ed comple ion ime p oblems, he bes model sol es all o he p ob-
lems up o 30-jobs wi hin 5 s, all 50-job p oblems wi hin 4 min and abou 1/3 o he 75-job o 100-job
p oblems wi hin 1 h. Fo maximum la eness p oblems, he bes model sol es almos all he p oblems up
o 30-jobs wi hin 11 min and a ound hal o he 50-job o 100-job p oblems wi hin 1 h.
©2017 The Au ho s. Published by Else ie L d.
This is an open access a icle unde he CC BY license. ( h p://c ea i ecommons.o g/licenses/by/4.0/ )
1. In oduc ion
Ba ching jobs ha sha e he same se up on a machine o
inc ease p oduc i i y is a common p ac ice in manu ac u ing. Such
ba ching o jobs is o en classified as a amily in scheduling. When
p ocessing wo jobs belonging o di e en amilies consecu i ely,
a se up is equi ed be ween hem. The ba ching ope a ion o en
leads o job la eness and esul s in poo deli e y pe o mance.
How o ade-o p oduc i i y and deli e y pe o mance is a icky
scheduling p oblem. This p oblem is called ba ch/ amily/g oup
scheduling wi h se ups in he li e a u e. Fo pas esea ch on
amily scheduling see Re s. [12,16,23] .
The solu ion app oaches o sol e amily scheduling p oblems
include ma hema ical p og amming [1,3,8,13] , b anch and bound
[7,18,19] , dynamic p og amming [6,9,11,17] and heu is ic/me a
heu is ics [4,5,14,21,24,25] . The las app oach, heu is ic/me a
heu is ics, is o en designed o find good solu ions o la ge scale
p oblems. Excep o ma hema ical p og amming, ime consum-
ing and complica ed coding is equi ed o find op imal/good
sequences. On he o he hand, comme cial sol e s such as LINGO
and CPLEX a e a ailable o sol e ma hema ical models. Thus, he
s a -up ask o ma hema ical p og amming is much less han
hose o he o he h ee solu ion app oaches. O en he ma hema -
ical p og amming app oach is applied o find an op imal schedule
wi h limi ed CPU ime, say 1 h, and is o en used o sol e small
∗Co esponding au ho .
E-mail add esses: M10221311@yun ech.edu. w (M.-Y. Lin), kuoyl@yun ech.edu. w
(Y. Kuo).
size p oblems. Thus, he ma hema ical p og amming app oach is
applicable o small-size en e p ise scheduling p oblems o as a
basis o olling-ho izon based scheduling echniques.
Webs e and Bake [23] gi e an o e iew o op imal p ope ies
on amily scheduling on a single machine. Ve y o en hese op-
imal p ope ies a e included in he b anch and bound, dynamic
p og amming and heu is ic solu ion app oaches o achie e be e
compu a ional efficiency. In his s udy, we include some op imal
p ope ies o he amily scheduling p oblem in o ma hema ical
p og amming models and in es iga e he e ec s o his inclusion
on compu a ional efficiency. In sol ing scheduling p oblems wi h
ma hema ical p og amming, he e a e se e al well-known mixed
in ege p og amming (MIP) o mula ions p oposed in he li e a-
u e, which include: (1) he disjunc i e o mula ion de eloped by
Manne [10] which con ains p ecedence a iables ha define he
p ecedence o de o any wo jobs and disjunc i e cons ain s ha
ela e he comple ion imes be ween any wo jobs (2) he ime
indexed o mula ion p oposed by Sousa and Wolsey [20] which
defines ime a iables ha ela e jobs o he co esponding p o-
cessing s a ing imes in a fini e disc e e ime ho izon, (3) he
linea o de ing o mula ion de eloped by Po s [15] which adds
iangle inequali ies among he p ecedence a iables o any h ee
jobs and (4) he sequence posi ion o mula ion de eloped by
Wagne [22] which con ains sequence posi ion a iables ha
ela e jobs o co esponding posi ions in a sequence. Fo he single
machine scheduling p oblem wi h elease da es and sequence de-
penden se up and he objec i es o o al weigh ed a diness and
o al weigh ed comple ion ime, espec i ely, Noguei a and Ca -
alho (2014) compa es he pe o mance o six MIP o mula ions,
h p://dx.doi.o g/10.1016/j.o p.2017.03.001
2214-7160/© 2017 The Au ho s. Published by Else ie L d. This is an open access a icle unde he CC BY license. ( h p://c ea i ecommons.o g/licenses/by/4.0/ )
50 M.-Y. Lin, Y. Kuo / Ope a ions Resea ch Pe spec i es 4 (2017) 49–55
which include he ou o mula ions abo e and wo imp o ed
o mula ions and finds ha he disjunc i e o mula ion sol es a
g ea e numbe o p oblems.
In his s udy, we adop he ma hema ical p og amming ap-
p oach o find he op imal sequence o a single machine amily
scheduling p oblem wi h amily sequence independen se up ime
and he objec i es o o al weigh ed comple ion ime (TWC) and
maximum la eness ( L
max
), espec i ely. Th ee MIP o mula ions
which include he op imal sequence p ope ies a e p oposed. The
pe o mance o he p oposed h ee MIP o mula ions is compa ed
wi h wo MIP models ha do wi hou he op imal sequence p op-
e ies by compu a ional expe imen s unde di e en ope a ing
scena ios. The es o his pape is o ganized as ollows. Sec ion
2 gi es p oblem s a emen s and p esen s MIP o mula ions.
Sec ion 3 gi es he compu a ional esul s and he pape concludes
in Sec ion 4 .
2. P oblem s a emen s and MIP o mula ions
Conside he p oblem o scheduling N jobs belonging o F
amilies on a single machine. A amily sequence independen
se up is equi ed when a machine swi ches om idle o busy and
om p ocessing jobs in one amily o jobs in ano he amily. The
objec i es a e o minimize o al weigh ed comple ion ime (TWC)
and maximum la eness, espec i ely. Be o e p oposing he MIP
models, we gi e wo op imal sequence p ope ies o he amily
scheduling p oblems fi s .
B uno and Se hi’s op imal p ope y: Fo he TWC p oblems,
he e is an op imal sequence in which jobs in he same amily a e
o de ed by SWPT (sho es weigh ed p ocessing ime fi s ) [2] .
Monma and Po s’s op imal p ope y: Fo he L
max p oblems,
he e is an op imal sequence in which jobs in he same amily a e
o de ed by EDD (ea lies due da e fi s ) [11] .
We include hese wo op imal p ope ies in he cons ain s o
MIP o mula ions and in es iga e he e ec s o hese inclusions.
Fi e MIP o mula ions a e p oposed o sol e his p oblem, hey a e
(1) amily linea o de ing o mula ion, FLO, (2) FLO wi h jobs in
he same amily sequenced in SWPT o TWC p oblems, FLO
swp
,
and in EDD o L
max p oblems, FLO
edd
, (3) o de ed linea o de ing
o mula ion, OLO, whe e jobs in he same amily a e sequenced
in SWPT o TWC p oblems and in EDD o L
max p oblems, (4)
disjunc i e o mula ion, DJ and (5) DJ wi h jobs in same amily
sequenced in SWPT o TWC p oblems, DJ
swp
, and in EDD o L
max
p oblems, DJ
edd
. The FLO and DJ o mula ions a e p oposed o he
pu pose o compa ison. The no a ion and pa ame e s used in he
MIP o mula ions a e as ollows.
No a ion and pa ame e s
a
( i, j )
: job j o amily i .
F : se o all amilies.
N : se o all jobs.
s
i
: se up ime o amily i .
s
( i, k )
: se up ime om amily i o amily k , s
( i,k )
= s
k
, s
( i,k )
= 0 i
i = k .
p
( i, j )
: p ocessing ime o a
( i, j )
.
w
( i, j )
: weigh o a
( i, j )
.
d
( i, j )
: due da e o a
( i, j )
.
: o al numbe o amilies.
n
i
: o al numbe o jobs in amily i .
n : o al numbe o jobs.
M : a big numbe .
Decision a iables
δ(
i,j
) (
k,l
)
=
1 i a
(
i,j
)
is scheduled be o e a
(
k,l
)
.
0 o he wise .
x
i
j

j
=
1 i a
(i,j

)
is sched uled immed ia ely be o e a
(i,j)
.
0 o he wise .
y
(i,j)
=
1 i a se up occu s immedia ely be o e a
(i,j)
0 o he wise .
z
(i,j)(k,l)
=
⎧
⎨
⎩
1 i a
(i,j)
is scheduled be o e a
(k,l)
and a se up
s
i
occu s immedia ely be o e a
(i,j)
.
0 o he wise .
C
(i,j)
: comple ion ime o a
(i,j)
.
2.1. FLO o mula ion
The linea o de ing o mula ion is o sol e a single machine
scheduling p oblem wi hou se ups. The p oblem s udied he e is
a amily scheduling p oblem wi h se ups, and hus a amily linea
o de ing o mula ion, FLO, is p oposed. In he FLO o mula ion,
jobs in each amily a e a bi a ily numbe ed. The cons ain s o
FLO a e:
δ(i,j)(k,l)
+ δ(k,l)
(i,j)
= 1 ∀ ( i, j) , (k, l) ∈ N, ( i, j)  = (k, l) (A1)
δ(
i,j
) (
k,l
)
+ δ(
k,l
)
(
o,p
)
+ δ(
o,p
)
(
i,j
)
≤2
∀
(
i, j
)
,
(
k, l
)
,
(
o, p
)
∈ N and (
i, j
)
 =
(
k, l
)
 =
(
o, p
) (A2)
1 −x
i
j

j
≤

k =1
n
k

l=1
δ(k,l)(i,j)
−

o=1
n
o

p=1
δ(o,p)(i,j

)
−1

+ M
1
1 −δ(i,j

)(i,j)
∀ ( i, j) ,
i, j

∈ N, j < j
 (A3)


k =1
n
k

l=1
δ(k,l)(i,j)
−

o=1
n
o

p=1
δ(o,p)(i,j

)
−1

≤M
2
1 −x
i
j

j
∀ ( i, j) ,
i, j

∈ N, j < j
 (A4)
x
i
j

j
≤δ(i,j

)(i,j) ∀
(
i, j
)
,
i, j

∈ N, j < j
 (A5)
y
(i,j)
= 1 −
n
i

j

=1
x
i
j

j
∀ (i, j) ∈ N (A6)
z
(i,j)(k,l)
≥δ(i,j)(k,l)
+ y
(i,j)
−1 ∀ ( i, j) , (k, l) ∈ N (A7)
C
(i,j)
=

k =1
n
k

l=1
p
(k,l)
δ(k,l)(i,j)
+ s
k
z
(k,l)(i,j)

+ p
(i,j)
+ s
i
y
(i,j) ∀
(
i, j
)
∈ N (A8)
C
(i,j)
≥0 ∀ ( i, j)∈N (A9)
δ(i,j)(i,j)
= 0 ∀ (i, j) ∈ N (A10)
M.-Y. Lin, Y. Kuo / Ope a ions Resea ch Pe spec i es 4 (2017) 49–55 51
δ(i,j)(k,l)
∈
{
0 , 1
} ∀
(
i, j
)
,
(
k, l
)
∈ N (A11)
x
i
j

j
∈
{
0 , 1
} ∀
(
i, j
)
,
i, j

∈ N (A12)
y
(i,j)
∈
{
0 , 1
} ∀
(
i, j
)
∈ N (A13)
z
(i,j)(k,l)
∈
{
0 , 1
} ∀
(
i, j
)
,
(
k, l
)
∈ N (A14)
( A1 ) and ( A2 ) a e he o iginal cons ain s p oposed by Po s
[15] . ( A1 ) ensu es ha a
( i, j )
is scheduled be o e a
( k, l )
o a
( k, l )
is
scheduled be o e a
( i, j )
. ( A2 ) is he ansi i i y ela ion among
any h ee jobs. ( A3, A4 ) and ( A5 ) de e mine he alue o
x
i
j

j
o any wo jobs, a
(i,j

)
and a
( i, j )
in amily i : I a
(i,j

)
is
scheduled immedia ely be o e a
( i, j )
x
i
j

j
= 1 , o he wise x
i
j

j
= 0 .
(

k =1

n
k
l=1
δ(k,l)(i,j)
−
o=1

n
o
p=1
δ(o,p)(i,j

)
−1 ) calcula es he
numbe o jobs scheduled be ween a
(i,j

)
and a
( i, j )
. When a
(i,j

)
is scheduled be o e a
( i, j )
( δ(i,j

)(i,j)
= 1 ), he e a e wo possible
condi ions:
I a
(i,j

)
and a
( i, j )
a e p ocessed consecu i ely.
II a
(i,j

)
and a
( i, j )
a e p ocessed inconsecu i ely.
I condi ion I is sa isfied, (

k =1

n
k
l=1
δ(k,l)(i,j)
−
o=1

n
o
p=1
δ(o,p)(i,j

)
−1) = 0 , and ( A3, A4 ) and ( A5 ) a e simplified o:
1 −x
i
j

j
≤0 ∀
(
i, j
)
,
i, j

∈ N, j < j
 (A3a)
0 ≤M
2
1 −x
i
j

j
∀
(
i, j
)
,
i, j

∈ N, j < j
 (A4a)
x
i
j

j
≤1 ∀
(
i, j
)
,
i, j

∈ N, j < j
 (A5a)
Thus ( A3 ) leads o x
i
j

j
= 1 . I condi ion II is sa isfied,
0 < (

k =1

n
k
l=1
δ(k,l)(i,j)
−
o=1

n
o
p=1
δ(o,p)(i,j

)
−1 ) ≤n −2 , and
( A3, A4 ) and ( A5 ) a e simplified o:
1 −x
i
j

j
≤

k =1
n
k

l=1
δ(k,l)(i,j)
−

o=1
n
o

p=1
δ(o,p)(i,j

)
−1

∀
(
i, j
)
,
i, j

∈ N, j < j
 (A3b)


k =1
n
k

l=1
δ(k,l)(i,j)
−

o=1
n
o

p=1
δ(o,p)(i,j

)
−1

≤M
2
1 −x
i
j

j
∀
(
i, j
)
,
i, j

∈ N, j < j
 (A4b)
x
i
j

j
≤1 ∀
(
i, j
)
,
i, j

∈ N, j < j
 (A5b)
Thus ( A4 ) leads o x
i
j

j
= 0 . In o de no o iola e ( A4 ),
M
2
≥n −2 . When a
(i,j

)
is scheduled a e a
( i, j )
, δ(i,j

)(i,j)
= 0and
( A3, A4 ) and ( A5 ) a e simplified o:
1 −x
i
j

j
≤

k =1
n
k

l=1
δ(k,l)(i,j)
−

o=1
n
o

p=1
δ(o,p)(i,j

)
−1

+ M
1 ∀
(
i, j
)
,
i, j

∈ N, j < j
 (A3c)


k =1
n
k

l=1
δ(k,l)(i,j)
−

o=1
n
o

p=1
δ(o,p)(i,j

)
−1

≤M
2
1 −x
i
j

j
∀
(
i, j
)
,
i, j

∈ N, j < j
 (A4c)
Table 1
Value o x
i
j

j
wi h espec o ela ion o a
(i,j

)
and a
( i, j )
.
x
i
j

j
= 1 x
i
j

j
= 0
δ(i,j

)(i,j)
= 1 Consecu i e a
(i,j

)
, a
( i, j ) Inconsecu i e a
(i,j

)
, a
( i, j )
δ(i,j

)(i,j)
= 0 Impossible No cons ain is imposed
x
i
j

j
≤0 ∀ ( i, j) , ( i, j

) ∈ N, j < j
 (A5c)
Thus, ( A5 ) leads o x
i
j

j
= 0 . Because −n ≤
(

k =1

n
k
l=1
δ(k,l)(i,j)
−
o=1

n
o
p=1
δ(o,p)(i,j

)
−1 ) < 0 , in o de no
o iola e ( A3 ) and ( A5 ), M
1
≥n + 1 needs o be added o he
igh -hand side o ( A3 ). Table 1 summa izes possible alues o x
i
j

j
unde di e en a
(i,j

)
and a
( i, j )
ela ions.
( A6 ) examines whe he he job scheduled immedia ely be o e
a
( i, j )
belongs o amily i o no . I his job is om amily i hen
y
(i,j)
= 1 , o he wise y
(i,j)
= 0 . ( A7 ) finds he alue o z
( i, j )( k, l )
. I
δ(i,j)(k,l)
= 1 and y
(i,j)
= 1 , hen z
(i,j)(k,l)
= 1 , o he wise he mini-
miza ion o C
( i, j )
ela ed objec i e unc ion will make z
(i,j)(k,l)
= 0 .
( A8 ) finds he comple ion ime o a
( i, j )
which is he sum o he
p ocessing imes o all he jobs scheduled be o e a
( i, j )
plus i s
p ocessing ime and all needed se up imes. ( A9 ) ensu es ha he
comple ion imes a e posi i e. ( A10 ) is i ial. ( A11, A12, A13 ) and
( A14 ) a e in eg ali y cons ain s.
Fo he TWC p oblems, he objec i e is minimizing w
( i, j )
C
( i, j )
,
and cons ain s ( A1 )-(A14) a e equi ed. Fo he maximum la eness
p oblems, besides ( A1 )-(A14), he ollowing cons ain s ( A15 ) and
( A16 ) a e equi ed, he objec i e is minimizing L
max
.
L
max
≥C
(i,j)
−d
(i,j) ∀
(
i, j
)
∈ N (A15)
L
max
≥0 (A16)
2.2. FLO
swp
/FLO
edd
o mula ion
To include B uno and Se hi’s op imal p ope y and Monma
and Po s’ op imal p ope y in o he FLO o mula ion o TWC
p oblems and L
max p oblems, espec i ely, jobs wi hin each amily
a e numbe ed in SWPT o he TWC p oblems, and in EDD o he
L
max p oblems fi s and hen he ollowing cons ain s a e added
o he FLO o mula ion o de i e he FLO
swp
/FLO
edd
o mula ion.
δ(
i,j
) (
i,j+1
)
= 1 ∀
(
i, j
)
∈ N,
i = 1 , 2 , 3 , ... and j = 1 , 2 , 3 , ..
(
n
i
−1
)
2.3. OLO o mula ion
I jobs in each amily a e numbe ed in SWPT o de o he
TWC p oblems and in EDD o de o he L
max p oblems, a iables
x
i
j

j
can be dele ed. We can de e mine whe he a amily i se up
is equi ed o no based on whe he he e a e jobs scheduled be-
ween a
(i,j−1)
and a
( i, j )
o no . I he e a e jobs scheduled be ween
a
(i,j−1)
and a
( i, j )
, a amilyi se up is needed. Replace ( A3 )-(A6) o
he FLO o mula ion wi h ( B3 )-(B6) below and we ha e he OLO
o mula ion.
δ(
i,j
)
(
i,j+1
)
= 1 ∀
(
i, j
)
∈ N, i = 1 , 2 , 3 , ...
and j = 1 , 2 , 3 , ..
(
n
i
−1
) (B3)
y
(
i, 1
)
= 1 ∀ i ∈ F , i = 1 , 2 , 3 , ... (B4)
y
(i,j)
≤

k =1
n
k

l=1
δ(k,l)(i,j)
−

o=1
n
o

p=1
δ(o,p)(i,j−1)
−1

∀
(
i, j
)
∈ N
(B5)
52 M.-Y. Lin, Y. Kuo / Ope a ions Resea ch Pe spec i es 4 (2017) 49–55


k =1
n
k

l=1
δ(k,l)(i,j)
−

o=1
n
o

p=1
δ(o,p)(i,j−1)
−1

≤M
3
y
(i,j) ∀
(
i, j
)
∈ N
(B6)
( B3 ) ensu es ha jobs wi hin each amily a e p ocessed
in SWPT o he TWC p oblems and in EDD o he L
max
p oblems. ( B4 ) ensu es ha a se up is implemen ed be-
o e p ocessing he fi s job wi hin each amily. In ( B5 ),
0 ≤(

k =1
n
k

l=1
δ(k,l)(i,j)
−

o=1
n
o

p=1
δ(o,p)(i,j−1)
−1 )≤n −n
i
finds he
numbe o jobs scheduled be ween a
(i,j−1)
and a
( i, j )
. ( B5 ) and ( B6 )
de e mine he alue o y
( i, j )
. I he e a e jobs scheduled be ween
a
(i,j−1)
and a
( i, j )
, y
(i,j)
= 1 , o he wise y
(i,j)
= 0 . M
3
≥n −n
i
is
equi ed in o de no o iola e ( B6 ).
2.4. DJ o mula ion cons ain s
Fo he DJ o mula ion, jobs wi hin each amily a e a bi a ily
numbe ed. The ollowing o mula ion is adap ed om Manne
(1989) which sol es a scheduling p oblem wi h amily sequence
dependen se ups, hus, we change amily k ’s se up ime s
k
o
s
( i,k )
= s
k
o all i :
C
(k,l)
≥C
(i,j)
+ s
(i,k )
+ p
(k,l)
−M
4
1 −δ(i,j)(k,l)

∀
(
i, j
)
,
(
k, l
)
∈ N and
(
i, j
)
 =
(
k, l
) (C1)
δ(
i,j
) (
k,l
)
+ δ(
k,l
)
(
i,j
)
= 1 ∀
(
i, j
)
,
(
k, l
)
∈ N and
(
i, j
)
 =
(
k, l
) (C2)
C
(k,l)
≥p
(k,l)
+ s
(0 ,k ) ∀ (k, l) ∈ N (C3)
C
(k,l)
≥0 ∀ (k, l) ∈ N (C4)
δ(i,j)(k,l)
∈
{
0 , 1
} ∀ ( i, j) , (k, l) ∈ N and ( i, j)  = (k, l) (C5)
( C1 ) ensu es ha he comple ion ime o a
( k, l )
is g ea e
o equal o he sum o he comple ion ime o a
( i, j )
, he e-
qui ed se up ime s
( i,k )
= s
k
( om amily i o amily k ) and
he p ocessing ime o a
( k, l )
i a
( i, j )
is scheduled be o e a
( k, l )
.
M
4
=

(i,j)
p
(i,j)
+ n ( max
i
( s
i
)) [13] . ( C2 )ensu es ha a
( i, j )
is
scheduled be o e a
( k, l )
o a
( k, l )
is scheduled be o e a
( i, j )
. ( C3 )
ensu es ha he comple ion ime o a
( k, l )
is g ea e o equal o
i s p ocessing ime plus i s ini ial se up ime s
(0, k )
. ( C4 ) ensu es
ha he comple ion imes a e posi i e. ( C5 ) is he in eg ali y
cons ain s. Fo he TWC p oblem, ( C1 )-(C5) a e necessa y and o
he L
max p oblem, wo addi ional ( C6 ) and ( C7 ) a e needed:
L
max
≥C
(i,j)
−d
(i,j) ∀ ( i, j) ∈ N (C6)
L
max
≥0 (C7)
2.5. DJ
swp
/DJ
edd
o mula ion
The DJ
swp
/DJ
edd
o mula ion inco po a es he op imal sequence
p ope ies in o he DJ o mula ion. To apply he DJ
swp
/DJ
edd
o -
mula ion, jobs wi hin each amily a e numbe ed in SWPT o he
TWC p oblems and in EDD o he L
max p oblems. The ollowing
cons ain s a e added o he DJ o mula ion.
δ(
i,j
)
(
i,j+1
)
= 1 ∀
(
i, j
)
∈ N, i = 1 , 2 , 3 , ...
and j = 1 , 2 , 3 , ..
(
n
i
−1
)
Table 2
Pa ame e s gene a ions.
Inpu da a Value
P ocessing ime Uni o m (1, α1
50)
Se up ime Uni o m (1,
α2
10)
Weigh Uni o m (1, n )
Due da e Uni o m
( min
( i,j)
( p
(i,j)
) ,
2 h

α3
)
Numbe o amilies Uni o m (2, min ( n,
α4
4))
3. Compu a ional expe imen s and esul s
To compa e he pe o mance o he fi e MIP o mula ions p o-
posed, we designed he pa ame e selec ion simila o hose o
Noguei a e al. [13] o gene a e six ope a ing scena ios (classes).
The alues o he pa ame e s a e all in eg al and gene a ed acco d-
ing o Table 2
whe e h

=

( i,j)
p
(i,j)
+ n ( max
i
( s
i
)) and α1
, α2
, α3
and α4
a e
scale pa ame e s. α1
, α2
, α3
and α4
de e mine he six ope a ion
classes/scena ios. The minimum alues o α1
, α2
, α3
and α4
a e
all 1 and he maximum alues a e all 4 excep α2
which has a
maximum alue 10. These six classes a e
Class 1: all scale pa ame e s ha e minimum alues; (a basic
class)
Class 2: α1
has maximum alue (4) and he o he s ha e
minimum alues; (a la ge p ocessing ime class)
Class 3: α2
has maximum alue (10) and he o he s ha e
minimum alues; (a la ge se up ime class)
Class 4: α3
has maximum alue (4) and he o he s ha e
minimum alues; (a igh due da e class)
Class 5: α4
has maximum alue (4) and he o he s ha e
minimum alues; (a la ge numbe o amilies class)
Class 6: all scale pa ame e s ha e maximum alues (a complex
class).
Class 4 in es iga ing he due da e e ec s is no applicable o
TWC p oblems. 20 independen ins ances a e andomly gene a ed
o each class and each job size n ∈ {10, 20, 30, 50, 75, 100}. Thus,
he e a e 720 ins ances o L
max p oblems and 600 ins ances o
TWC p oblems.
All MIP o mula ions a e coded wi h Ilog Cplex 12.6 wi h he
de aul se ing and un on a compu e wi h a 2.9 Ghz p ocesso
and 16 GB memo y. Each ins ance is un o 1 h and i s op imali y
gap is eco ded.
3.1. Compu a ional esul s o TWC p oblems
Fo he TWC p oblems, based on he mean op imali y gap ( Fig.
1 ), he pe o mance o OLO is he bes among fi e MIP models o
each class. The nex one is FLO
swp ollowed by FLO and DJ is he
wo s .
Table 3 gi es he mean CPU ime pe sol ed p oblem, and Table
4 gi es he numbe o sol ed p oblems o he TWC p oblems.
Based on Tables 3 and 4 , OLO has he bes pe o mance, which
sol es all p oblems up o 30-jobs wi hin 5 s, and sol es all 50-job
p oblems wi hin 200 s. The second bes model is FLO
swp
, which
sol es all p oblems up o 30-jobs wi hin 15 s. The wo s model
is DJ. Conside ing p oblems o all classes and all job-sizes, FLO
and DJ sol e 34.17% and 16.67% o p oblems, espec i ely and
hose o FLO
swp
, DJ
swp and OLO a e 64.83, 34.33% and 77.83%,
espec i ely. Fu he mo e, he mean CPU imes pe sol ed p oblem
o FLO
swp
, DJ
swp
and OLO a e much be e han hose o FLO and
DJ, espec i ely. I is clea ha he pe o mances o FLO
swp
, DJ
swp
and OLO a e much be e han hose o FLO and DJ, espec i ely.
In conclusion, o TWC p oblems when B uno and Se hi’s
op imal p ope y is included in o MIP models, he e is ema kable

M.-Y. Lin, Y. Kuo / Ope a ions Resea ch Pe spec i es 4 (2017) 49–55 53
Fig. 1. Mean op imali y gap% o TWC p oblems.
Table 3
Mean CPU ime pe sol ed p oblem o TWC.
mean CPU Class 1: basic class Class 2: la ge p ocessing ime Class 3: la ge se up ime
numbe o jobs FLO FLO
SWPT
OLO DJ DJ SWPT FLO FLO
SWPT
OLO DJ DJ
SWPT
FLO FLO SWPT OLO DJ DJ SWPT
10 0.39 0.07 0.13 5.14 0.32 0.15 0.04 0.09 5.27 0.21 1.85 0.11 0.07 1.03 0.07
20 609.84 0.69 0.33 –213.55 26.92 0.44 0.32 –704.24 1725.8 0.68 0.21 –24.83
30 –9.77 2.4 – 223.36 1417.1 4.03 1.28 –1012.96 –8.88 1.84 –809.94
50 –730.05 102.94 –––712.1 36.88 ––– 675.23 130.09 –538.17
75 – – 1110.46 – – – 1202.46 687.65 ––– 1681.6 1348.53 –1725.1
100 – – 2696.27 – – – – 1482.75 ––––2417.4 ––
mean CPU Class 5: la ge numbe o amilies Class 6: mos complex
numbe o jobs FLO FLO
SWPT
OLO DJ DJ SWPT FLO FLO
SWPT
OLO DJ DJ
SWPT
10 0.19 0.02 0.07 7.01 0.81 0.25 0.08 0.05 3.88 1.12
20 108.2 0.48 0.41 – 289.19 208.64 0.48 0.35 –1167.9
30 259.62 6.53 2.48 – 126.91 895.86 11.41 4.06 –834.41
50 –714.1 117.02 –––474.76 196.27 ––
75 –3109.3 1367.41 – – – – 2223.62 ––
100 ––2716.68 –––––––
Table 4
Numbe o sol ed p oblems o TWC.
# sol ed Class 1: basic class Class 2: la ge p ocessing ime Class 3: la ge se up ime Class 5: la ge numbe o amilies Class 6: mos complex
numbe o
jobs
FLO FLO
SWPT
OLO DJ DJ
SWPT
FLO FLO
SWPT
OLO DJ DJ
SWPT
FLO FLO
SWPT
OLO DJ DJ
SWPT
FLO FLO
SWPT
OLO DJ DJ
SWPT
FLO FLO
SWPT
OLO DJ DJ
SWPT
10 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
20 18 20 20 0 16 20 20 20 0 17 3 20 20 0 20 20 20 20 0 5 19 20 20 0 5
30 0 20 20 0 6 8 20 20 0 9 0 20 20 0 19 10 20 20 0 2 7 20 20 0 3
50 0 9 20 0 0 0 17 20 0 0 0 6 20 0 3 0 16 20 0 0 0 15 20 0 0
75 0 0 10 0 0 0 4 17 0 0 0 3 10 0 1 0 1 4 0 0 0 0 7 0 0
100 0 0 4 0 0 0 0 9 0 0 0 0 5 0 0 0 0 1 0 0 0 0 0 0 0
sum 38 69 94 20 42 48 81 106 20 46 23 69 95 20 63 50 77 85 20 27 46 75 87 20 28
imp o emen in compu a ional efficiency. OLO has he bes pe o -
mance and DJ has he wo s pe o mance among he fi e MIP mod-
els wi h espec o bo h he numbe o sol ed p oblems, mean CPU
ime pe sol ed p oblem and mean op imali y gap o all classes
and all job-sizes. OLO sol es all p oblems up o 50-jobs and a ound
50% o 75-job p oblems and nea 20% o 100-job p oblems unde
a ious ope a ing scena ios. On he easiness o p oblem sol ing
in di e en classes/scena ios, class 2, he la ge p ocessing imes
scena io, p oblems a e he easies o sol e o all o mula ions.
3.2. Compu a ional esul s o L
max p oblems
Fo he L
max p oblem, wi h he inclusion o Monma and Po s’
op imal p ope y in o MIP models, based on he mean op imali y
gap ( Fig. 2 ), o all classes he pe o mance o FLO
edd
and OLO a e
be e han ha o FLO; and he pe o mance o DJ
edd
is be e
han ha o DJ.
Table 5 gi es he mean CPU ime pe sol ed p oblem, and Table
6 gi es he numbe o sol ed p oblems o he L
max p oblems.
The bes model is OLO again, bu he pe o mance o OLO o
he L
max p oblems is wo se han ha o he TWC p oblems. Fo
classes 1 o 4 p oblems, OLO sol es all p oblems up o 30-jobs
wi hin 20 s. Fo class 5 p oblems OLO sol es 93% o he p oblems
up o 30-jobs wi hin 3 min. On he numbe o sol ed p oblems
( Table 6 ), conside ing p oblems o all classes and all job-sizes,
FLO and DJ sol e 39.83% and 50.33% o he p oblems, espec i ely
and hose o FLO
edd
, DJ
edd
and OLO a e 84.83, 70.83% and 87.83%,
espec i ely. The pe o mance o FLO
edd
, DJ
edd
and OLO a e be e
han hose o FLO and DJ, espec i ely and hese imp o emen s
a e mo e p o ound han hose o he TWC p oblems.
54 M.-Y. Lin, Y. Kuo / Ope a ions Resea ch Pe spec i es 4 (2017) 49–55
Fig. 2. Mean op imali y gap % o L
max
p oblems.
Table 5
Mean CPU ime pe sol ed p oblem o L
max
p oblems.
mean CPU Class 1: basic class Class 2: la ge p ocessing ime Class 3: la ge se up ime
job size FLO FLO EDD OLO DJ DJ EDD FLO FLO EDD OLO DJ DJ EDD FLO FLO EDD OLO DJ DJ EDD
10 0.51 0.09 0.14 0.3 0.17 0.68 0.1 0.21 0.49 0.27 0.11 0.03 0.02 0.02 0.06
20 67.16 1.21 0.95 76.65 0.85 307.57 2.07 2.34 349.99 238.28 51.27 0.23 0.24 0.31 0.12
30 757.07 8.62 6.67 38.87 1.85 1108.59 29.73 16.95 342.26 111.94 179.77 2.66 1.45 1.13 0.28
50 –167.08 157.07 344.83 121.19 – 655.33 730.79 –73.06 1.05 22.21 24.03 19.62 0.89
75 –130.42 389.1 –24.37 –72.48 285.34 –21.64 3.3 393.9 210.51 567.27 3.14
100 – 856.79 251.21 –124.84 –331.58 897.75 –241.89 –449.43 542.56 550.54 1.97
mean CPU Class 4: small due da es Class 5: la ge numbe o amilies Class 6: mos complex
job size FLO FLO EDD OLO DJ DJ EDD FLO FLO EDD OLO DJ DJ EDD FLO FLO EDD OLO DJ DJ EDD
10 1.58 0.1 0.12 3.22 0.18 0.27 0.06 0.16 0.13 0.2 1.6 0.38 0.35 3.25 1.62
20 –1.92 1.59 – 269.93 184.5 8.26 5.64 171.82 228.41 1553.13 175.44 301.03 – 856.53
30 – 26.19 18.82 –644.27 1200.37 232.53 166.34 472.17 55.27 – 555.57 631.08 –70.7
50 –6 86.4 9 751 – – – 692.15 1163.08 589.59 132.94 –10.22
25.26 ––
75 –773.18 482.36 –– – 20.56 289.76 – 63.27 – 2307.5 963.55 ––
100 –1867.66 1632.17 – – – 45.01 17.22 – 53.63 –– –––
Table 6
Numbe o sol ed p oblems o L
max
p oblems.
# sol ed Class 1: basic class Class 2: la ge p ocessing ime Class 3: la ge se up ime
Numbe o Jobs FLO FLO EDD OLO DJ DJ EDD FLO FLO EDD OLO DJ DJ EDD FLO FLO EDD OLO DJ DJ EDD
10 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
20 20 20 20 20 20 16 20 20 10 20 19 20 20 20 20
30 12 20 20 19 19 7 20 20 8 15 15 20 20 20 20
50 0 18 18 7 16 0 13 14 0 5 1 20 20 20 20
75 0 11 14 0 14 0 6 6 0 4 2 20 20 15 20
100 0 9 9 0 14 0 8 9 0 5 0 16 20 16 20
sum 52 98 101 66 103 43 87 89 38 69 57 116 120 111 120
# sol ed Class 4: small due da es Class 5: la ge numbe o amilies Class 6: mos complex
Numbe o Jobs FLO FLO EDD OLO DJ DJ EDD FLO FLO EDD OLO DJ DJ EDD FLO FLO EDD OLO DJ DJ EDD
10 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20
20 0 20 20 0 20 20 20 20 16 17 1 20 20 0 8
30 0 20 20 0 6 6 16 16 8 9 0 11 12 0 3
50 0 17 19 0 0 0 5 8 3 5 0 1 1 0 0
75 0 7 8 0 0 0 2 3 0 3 0 3 4 0 0
100 0 5 5 0 0 0 1 1 0 2 0 0 0 0 0
sum 20 89 92 20 46 46 64 68 47 56 21 55 57 20 31
Compa a i ely, o he L
max p oblems, he pe o mance o OLO
is he bes among all o mula ions. OLO sol es all p oblems up o
20-jobs, 90% o 30-job p oblems, a ound 50% o he 50-job, 75-job,
and 100-job p oblems. Finally, on he easiness o p oblem sol ing
in di e en ope a ing classes ( Table 6 ) o all he MIP models he
la ge se up ime p oblems (class 3) a e easie o sol e han o he
classes, he nex one is he class 1 p oblems.
4. Conclusion
In his pape , we s udy he compu a ional efficiency o in-
cluding op imal sequence p ope ies in o MIP models o amily
scheduling p oblems. Two se s o MIP models a e cons uc ed:
he fi s se con ains FLO and DJ o mula ions ha do wi hou
he op imal sequence p ope ies and he second se con ains
M.-Y. Lin, Y. Kuo / Ope a ions Resea ch Pe spec i es 4 (2017) 49–55 55
he FLO
swp /edd
, DJ
swp /edd
and OLO models ha include op imal
sequence p ope ies. Based on he expe imen esul s we find ha
he compu a ional efficiencies o he se o MIP models embed-
ded wi h he op imal sequence p ope ies a e much be e han
hose MIP models ha do wi hou op imal sequence p ope ies in
a ious ope a ing scena ios. Among he fi e MIP models s udied,
he bes model o he TWC p oblems is OLO, which sol es all o
he p oblems up o 50-jobs wi hin 4 min and a ound 50% o he
75-job p oblems and nea 20% o he 100-job p oblems wi hin 1 h.
Fo L
max
he bes model is OLO again, which sol es all p oblems up
o 20-jobs, 90% o he 30-job p oblems wi hin 11 min a ound 50%
o he p oblems con aining mo e han 50 jobs wi hin 1 h. Thus o
almos all small size p oblems and some medium size p oblems
applying easy- o-cons uc imp o ed MIP models such as OLO,
p ac i ione s can find he op imal job sequence wi hin an hou .
Re e ences
[1] Bake KR , Kelle B . Sol ing he single-machine sequencing p oblem using in e-
ge p og amming. Compu Ind Eng 2010;59(4):730–5 .
[2] B uno J , Se hi R . Task sequencing in a ba ch en i onmen wi h se up imes. In:
P oceedings o he in e na ional wo kshop o ganized by he commission o he
Eu opean communi ies on modelling and pe o mance e alua ion o compu e
sys ems. No h-Holland Publishing Co; 1976. p. 81–8 .
[3] Cos a A , Cappadonna FA , Fiche a S . Join op imiza ion o a flow -shop g oup
scheduling wi h sequence dependen se -up imes and skilled wo k o ce as-
signmen . In J P od Res 2014a;52(9):2696–728 .
[4] Cos a A , Cappadonna FA , Fiche a S . A hyb id me aheu is ic app oach o mini-
mizing he o al flow ime in a flow shop sequence dependen g oup schedul-
ing p oblem. Algo i hms 2014b;7(3):376–96 .
[5] C auwels HAJ , Po s CN , Van Wassenho e LN . Local sea ch heu is ics o sin-
gle machine scheduling wi h ba ch se -up imes o minimize o al weigh ed
comple ion ime. An Ope Res 1997;70:261–79 .
[6] Ghosh JB , Gup a JN . Ba ch scheduling o minimize maximum la eness. Ope
Res Le 1997;21(2):77–80 .
[7] Jo dan C , D exl A . Disc e e lo sizing and scheduling by ba ch sequencing. Man-
age Sci 1998;44(5):698–713 .
[8] Keha AB , Khowala K , Fowle JW . Mixed in ege p og amming o mula ions o
single machine scheduling p oblems. Compu Ind Eng 2009;56(1):357–67 .
[9] Liao CJ , Liao LM . Single acili y scheduling wi h majo and mino se ups. Com-
pu Ope Res 1997;24(2):169–78 .
[10] Manne AS . On he job-shop scheduling p oblem. Ope Res 1960;8(2):219–23 .
[11] Monma CL , Po s CN . On he complexi y o scheduling wi h ba ch se up imes.
Ope Res 1989;37(5):798–804 .
[12] Neu eld JS , Gup a JND , Busche U . A comp ehensi e e iew o flowshop g oup
scheduling li e a u e. Compu Ope Res 2016;70:56–74 .
[13] Noguei a TH , de Ca alho CRV , Ra e i MG . Analysis o mixed in ege p og am-
ming o mula ions o single machine scheduling p oblems wi h sequence de-
penden se up imes and elease da es. Op imiza ion Online 2014 .
[14] Nowicki E , Zd załka S . Single machine scheduling wi h majo and mino se up
imes: a abu sea ch app oach. J Ope Res Soc 1996;47(8):1054–64 .
[15] Po s CN . An algo i hm o he single machine sequencing p oblem wi h p ece-
dence cons ain s. In: Combina o ial Op imiza ion II. Sp inge ; 1980. p. 78–87 .
[16] Po s CN , Ko alyo MY . Scheduling wi h ba ching: a e iew. Eu J
Ope Res
20 0 0;120(2):228–49 .
[17] Psa a is HN . A dynamic p og amming app oach o sequencing g oups o
iden ical jobs. Ope Res 1980;28(6):1347–59 .
[18] Schalle JE , Gup a JN . Single machine scheduling wi h amily se ups o mini-
mize o al ea liness and a diness. Eu J Ope Res 2008;187(3):1050–68 .
[19] Schu en JMJ , Van de Velde SL , Zijm WHM . Single-machine scheduling wi h e-
lease da es, due da es and amily se up imes. Manage Sci 1996;42(8):1165–74 .
[20] Sousa JP , Wolsey LA . A ime indexed o mula ion o non-p eemp i e single ma-
chine scheduling p oblems. Ma h P og 1992;54(1-3):353–67 .
[21] Uzsoy R , Velásquez JD . Heu is ics o minimizing maximum la eness on
a single machine wi h amily-dependen se -up imes. Compu Ope Res
2008;35(6):2018–33 .
[22] Wagne HM . An in ege linea -p og amming model o machine scheduling.
Na al Res Logis Q 1959;6(2):131–40 .
[23] Webs e S , Bake KR . Scheduling g oups o jobs on a single machine. Ope Res
1995;43(4):692–703 .
[24] Williams D , Wi h A . A new heu is ic o a single machine scheduling p oblem
wi h se -up imes. J Ope Res Soc 1996;47(1):175–80 .
[25] Yin N , Kang L , Wang XY . Single-machine g oup scheduling wi h p ocessing
imes
dependen on posi ion, s a ing ime and allo ed esou ce. Appl Ma h
Model 2014;38(19):4602–13 .