A combinatorial Benders decomposition algorithm for parallel machine scheduling with working-time restrictions - Archive ouverte HAL Access content directly
Journal Articles European Journal of Operational Research Year : 2021

A combinatorial Benders decomposition algorithm for parallel machine scheduling with working-time restrictions

(1) , (2) , (3) , (4) , (5, 6)
1
2
3
4
5
6

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.
Not file

Dates and versions

hal-02991368 , version 1 (05-11-2020)

Identifiers

Cite

Kan Fang, Shijin Wang, Michael Pinedo, Lin Chen, Feng Chu. A combinatorial Benders decomposition algorithm for parallel machine scheduling with working-time restrictions. European Journal of Operational Research, 2021, 291 (1), pp.128--146. ⟨10.1016/j.ejor.2020.09.037⟩. ⟨hal-02991368⟩
71 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More