Mining Goes Digital – Mueller et al. (Eds)
© 2019 Taylor & Francis Group, London, ISBN 978-0-367-33604-2
377
A two-stage solution approach for a shift scheduling problem
with a simultaneous assignment of machines and workers
Cinna Seifi
Clausthal University of Technology, Clausthal-Zellerfeld, Germany
Marco Schulze
K+S Aktiengesellschaft, Kassel, Germany
Jürgen Zimmermann
Clausthal University of Technology, Clausthal-Zellerfeld, Germany
ABSTRACT: We consider a short-term production scheduling problem in a German potash
underground mine where drill-and-blast mining operations have to be assigned to machines and
workers and scheduled simultaneously. In addition, several mining-specific requirements have to
be taken into account. In order to solve the problem at hand, we propose a two-stage solution
approach. In the first stage, we apply a mixed-integer linear program where some time-consuming
restrictions are neglected. Afterward, we modify the obtained schedule by integrating the necessary time intervals that were dismissed within the mathematical model. Since an existing heuristic solution procedure for the same problem is currently in use in a German potash mine, we
will present results for computational experiments conducted on problem instances derived from
real-world data in order to evaluate the performance of the two solution approaches.
1 PROBLEM DESCRIPTION AND LITERATURE REVIEW
This paper addresses a short-term production scheduling problem in a German potash underground mine that was already studied by Schulze & Zimmermann (2017) as well as Schulze
et al. (2017) who proposed a rule-based constructive procedure. The extraction of the examined
potash mine is done by room-and pillar mining method and the excavation of potash is based
on drilling and blasting technique. This kind of underground mining is characterized by eight
consecutive sub-steps, i.e., operations, that can be seen as a production cycle: scaling the roof,
bolting the roof with expansion-shell bolts, drilling large diameter bore holes, removing the
drilled material, drilling blast holes, filling the blast holes with an explosive substance, blasting,
and transportation of the broken material to a crusher. For each operation, except blasting, one
special mobile machine out of a set of identical or uniform machines is required that is handled
by a worker with the corresponding qualification, i.e., skill. Hence, the underlying problem consists of the determination of a shift schedule where (i) a set of jobs
1 has to be selected and determined for execution, (ii) start times of the selected jobs have to be specified, and (iii) machines
and workers have to be assigned to the jobs simultaneously while the individual skills of the
workers as well as the technological-based precedence relations for the jobs have to be taken
into account. The objective is the minimization of the average positive deviation between a
predetermined quantity and the amount of extracted crude salt, cumulated over all operations.
Taking the aforementioned characteristics into consideration, we deal with two different
problem types that have to be solved simultaneously, that is a machine scheduling problem
on the one hand, and an employee timetabling problem on the other hand. The machine
1. Note that a job is characterized by the corresponding operation type from the production cycle and
the place within the mine where the operation has to be executed.
© 2019 Taylor & Francis Group, London, ISBN 978-0-367-33604-2
377
A two-stage solution approach for a shift scheduling problem
with a simultaneous assignment of machines and workers
Cinna Seifi
Clausthal University of Technology, Clausthal-Zellerfeld, Germany
Marco Schulze
K+S Aktiengesellschaft, Kassel, Germany
Jürgen Zimmermann
Clausthal University of Technology, Clausthal-Zellerfeld, Germany
ABSTRACT: We consider a short-term production scheduling problem in a German potash
underground mine where drill-and-blast mining operations have to be assigned to machines and
workers and scheduled simultaneously. In addition, several mining-specific requirements have to
be taken into account. In order to solve the problem at hand, we propose a two-stage solution
approach. In the first stage, we apply a mixed-integer linear program where some time-consuming
restrictions are neglected. Afterward, we modify the obtained schedule by integrating the necessary time intervals that were dismissed within the mathematical model. Since an existing heuristic solution procedure for the same problem is currently in use in a German potash mine, we
will present results for computational experiments conducted on problem instances derived from
real-world data in order to evaluate the performance of the two solution approaches.
1 PROBLEM DESCRIPTION AND LITERATURE REVIEW
This paper addresses a short-term production scheduling problem in a German potash underground mine that was already studied by Schulze & Zimmermann (2017) as well as Schulze
et al. (2017) who proposed a rule-based constructive procedure. The extraction of the examined
potash mine is done by room-and pillar mining method and the excavation of potash is based
on drilling and blasting technique. This kind of underground mining is characterized by eight
consecutive sub-steps, i.e., operations, that can be seen as a production cycle: scaling the roof,
bolting the roof with expansion-shell bolts, drilling large diameter bore holes, removing the
drilled material, drilling blast holes, filling the blast holes with an explosive substance, blasting,
and transportation of the broken material to a crusher. For each operation, except blasting, one
special mobile machine out of a set of identical or uniform machines is required that is handled
by a worker with the corresponding qualification, i.e., skill. Hence, the underlying problem consists of the determination of a shift schedule where (i) a set of jobs
1 has to be selected and determined for execution, (ii) start times of the selected jobs have to be specified, and (iii) machines
and workers have to be assigned to the jobs simultaneously while the individual skills of the
workers as well as the technological-based precedence relations for the jobs have to be taken
into account. The objective is the minimization of the average positive deviation between a
predetermined quantity and the amount of extracted crude salt, cumulated over all operations.
Taking the aforementioned characteristics into consideration, we deal with two different
problem types that have to be solved simultaneously, that is a machine scheduling problem
on the one hand, and an employee timetabling problem on the other hand. The machine
1. Note that a job is characterized by the corresponding operation type from the production cycle and
the place within the mine where the operation has to be executed.