Preemptive job-shop scheduling problems with a fixed number of jobs

Autor(en): Brucker, P
Kravchenko, SA
Sotskov, YN
Stichwörter: 3 JOBS; ALGORITHM; COMPLEXITY; job-shop problem; Mathematics; Mathematics, Applied; NP-hard; Operations Research & Management Science; scheduling
Erscheinungsdatum: 1999
Herausgeber: SPRINGER HEIDELBERG
Journal: MATHEMATICAL METHODS OF OPERATIONS RESEARCH
Volumen: 49
Ausgabe: 1
Startseite: 41
Seitenende: 76
Zusammenfassung: 
It is shown that the two machine preemptive job-shop problem with mean flow-time or makespan objective function and three jobs is NP-hard. This contrasts the fact that the nonpreemptive versions of these problems are polynomially solvable if the number of jobs is arbitrary but fixed. It is also shown that the preemptive problems can be solved pseudopolynomially if both the number of machines and the number of jobs is fixed.
ISSN: 14322994

Show full item record

Page view(s)

1
Last Week
0
Last month
0
checked on Feb 23, 2024

Google ScholarTM

Check