---
_id: '6512'
abstract:
- lang: eng
  text: 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.
author:
- first_name: Gerhard
  full_name: Rauchecker, Gerhard
  last_name: Rauchecker
- first_name: Guido
  full_name: Schryen, Guido
  id: '72850'
  last_name: Schryen
citation:
  ama: '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. <i>Computers &#38; Operations
    Research</i>. 2019;(104):338-357.'
  apa: 'Rauchecker, G., &#38; 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.
    <i>Computers &#38; Operations Research</i>, (104), 338–357.'
  bibtex: '@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 &#38; Operations Research}, publisher={Elsevier},
    author={Rauchecker, Gerhard and Schryen, Guido}, year={2019}, pages={338–357}
    }'
  chicago: '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.”
    <i>Computers &#38; Operations Research</i>, no. 104 (2019): 338–57.'
  ieee: '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,” <i>Computers
    &#38; Operations Research</i>, no. 104, pp. 338–357, 2019.'
  mla: '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.”
    <i>Computers &#38; Operations Research</i>, no. 104, Elsevier, 2019, pp. 338–57.'
  short: G. Rauchecker, G. Schryen, Computers &#38; Operations Research (2019) 338–357.
date_created: 2019-01-08T13:50:44Z
date_updated: 2022-01-06T07:03:08Z
ddc:
- '000'
department:
- _id: '277'
file:
- access_level: open_access
  content_type: application/pdf
  creator: hsiemes
  date_created: 2019-01-08T14:03:53Z
  date_updated: 2019-01-08T14:03:53Z
  file_id: '6513'
  file_name: cor-parallel-bp-for-upmsp.pdf
  file_size: 4153528
  relation: main_file
file_date_updated: 2019-01-08T14:03:53Z
has_accepted_license: '1'
issue: '104'
keyword:
- parallel machine scheduling with setup times
- parallel branch-and-price algorithm
- high performance computing
- master/worker parallelization
language:
- iso: eng
oa: '1'
page: 338-357
publication: Computers & Operations Research
publisher: Elsevier
status: public
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'
type: journal_article
user_id: '61579'
year: '2019'
...