Abstract
This paper addresses a parallel machine scheduling problem with restrictions on employees’ working-times and break times. Tasks must be processed by employees nonpreemptively on unrelated parallel machines with different thresholds that specify for each employee the maximum total and consecutive working-time, and the minimum break time. The objective is to minimize the weighted sum of the makespan, the machine depreciation costs, and the labor costs. To solve this problem, a mixed integer linear programming model is formulated, and two different decomposition-based exact algorithms are implemented as well as a list scheduling (LS)-based heuristic method. Extensive computational experiments are performed on randomly generated instances, and the results demonstrate the efficiency of our proposed combinatorial Benders decomposition approach.
Original language | English |
---|---|
Pages (from-to) | 128-146 |
Number of pages | 19 |
Journal | European Journal of Operational Research |
Volume | 291 |
Issue number | 1 |
DOIs | |
State | Published - May 16 2021 |
Keywords
- Combinatorial Benders decomposition
- Maximum consecutive working-time
- Minimum break time
- Parallel machine
- Scheduling