The complexity of shop-scheduling problems with two or three jobs
From MaRDI portal
Publication:1178530
DOI10.1016/0377-2217(91)90066-5zbMath0742.90046MaRDI QIDQ1178530
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
Polynomial algorithms; makespan; directed graphs; NP-hardness; job-shop; flow-shop; open-shop; mean flowtime; regular performance measures
90C60: Abstract computational complexity for mathematical programming problems
90B35: Deterministic scheduling theory in operations research
Related Items
The Machine Duplication Problem in a Job Shop with Two Jobs, An actor-critic algorithm with policy gradients to solve the job shop scheduling problem using deep double recurrent agents, Job-shop production scheduling with reverse flows, Using mixed graph coloring to minimize total completion time in job shop scheduling, Job-shop scheduling with multi-purpose machines, 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, A polynomial algorithm for the two machine job-shop scheduling problem with a fixed number of jobs, On the complexity of two machine job-shop scheduling with regular objective functions, Is a unit-job shop not easier than identical parallel machines?, The complexity of two-job shop problems with multi-purpose unrelated machines., 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., NP-hardness of shop-scheduling problems with three jobs, Parallel dedicated machines scheduling with chain precedence constraints, Complexity of mixed shop scheduling problems: A survey, Minimizing the weighted number of tardy jobs on multiple machines: a review, A new lower bound for the job-shop scheduling problem, Parameterized mixed graph coloring, Complexity of shop-scheduling problems with fixed number of jobs: a survey, Complexity of the job insertion problem in multi-stage scheduling
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
