Using High Performance Computing for Unrelated Parallel Machine Scheduling with Sequence-Dependent Setup Times: Development and Computational Evaluation of a Parallel Branch-and-Price Algorithm

G. Rauchecker, G. Schryen, Computers & Operations Research (2019) 338–357.

Download
OA 4.15 MB
Journal Article | English
Author
;
Abstract
Scheduling problems are essential for decision making in many academic disciplines, including operations management, computer science, and information systems. Since many scheduling problems are NP-hard in the strong sense, there is only limited research on exact algorithms and how their efficiency scales when implemented on parallel computing architectures. We address this gap by (1) adapting an exact branch-and-price algorithm to a parallel machine scheduling problem on unrelated machines with sequence- and machine-dependent setup times, (2) parallelizing the adapted algorithm by implementing a distributed-memory parallelization with a master/worker approach, and (3) conducting extensive computational experiments using up to 960 MPI processes on a modern high performance computing cluster. With our experiments, we show that the efficiency of our parallelization approach can lead to superlinear speedup but can vary substantially between instances. We further show that the wall time of serial execution can be substantially reduced through our parallelization, in some cases from 94 hours to less than six minutes when our algorithm is executed on 960 processes.
Publishing Year
Journal Title
Computers & Operations Research
Issue
104
Page
338-357
LibreCat-ID

Cite this

Rauchecker G, Schryen G. Using High Performance Computing for Unrelated Parallel Machine Scheduling with Sequence-Dependent Setup Times: Development and Computational Evaluation of a Parallel Branch-and-Price Algorithm. Computers & Operations Research. 2019;(104):338-357.
Rauchecker, G., & Schryen, G. (2019). Using High Performance Computing for Unrelated Parallel Machine Scheduling with Sequence-Dependent Setup Times: Development and Computational Evaluation of a Parallel Branch-and-Price Algorithm. Computers & Operations Research, (104), 338–357.
@article{Rauchecker_Schryen_2019, title={Using High Performance Computing for Unrelated Parallel Machine Scheduling with Sequence-Dependent Setup Times: Development and Computational Evaluation of a Parallel Branch-and-Price Algorithm}, number={104}, journal={Computers & Operations Research}, author={Rauchecker, Gerhard and Schryen, Guido}, year={2019}, pages={338–357} }
Rauchecker, Gerhard, and Guido Schryen. “Using High Performance Computing for Unrelated Parallel Machine Scheduling with Sequence-Dependent Setup Times: Development and Computational Evaluation of a Parallel Branch-and-Price Algorithm.” Computers & Operations Research, no. 104 (2019): 338–57.
G. Rauchecker and G. Schryen, “Using High Performance Computing for Unrelated Parallel Machine Scheduling with Sequence-Dependent Setup Times: Development and Computational Evaluation of a Parallel Branch-and-Price Algorithm,” Computers & Operations Research, no. 104, pp. 338–357, 2019.
Rauchecker, Gerhard, and Guido Schryen. “Using High Performance Computing for Unrelated Parallel Machine Scheduling with Sequence-Dependent Setup Times: Development and Computational Evaluation of a Parallel Branch-and-Price Algorithm.” Computers & Operations Research, no. 104, 2019, pp. 338–57.
Main File(s)
Access Level
OA Open Access
Last Uploaded
2019-01-08T14:03:53Z


Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar