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

DOI10.1007/BF01539799zbMATH Open0892.90097MaRDI QIDQ1374404FDOQ1374404

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

Publication date: 4 December 1997

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

Recommendations

• Job Shop Scheduling With Two Jobs And Nonregular Objective Functions
• A neighborhood for complex job shop scheduling problems with regular objectives
• On the complexity of non-preemptive shop scheduling with two jobs
• Tighter bounds on preemptive job shop scheduling with two machines
• Two parallel-machine scheduling problems with function constraint
• Two-machine flow shop scheduling with nonregular criteria
• Two machine open shop scheduling problem to minimize an arbitrary machine usage regular penalty function
• The computational complexities of two multi-purpose machines scheduling problem with setup times
• Heuristic and exact algorithms for the two-machine just in time job shop scheduling problem
• Scheduling the two-machine open shop problem under resource constraints for setting the jobs

zbMATH Keywords

polynomial timenonpreemptive two machine job-shop scheduling

Mathematics Subject Classification ID

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

Cites Work

• Network flows. Theory, algorithms, and applications.
• Title not available (Why is that?)
• The Complexity of Flowshop and Jobshop Scheduling
• NP-hardness of shop-scheduling problems with three jobs
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of shop-scheduling problems with two or three jobs
• An efficient algorithm for the job-shop problem with two jobs
• A polynomial algorithm for the two machine job-shop scheduling problem with a fixed number of jobs
• Title not available (Why is that?)

Cited In (15)

• Two-machine job-shop scheduling with one joint job
• A neighborhood for complex job shop scheduling problems with regular objectives
• Title not available (Why is that?)
• The nonpermutation flowshop scheduling problem: adjustment and bounding procedures
• Complexity of mixed shop scheduling problems: A survey
• Optimal job-shop scheduling with two jobs in systems with unrestricted paths
• Title not available (Why is that?)
• Deterministic job-shop scheduling: Past, present and future
• Job Shop Scheduling With Two Jobs And Nonregular Objective Functions
• A polynomial algorithm for the two machine job-shop scheduling problem with a fixed number of jobs
• Mixed graph colouring as scheduling multi-processor tasks with equal processing times
• Fair optimization and networks: a survey
• Minimizing the weighted number of tardy jobs on multiple machines: a review
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: On the complexity of two machine job-shop scheduling with regular objective functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1374404)