The complexity of shop-scheduling problems with two or three jobs

DOI10.1016/0377-2217(91)90066-5zbMath0742.90046OpenAlexW2068615854MaRDI QIDQ1178530

Yuri N. Sotskov

Publication date: 26 June 1992

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(91)90066-5

zbMATH Keywords

Polynomial algorithmsmakespandirected graphsNP-hardnessjob-shopflow-shopopen-shopmean flowtimeregular performance measures

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 ⋮ A polynomial algorithm for the two machine job-shop scheduling problem with a fixed number of jobs ⋮ A new lower bound for the job-shop scheduling problem ⋮ NP-hardness of shop-scheduling problems with three jobs ⋮ Job-shop production scheduling with reverse flows ⋮ Using mixed graph coloring to minimize total completion time in job shop scheduling ⋮ On the complexity of two machine job-shop scheduling with regular objective functions ⋮ Parallel dedicated machines scheduling with chain precedence constraints ⋮ Is a unit-job shop not easier than identical parallel machines? ⋮ An actor-critic algorithm with policy gradients to solve the job shop scheduling problem using deep double recurrent agents ⋮ Parameterized mixed graph coloring ⋮ Two-machine job-shop scheduling with one joint job ⋮ The complexity of two-job shop problems with multi-purpose unrelated machines. ⋮ The Machine Duplication Problem in a Job Shop with Two Jobs ⋮ Job-shop scheduling with multi-purpose machines ⋮ Complexity of mixed shop scheduling problems: A survey ⋮ Complexity of shop-scheduling problems with fixed number of jobs: a survey ⋮ Complexity of the job insertion problem in multi-stage scheduling ⋮ Lower bounds for the job-shop scheduling problem on multi-purpose machines ⋮ Deterministic job-shop scheduling: Past, present and future ⋮ A lower bound for the job insertion problem. ⋮ The job shop scheduling problem: Conventional and new solution techniques ⋮ Two machine open shop scheduling problem to minimize an arbitrary machine usage regular penalty function ⋮ Scheduling two jobs with fixed and nonfixed routes

Cites Work

• An efficient algorithm for the job-shop problem with two jobs
• Solution of the Akers-Friedman Scheduling Problem
• Open Shop Scheduling to Minimize Finish Time
• On general routing problems
• A Geometric Model and a Graphical Algorithm for a Sequencing Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item