Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches

DOI10.1016/j.cor.2022.105732OpenAlexW4213419954WikidataQ114193088 ScholiaQ114193088MaRDI QIDQ2147068

Vitaly A. Strusevich

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

zbMATH Keywords

complexityapproximationopen shop schedulingflow shop scheduling

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

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