Title: Two, Three, Many or the Complexity of Scheduling with Fixed Number of Jobs
Abstract: SummaryThe paper surveys the complexity of job-shop, flow-shop, open-shop and mixed-shop scheduling problems when the number of jobs n is less or equal to the number of machines m. Almost all shop-scheduling problems with two jobs can be solved in polynomial time for any given regular criterion, but those with three jobs are binary NP-hard. The exceptions are the two job m machine mixed-shop problem without operation preemptions, which is binary NP-hard for any non-trivial regular criterion, and the n job m machine open-shop problem with allowed operation preemptions, which is polynomially solvable for minimizing makespan.
Publication Year: 1995
Publication Date: 1995-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 1
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot