Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches
From MaRDI portal
Publication:2147068
DOI10.1016/j.cor.2022.105732OpenAlexW4213419954WikidataQ114193088 ScholiaQ114193088MaRDI QIDQ2147068
Publication date: 22 June 2022
Published in: Computers \& Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.cor.2022.105732
Related Items
An FPTAS for scheduling with resource constraints, A constraint programming-based iterated greedy algorithm for the open shop with sequence-dependent processing times and makespan minimization, A genetic algorithm for scheduling open shops with conflict graphs to minimize the makespan
Cites Work
- The two-machine no-wait general and proportionate open shop makespan problem
- The three-machine proportionate open shop and mixed shop minimum makespan problems
- The assignment problem with nearly Monge arrays and incompatible partner indices
- Efficient approximation algorithms for the routing open shop problem
- A survey on offline scheduling with rejection
- Routing open shop and flow shop scheduling problems
- Two-machine flow shop scheduling problem with an outsourcing option
- Approximation algorithms for the parallel flow shop problem
- Scheduling with time-changing effects and rate-modifying activities
- Scheduling ordered open shops
- Complexity results for flow-shop and open-shop scheduling problems with transportation delays
- Scheduling three-operation jobs in a two-machine flow shop to minimize makespan
- Two-machine flow shop and open shop scheduling problems with a single maintenance window
- Complexity results for flow shop problems with synchronous movement
- V-shop scheduling
- Seven problems: so different yet close
- A survey of results for sequencing problems with controllable processing times
- Time-dependent scheduling
- Approximation results for flow shop scheduling problems with machine availability constraints
- Dense open-shop schedules with release times
- An optimal online algorithm for two-machine open shop preemptive scheduling with bounded processing times
- Scheduling incompatible tasks on two machines
- Scheduling subject to resource constraints: Classification and complexity
- Analysis of a linear programming heuristic for scheduling unrelated parallel machines
- The mixed shop scheduling problem
- A two-machine flow shop scheduling problem with controllable job processing times
- On the two-phase method for preemptive scheduling
- Value of the Steinitz constant
- Scheduling open shops with parallel machines
- Minimization of resource consumption under a given deadline in the two- processor flow-shop scheduling problem
- Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard
- Nonstrict vector summation in multi-operation scheduling
- A greedy open shop heuristic with job priorities
- A heuristic algorithm for two-machine re-entrant shop scheduling
- Approximability of flow shop scheduling
- Makespan minimization in open shops: A polynomial time approximation scheme
- Approximation algorithms for two-machine flow shop scheduling with batch setup times
- Minimization of the makespan in a two-machine problem under given resource constraints
- A heuristic for the two-machine open-shop scheduling problem with transportation times
- Heuristics for short route job shop scheduling problems
- Approximation algorithms for the multiprocessor open shop scheduling problem
- An approximation algorithm for the \(m\)-machine permutation flow shop scheduling problem with controllable processing times
- Worst-case analysis of heuristics for open shops with parallel machines
- Two machine open shop scheduling problem to minimize an arbitrary machine usage regular penalty function
- Optimal job-shop scheduling with two jobs in systems with unrestricted paths
- On some geometric methods in scheduling theory: A survey
- Complexity analysis of job-shop scheduling with deteriorating jobs
- Shop scheduling problems under precedence constraints
- An open shop scheduling problem with a non-bottleneck machine
- Open shop scheduling with maximal machines
- On-line scheduling of two-machine open shops where jobs arrive over time
- Non-preemptive two-machine open shop scheduling with non-availability constraints
- Preemptive scheduling with rejection
- A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem
- Heuristics for the two-stage job shop scheduling problem with a bottleneck machine
- Group technology approach to the open shop scheduling problem with batch setup times
- Flow shop and open shop scheduling with a critical machine and two operations per job
- Two-stage open shop scheduling with a bottleneck machine
- Geometrical heuristics for multiprocessor flowshop scheduling with uniform machines at each stage
- Open shop scheduling with synchronization
- Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: a review of solution approaches
- Two-machine flow-shop scheduling with rejection
- A \(\frac 6 5\)-approximation algorithm for the two-machine routing open-shop problem on a two-node network
- Two-machine shop scheduling problems with batch processing
- Two machine flow shop scheduling problem with no wait in process: Controllable machine speeds
- Polynomial time approximation algorithms for machine scheduling: Ten open problems
- A 3/2 algorithm for two-machine open shop with route-dependent processing times
- The two-machine open shop problem: To fit or not to fit, that is the question
- A polynomial-time open-shop problem with an arbitrary number of machines
- Two machine mixed shop scheduling problem with controllable machine speeds
- A linear time approximation scheme for makespan minimization in an open shop with release dates
- Comments on Flow shop and open shop scheduling with a critical machine and two operations per job
- Complexity of flow shop scheduling problems with transportation constraints
- NP-hardness of shop-scheduling problems with three jobs
- Open shop, satellite communication and a theorem by Egerváry (1931)
- Perspectives of Monge properties in optimization
- Approximation algorithms for parallel open shop scheduling
- A polynomial algorithm for the three-machine open shop with a bottleneck machine
- When difference in machine loads leads to efficient scheduling in open shops
- Scheduling with batching: A review
- A new algorithm for the two-machine open shop and the polynomial solvability of a scheduling problem with routing
- Three-machine open shop with a bottleneck machine revisited
- How the difference in travel times affects the optima localization for the routing open shop
- Two-stage open-shop scheduling with a two-machine flow shop as a stage: approximation algorithms and empirical experiments
- Four decades of research on the open-shop scheduling problem to minimize the makespan
- Approximation algorithms for the three-machine proportionate mixed shop scheduling
- A cyclical search for the two machine flow shop and open shop to minimise finishing time
- Two machine open shop scheduling problem with setup, processing and removal times separated
- A network flow-based method to solve performance cost and makespan open-shop scheduling problems with time-windows
- A survey of scheduling with controllable processing times
- Open-shop dense schedules: properties and worst-case performance ratio
- A complete 4-parametric complexity classification of short shop scheduling problems
- Three is easy, two is hard: Open shop sum-batch scheduling problem refined
- Two-machine open shop problem with controllable processing times
- Approximation schemes for job shop scheduling problems with controllable processing times
- The routing open-shop problem on a network: complexity and approximation
- Two-machine flow shop no-wait scheduling with machine maintenance
- Two-machine shop scheduling: Compromise between flexibility and makespan value
- Some positive news on the proportionate open shop problem
- On-line two-machine open shop scheduling with time lags
- Two-Machine No-Wait Flow Shop Scheduling with Missing Operations
- Sequencing n Jobs on Two Machines with Arbitrary Time Lags
- Optimal two- and three-stage production schedules with setup times included
- Scheduling Batches with Sequential Job Processing for Two-Machine Flow and Open Shops
- Review of the ordered and proportionate flow shop scheduling research
- The 2-Machine Routing Open Shop on a Triangular Transportation Network
- An FPTAS for scheduling a two-machine flowshop with one unavailability interval
- Two-machine open shop scheduling with special transportation times
- Planning Machine Maintenance in Two-Machine Shop Scheduling
- Fifty years of scheduling: a survey of milestones
- Polynomial-time approximation schemes for two-machine open shop scheduling with nonavailability constraints
- AN IMPROVED APPROXIMATION ALGORITHM FOR THE TWO-MACHINE FLOW SHOP SCHEDULING PROBLEM WITH AN INTERSTAGE TRANSPORTER
- On the Power of Linear Dependencies
- Transporting jobs through a two‐machine open shop
- TWO MACHINE OPEN SHOP SCHEDULING PROBLEM WITH CONTROLLABLE MACHINE SPEEDS
- Open-shop scheduling problems with dominated machines
- The Two-Machine Maximum Flow Time Problem with Series-Parallel Precedence Constraints: An Algorithm and Extensions
- A Note on Open Shop Preemptive Schedules
- Sequencing to Minimize the Maximum Job Cost
- The Two-Machine Maximum Flow Time Problem with Series Parallel Precedence Relations
- Sequencing with Series-Parallel Precedence Constraints
- Complexity of Scheduling Shops with No Wait in Process
- Preemptive Scheduling of Independent Jobs with Release and Due Times on Open, Flow and Job Shops
- Algorithms for Edge Coloring Bipartite Graphs and Multigraphs
- Minimizing Maximum Lateness in a Two-Machine Open Shop
- Two-Machine Super-Shop Scheduling Problem
- Compact Cylindrical Chromatic Scheduling
- Optimal choice of machine speeds for two-stage non-homogeneous systems
- Open Shop Scheduling to Minimize Finish Time
- Flowshop and Jobshop Schedules: Complexity and Approximation
- On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
- The Complexity of Flowshop and Jobshop Scheduling
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey
- The open shop scheduling problem with a given sequence of jobs on one machine
- Approximation Algorithms for Three-Machine Open Shop Scheduling
- Nonpreemptive open shop with restricted processing times
- On non-permutation solutions to some two machine flow shop scheduling problems
- A New Heuristic for Three-Machine Flow Shop Scheduling
- Routing Two-Machine Flowshop Problems on Networks with Special Structure
- Two-Machine Open Shops with Renewable Resources
- An O(n log n) Algorithm for the Two-Machine Flow Shop Problem with Controllable Machine Speeds
- Short Shop Schedules
- Minimizing Makespan in a Class of Reentrant Shops
- A Simple Heuristic for m-Machine Flow-Shop and its Applications in Routing-Scheduling Problems
- Three-machine shop scheduling with partially ordered processing routes
- A dynamic programming algorithm for scheduling jobs in a two-machine open shop with an availability constraint
- NP-hard cases in scheduling deteriorating jobs on dedicated machines
- An NP-Hard Open Shop Scheduling Problem with Polynomial Average Time Complexity
- Dual criteria preemptive open-shop problems with minimum makespan
- An Algorithm for the Open-Shop Problem
- Sequencing n jobs on two machines with setup, processing and removal times separated
- Vector Summation in Banach Space and Polynomial Algorithms for Flow Shops and Open Shops
- Polynomial time approximation algorithms for proportionate open‐shop scheduling
- O(log m)-approximation for the routing open shop problem
- On the routing open shop problem with two machines on a two-vertex network
- The open shop problem with routing at a two-node network and allowed preemption
- Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
- Flow shop-sequencing problem with synchronous transfers and makespan minimization
- Minimizing the makespan in open‐shop scheduling problems with a convex resource consumption function
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Convex Resource Allocation Problems on Directed Acyclic Graphs: Duality, Complexity, Special Cases, and Extensions
- Scheduling
- How good is a dense shop schedule?
- Machine scheduling with transportation considerations
- Scheduling batches with simultaneous job processing for two-machine shop problems
- On-line scheduling of small open shops
- Two-machine open shop scheduling with an availability constraint
- Two-machine flow shops with limited machine availability
- A 3/2-approximation algorithm for two-machine flow-shop sequencing subject to release dates.
- Linear time approximation scheme for the multiprocessor open shop problem
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item