Preemptive job-shop scheduling problems with a fixed number of jobs (Q1299919)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Preemptive job-shop scheduling problems with a fixed number of jobs |
scientific article; zbMATH DE number 1332726
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Preemptive job-shop scheduling problems with a fixed number of jobs |
scientific article; zbMATH DE number 1332726 |
Statements
Preemptive job-shop scheduling problems with a fixed number of jobs (English)
0 references
7 September 1999
0 references
The authors show that the two machine preemptive job-shop problems with mean flow-time or makespan objective function and three jobs are binary NP-hard in contrast to the polynomial solvability of the corresponding nonpreemptive problems with arbitrary but fixed number of jobs. A pseudopolynomial algorithm is constructed for the preemptive problems with fixed numbers of jobs and machines and the same objective functions.
0 references
job-shop problem
0 references
scheduling
0 references
NP-hard
0 references
partition
0 references
