Paper Info
Title
Polynomial Time Approximation Schemes for the Multiprocessor Open and Flow Shop Scheduling Problem
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 mi 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 mi are non-constant.
Year
DOI
Venue
2000
10.1007/3-540-46541-3_38
STACS
Keywords
Field
DocType
parallel identical machine,multiprocessor multi-stage open shop,polynomial time approximation scheme,flow shop scheduling problem,polynomial time approximation schemes,non-preemptive schedule,number mi,multiprocessor open,multiprocessor open shop,preemptive scheduling,scheduling problem,flow shop scheduling
Open shop,Dynamic programming,Approximation algorithm,Mathematical optimization,Multiprocessor scheduling,Job shop scheduling,Computer science,Flow shop scheduling,Multiprocessing,Time complexity
Conference
Volume
ISSN
ISBN
1770
0302-9743
3-540-67141-2
Citations 
PageRank 
References 
13
0.76
11
Authors
2
Name
Order
Citations
PageRank
Klaus Jansen178982.68
MAXIM SVIRIDENKO22072140.65