Preemptive job-shop scheduling problems with a fixed number of jobs (Q1299919): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Latest revision as of 02:51, 5 March 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
