Preemptive job-shop scheduling problems with a fixed number of jobs (Q1299919): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q593590 |
||
| Property / reviewed by | |||
| Property / reviewed by: Feliks R. Bobovich / rank | |||
Revision as of 23:59, 19 February 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Preemptive job-shop scheduling problems with a fixed number of jobs |
scientific article |
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
