Paper Info
Title
A Linear Time Approximation Scheme for the Job Shop Scheduling Problem
Abstract
We study the preemptive and non-preemptive versions of the job shop scheduling problem when the number of machines and the number of operations per job are fixed. We present linear time approximation schemes for both problems. These algorithms are the best possible for such problems in two regards: they achieve the best possible performance ratio since both problems are known to be strongly NP-hard; and they have optimum asymptotic time complexity.
Year
DOI
Venue
1999
10.1007/978-3-540-48413-4_19
RANDOM-APPROX
Keywords
Field
DocType
job shop scheduling problem,linear time approximation scheme,time complexity,linear time
Open shop,Combinatorics,Mathematical optimization,Job shop scheduling,Scheduling (computing),Job shop scheduling problem,Computer science,Flow shop scheduling,Algorithm,Combinatorial optimization,Time complexity,Polynomial-time approximation scheme
Conference
ISBN
Citations 
PageRank 
3-540-66329-0
8
0.81
References 
Authors
7
3
Name
Order
Citations
PageRank
Klaus Jansen178982.68
Roberto Solis-Oba247342.58
MAXIM SVIRIDENKO32072140.65