Polynomial Time Approximation Schemes for the Multiprocessor Open and Flow Shop Scheduling Problem

Klaus Jansen, Maxim SviridenkoSTACS 2000 · OpenReview

Abstract

We investigate the multiprocessor multi-stage open shop and flow shop scheduling problem. In both problems, there are s stages each consisting of a number m i of parallel identical machines for 1 ≤ i ≤ s. Each job consists of s operations with one operation for each stage. The goal is to find a non-preemptive schedule that minimizes the makespan. We propose polynomial time approximation schemes for the multiprocessor open shop and flow shop scheduling problem when the number of stages s is constant and the numbers of machines m i are non-constant.
BibTeX
@inproceedings{jansen2000polynomial,
  author = {Klaus Jansen and Maxim Sviridenko},
  title = {{Polynomial Time Approximation Schemes for the Multiprocessor Open and Flow Shop Scheduling Problem}},
  booktitle = {STACS},
  year = {2000},
  url = {https://openreview.net/forum?id=UIRgqdIjn_P},
}

Loading related content...

Figure