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

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

0.00 Avg rating0 Votes
Article ID: iaor2000841
Country: Germany
Volume: 49
Issue: 1
Start Page Number: 41
End Page Number: 76
Publication Date: Jan 1999
Journal: Mathematical Methods of Operations Research (Heidelberg)
Authors: , ,
Abstract:

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 with 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.

Reviews

Required fields are marked *. Your email address will not be published.