384
The heuristic procedure is embedded in a multi-start algorithm, where jobs, machines, and
workers are chosen based on selection probabilities that are determined by priority values. For
the heuristic approach in this paper, we use the setting that is currently used in the underground
mine under consideration. In the corresponding assigning method, jobs and workers are randomly chosen, and machines are selected regarding the shortest driving times to the selected
job or regarding the shortest processing time based on the selected job and the selected worker.
All tests are executed on an Intel i7–7700 K@4.20 GHz machine with 64 GB RAM under Windows 10. The heuristic algorithm is implemented in Xpress IVE 8.4. For the two-stage approach,
we used GAMS 25.1 and GUROBI solver 8.1.0 to solve R-Model and C++ to generate a feasible
solution with the aid of Algorithm 1. Since we schedule only one working shift, we set an upper time
limit of 900 seconds for both approaches that symbolizes a typical duration of a shift handover.
To compare the results achieved by the procedures, we use the value of
dev k
k K
2
∑
that
shows how consistent the desired progress could be implemented at the end of the working
shift compared to the given state at the beginning of the working shift.
Table 2 presents the number of best solutions found and an average gap to the best solution found. Let S i
S S
* be the solution found for instance i by procedure * and S
best be the best
solution found. We calculate
S S
S
i
S
best
i
S S
*
*
to determine the gap for instance i (gap i ). The numbers
presented under “Gap to the best solution found” are obtained by arithmetic averaging over
all instances. Note that the number in parentheses is the obtained gap by arithmetic averaging
over the number of the instances for which the solution found is not equal to the best solution
found (i.e., gap i ≠ 0).
We see that the two-stage approach can find for 70 instances the best solution, where the
solutions found for the other 30 instances are 20.3% far from the best solution found. On
the other hand, the solutions found by the constructive heuristic are on average 45.2% worse
than the best solutions found. This number gets significantly worse (64.6%) if we make an
average over the 70 instances for which the heuristic could not find the best solution. So, we
can conclude that our two-stage approach performs quite promising.
4 CONCLUSION
In this paper, we consider a shift scheduling problem where machines and workers are simultaneously assigned to a selection of the available jobs. We formulate a relaxation of the problem described in Sect. 1 and introduced an algorithm to generate feasible solutions using the
solution achieved by the relaxation. The results of a preliminary performance analysis using
realistic instances show that the solutions of our proposed two-stage approach clearly outperform the solutions which are currently generated by a constructive heuristic procedure.
Future work concerns the development of good lower bounds for our problem. Moreover, the
total output can additionally be taken into account. Considering the trade-off between the presented objective function and the total excavated amount of material could provide new insights.
REFERENCES
Agnetis, A., Murgia, G., & Sbrilli, S., 2014. A job shop scheduling problem with human operators in
handicraft production. International Journal of Production Research 52(13): 3820–3831.
Table 2. Comparison of the approaches.
Number of best
solutions found
Gap to the best
solution found
Two-Stage approach
70
6.1% (20.3%)
Constructive heuristic
30
45.2% (64.6%)
The heuristic procedure is embedded in a multi-start algorithm, where jobs, machines, and
workers are chosen based on selection probabilities that are determined by priority values. For
the heuristic approach in this paper, we use the setting that is currently used in the underground
mine under consideration. In the corresponding assigning method, jobs and workers are randomly chosen, and machines are selected regarding the shortest driving times to the selected
job or regarding the shortest processing time based on the selected job and the selected worker.
All tests are executed on an Intel i7–7700 K@4.20 GHz machine with 64 GB RAM under Windows 10. The heuristic algorithm is implemented in Xpress IVE 8.4. For the two-stage approach,
we used GAMS 25.1 and GUROBI solver 8.1.0 to solve R-Model and C++ to generate a feasible
solution with the aid of Algorithm 1. Since we schedule only one working shift, we set an upper time
limit of 900 seconds for both approaches that symbolizes a typical duration of a shift handover.
To compare the results achieved by the procedures, we use the value of
dev k
k K
2
∑
that
shows how consistent the desired progress could be implemented at the end of the working
shift compared to the given state at the beginning of the working shift.
Table 2 presents the number of best solutions found and an average gap to the best solution found. Let S i
S S
* be the solution found for instance i by procedure * and S
best be the best
solution found. We calculate
S S
S
i
S
best
i
S S
*
*
to determine the gap for instance i (gap i ). The numbers
presented under “Gap to the best solution found” are obtained by arithmetic averaging over
all instances. Note that the number in parentheses is the obtained gap by arithmetic averaging
over the number of the instances for which the solution found is not equal to the best solution
found (i.e., gap i ≠ 0).
We see that the two-stage approach can find for 70 instances the best solution, where the
solutions found for the other 30 instances are 20.3% far from the best solution found. On
the other hand, the solutions found by the constructive heuristic are on average 45.2% worse
than the best solutions found. This number gets significantly worse (64.6%) if we make an
average over the 70 instances for which the heuristic could not find the best solution. So, we
can conclude that our two-stage approach performs quite promising.
4 CONCLUSION
In this paper, we consider a shift scheduling problem where machines and workers are simultaneously assigned to a selection of the available jobs. We formulate a relaxation of the problem described in Sect. 1 and introduced an algorithm to generate feasible solutions using the
solution achieved by the relaxation. The results of a preliminary performance analysis using
realistic instances show that the solutions of our proposed two-stage approach clearly outperform the solutions which are currently generated by a constructive heuristic procedure.
Future work concerns the development of good lower bounds for our problem. Moreover, the
total output can additionally be taken into account. Considering the trade-off between the presented objective function and the total excavated amount of material could provide new insights.
REFERENCES
Agnetis, A., Murgia, G., & Sbrilli, S., 2014. A job shop scheduling problem with human operators in
handicraft production. International Journal of Production Research 52(13): 3820–3831.
Table 2. Comparison of the approaches.
Number of best
solutions found
Gap to the best
solution found
Two-Stage approach
70
6.1% (20.3%)
Constructive heuristic
30
45.2% (64.6%)