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

14 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
JournalEuropean Journal of Operational Research
DOIs
StatePublished - Oct 2020

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