NP-hardness of shop-scheduling problems with three jobs
From MaRDI portal
Publication:1893158
DOI10.1016/0166-218X(93)E0169-YzbMath0837.90072MaRDI QIDQ1893158
Yuri N. Sotskov, Natalia V. Shakhlevich
Publication date: 13 May 1996
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
job-shopmaximum completion timemean flow timeopen-shopoptimal makespancomplexity of shop-schedulingNP-hardness proof
Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)
Related Items
Polynomially solvable cases of the project scheduling problem with changing consumption and supply rates of nonaccumulative resources, Permutation-induced acyclic networks for the job shop scheduling problem, List scheduling algorithms to minimize the makespan on identical parallel machines, Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches, Shop scheduling problems with multiprocessor tasks on dedicated processors, A simulated multi-objective model for flexible job shop transportation scheduling, 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, A graph-based constraint programming approach for the integrated process planning and scheduling problem, A bi-objective branch-and-bound algorithm for the unit-time job shop scheduling: a mixed graph coloring approach, Parallel dedicated machines scheduling with chain precedence constraints, A neural network algorithm for servicing jobs with sequential and parallel machines, Optimizing concurrency under Scheduling by Edge Reversal, An actor-critic algorithm with policy gradients to solve the job shop scheduling problem using deep double recurrent agents, Scheduling large-scale micro/nano biochemical testing: Exact and heuristic algorithms, Dynamic assignment of a multi-skilled workforce in job shops: an approximate dynamic programming approach, Two-machine job-shop scheduling with one joint job, Solving job shop scheduling with setup times through constraint-based iterative sampling: an experimental analysis, Vyacheslav Tanaev: contributions to scheduling and related areas, Job-shop scheduling in a body shop, A job-shop problem with one additional resource type, Complexity of mixed shop scheduling problems: A survey, Complexity of shop-scheduling problems with fixed number of jobs: a survey, Linear programming-based algorithms for the minimum makespan high multiplicity jobshop problem, Mathematical models for preemptive shop scheduling problems, Approximation schemes for job shop scheduling problems with controllable processing times, Approximation results for the two-machine job shop under limited machine availability, Deterministic job-shop scheduling: Past, present and future, The job shop scheduling problem: Conventional and new solution techniques, Quadratic and higher-order unconstrained binary optimization of railway rescheduling for quantum computing
Cites Work
- An efficient algorithm for the job-shop problem with two jobs
- The complexity of shop-scheduling problems with two or three jobs
- Two machine open shop scheduling problem to minimize an arbitrary machine usage regular penalty function
- Solution of the Akers-Friedman Scheduling Problem
- Scheduling the Open Shop to Minimize Mean Flow Time
- 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
- Unnamed Item
