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

1 Scopus citations

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
Pages (from-to)128-146
Number of pages19
JournalEuropean Journal of Operational Research
Volume291
Issue number1
DOIs
StatePublished - May 16 2021

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