379
shop (JSP), open shop (OSP), or hybrid job shop (HJSP) scheduling problem. Moreover, we
indicate what kind of objective function as well as formulation is considered within the corresponding study.
In brief, our literature review shows that the approaches discussed in the studies are not
suitable for the problem at hand what is mainly due to the aspects that we consider (i) a
selection of jobs, (ii) setup times for machines and workers, (iii) possible interruption of jobs
at the end of the shift, (iv) breaks that could delay the processing of jobs, and (v) that the
workers can change their machine within a working shift. In the next section, we introduce a
two-stage approach to tackle the problem.
2 TWO-STAGE APPROACH
In our two-stage approach, we first solve a relaxation of the problem described in the previous section using a MIP solver and then, we repair the solution found and generate a feasible one. First, we describe the relaxation (R-Model) of our short-term scheduling problem,
where some restrictions concerning the breaks or technical services are omitted.
Let J be the set of jobs in the underground mine under consideration. Binary decision variables b j are 1 if j J is processed. Moreover, we introduce binary decision variables x jw and y jm
that are 1 if j is processed by worker w W j
W W and machine m G j
G , respectively. G j and W j are
subsets of the set of available machines G and workers W that can process job j. We also define
binary decision variables jwm that are 1 if worker w and machine m are assigned to job j.
m G
jm
j
j
G
y
b
jm
j
j J
∑
∀
j
b j
j j
(1)
w W
jw
j
j
W
x
b
jw
j
j J
∑
∀
j
b j
j j
(2)
x
y
w
m G
jw
jm
jwm
j
j
w W W
j
G
+
≤
y jm
∀
∀ ∈
∀
W W
∈
1 z
j
j J
+
∀
z
j
j j ∈ J J
,
(3)
z
j
w
m G
jwm
j
x w
j
j J w
j
G
≤
∀
x
j j
j
x w
j ∈ ∀
J J
∈
∀
W j
W ,
j
w W j
W
(4)
z
j
w
m G
jwm
j
y m
j
j J w
j j
j
G
≤
∀
y
j j
j
y m
j
j
∈ ∀
J J
∈
∀
W j
W ,
j
w W
W j
W
(5)
Let PT jw
T m be the given parameter that denotes the processing time of job j by worker w
and machine m. The actual processing time of job j is then p
z
PT
j
j
z wm
jw
T m
m G
w W
j
G
j
W
⋅
z
∑ ∑
∑ ∑
. In
Table 1. Literature review.
Production
environment
Objective
function
Formulation
Daniels & Mazzola (1994)
FSP
makespan
time-indexed
Daniels et al. (2004)
FSP
makespan
time-indexed
Huq et al. (2004)
FSP
multi-obj.
seq.-based
Artigues et al. (2006)
JSP
empl. cost
time-indexed
Artigues et al. (2009)
JSP
multi-obj.
seq.-based
Puttkammer et al. (2011)
FSP
multi-obj.
time-indexed
Mencia et al. (2013)
JSP
flow time
Ramya & Chandrasekaran (2014)
JSP
empl. cost
time-indexed
Frihat et al. (2014)
HJSP
empl. cost
seq.-based
Benavides et al. (2014)
FSP
makespan
seq.-based
Guyon et al. (2014)
JSP
empl. cost
Agnetis et al. (2014)
JSP
makespan
seq.-based
Campos Ciro et al. (2016)
OSP
flow time
seq.-based
Ahmadi-Javid & Hooshangi-Tabrizi (2017)
JSP
makespan
seq.-based
Santos et al. (2018)
JSP
throughput
time-indexed
shop (JSP), open shop (OSP), or hybrid job shop (HJSP) scheduling problem. Moreover, we
indicate what kind of objective function as well as formulation is considered within the corresponding study.
In brief, our literature review shows that the approaches discussed in the studies are not
suitable for the problem at hand what is mainly due to the aspects that we consider (i) a
selection of jobs, (ii) setup times for machines and workers, (iii) possible interruption of jobs
at the end of the shift, (iv) breaks that could delay the processing of jobs, and (v) that the
workers can change their machine within a working shift. In the next section, we introduce a
two-stage approach to tackle the problem.
2 TWO-STAGE APPROACH
In our two-stage approach, we first solve a relaxation of the problem described in the previous section using a MIP solver and then, we repair the solution found and generate a feasible one. First, we describe the relaxation (R-Model) of our short-term scheduling problem,
where some restrictions concerning the breaks or technical services are omitted.
Let J be the set of jobs in the underground mine under consideration. Binary decision variables b j are 1 if j J is processed. Moreover, we introduce binary decision variables x jw and y jm
that are 1 if j is processed by worker w W j
W W and machine m G j
G , respectively. G j and W j are
subsets of the set of available machines G and workers W that can process job j. We also define
binary decision variables jwm that are 1 if worker w and machine m are assigned to job j.
m G
jm
j
j
G
y
b
jm
j
j J
∑
∀
j
b j
j j
(1)
w W
jw
j
j
W
x
b
jw
j
j J
∑
∀
j
b j
j j
(2)
x
y
w
m G
jw
jm
jwm
j
j
w W W
j
G
+
≤
y jm
∀
∀ ∈
∀
W W
∈
1 z
j
j J
+
∀
z
j
j j ∈ J J
,
(3)
z
j
w
m G
jwm
j
x w
j
j J w
j
G
≤
∀
x
j j
j
x w
j ∈ ∀
J J
∈
∀
W j
W ,
j
w W j
W
(4)
z
j
w
m G
jwm
j
y m
j
j J w
j j
j
G
≤
∀
y
j j
j
y m
j
j
∈ ∀
J J
∈
∀
W j
W ,
j
w W
W j
W
(5)
Let PT jw
T m be the given parameter that denotes the processing time of job j by worker w
and machine m. The actual processing time of job j is then p
z
PT
j
j
z wm
jw
T m
m G
w W
j
G
j
W
⋅
z
∑ ∑
∑ ∑
. In
Table 1. Literature review.
Production
environment
Objective
function
Formulation
Daniels & Mazzola (1994)
FSP
makespan
time-indexed
Daniels et al. (2004)
FSP
makespan
time-indexed
Huq et al. (2004)
FSP
multi-obj.
seq.-based
Artigues et al. (2006)
JSP
empl. cost
time-indexed
Artigues et al. (2009)
JSP
multi-obj.
seq.-based
Puttkammer et al. (2011)
FSP
multi-obj.
time-indexed
Mencia et al. (2013)
JSP
flow time
Ramya & Chandrasekaran (2014)
JSP
empl. cost
time-indexed
Frihat et al. (2014)
HJSP
empl. cost
seq.-based
Benavides et al. (2014)
FSP
makespan
seq.-based
Guyon et al. (2014)
JSP
empl. cost
Agnetis et al. (2014)
JSP
makespan
seq.-based
Campos Ciro et al. (2016)
OSP
flow time
seq.-based
Ahmadi-Javid & Hooshangi-Tabrizi (2017)
JSP
makespan
seq.-based
Santos et al. (2018)
JSP
throughput
time-indexed