On the complexity of two machine job-shop scheduling with regular objective functions

DOI10.1007/BF01539799zbMath0892.90097MaRDI QIDQ1374404

Yuri N. Sotskov, Svetlana A. Kravchenko, Peter Brucker

Publication date: 4 December 1997

Published in: OR Spektrum (Search for Journal in Brave)

zbMATH Keywords

polynomial timenonpreemptive two machine job-shop scheduling

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)

Related Items

Minimizing the weighted number of tardy jobs on multiple machines: a review ⋮ Two-machine job-shop scheduling with one joint job ⋮ Complexity of mixed shop scheduling problems: A survey ⋮ Deterministic job-shop scheduling: Past, present and future ⋮ The nonpermutation flowshop scheduling problem: adjustment and bounding procedures ⋮ Fair optimization and networks: a survey

Cites Work

• An efficient algorithm for the job-shop problem with two jobs
• The complexity of shop-scheduling problems with two or three jobs
• A polynomial algorithm for the two machine job-shop scheduling problem with a fixed number of jobs
• NP-hardness of shop-scheduling problems with three jobs
• The Complexity of Flowshop and Jobshop Scheduling
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item