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

Kan Fang, Shijin Wang, Michael L. Pinedo, Lin Chen, Feng Chu

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
JournalEuropean Journal of Operational Research
DOIs
StateAccepted/In press - 2020

Keywords

  • Combinatorial Benders decomposition
  • Maximum consecutive working-time
  • Minimum break time
  • Parallel machine
  • Scheduling

Fingerprint Dive into the research topics of 'A combinatorial Benders decomposition algorithm for parallel machine scheduling with working-time restrictions'. Together they form a unique fingerprint.

Cite this