Skip to Main content Skip to Navigation
Journal articles

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

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.
Document type :
Journal articles
Complete list of metadatas

https://hal.archives-ouvertes.fr/hal-02991368
Contributor : Frédéric Davesne <>
Submitted on : Thursday, November 5, 2020 - 11:56:59 PM
Last modification on : Saturday, November 7, 2020 - 3:25:34 AM

Identifiers

Collections

Citation

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, Elsevier, In press, ⟨10.1016/j.ejor.2020.09.037⟩. ⟨hal-02991368⟩

Share

Metrics

Record views

13