Four decades of research on the open-shop scheduling problem to minimize the makespan
From MaRDI portal
Publication:2239884
DOI10.1016/j.ejor.2021.03.026zbMath1487.90260OpenAlexW3138537503MaRDI QIDQ2239884
Mostafa Khatami, Amir Salehipour, Mohammad Mahdi Ahmadian, Cheng, T. C. Edwin
Publication date: 5 November 2021
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ejor.2021.03.026
Deterministic scheduling theory in operations research (90B35) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)
Related Items
New efficient heuristics for scheduling open shops with makespan minimization, Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches, Decentralized task coordination, A column generation-based heuristic for a rehabilitation patient scheduling and routing problem, A new variable neighbourhood search with a constraint programming search strategy for the open shop scheduling problem with operation repetitions, 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
Uses Software
Cites Work
- Two-machine open-shop scheduling with rejection to minimize the makespan
- The two-machine no-wait general and proportionate open shop makespan problem
- The three-machine proportionate open shop and mixed shop minimum makespan problems
- Efficient approximation algorithms for the routing open shop problem
- Flexible open shop scheduling problem to minimize makespan
- Open shop scheduling problem to minimize makespan with release dates
- A survey on offline scheduling with rejection
- Routing open shop and flow shop scheduling problems
- A mixed-integer linear programming approach to the optimization of event-bus schedules: a scheduling application in the tourism sector
- Scheduling ordered open shops
- Complexity results for flow-shop and open-shop scheduling problems with transportation delays
- Polynomial-time approximation schemes for scheduling problems with time lags
- Jenő Egerváry: from the origins of the Hungarian algorithm to satellite communication
- Properties of optimal schedules in preemptive shop scheduling
- Unit-time scheduling problems with time dependent resources
- Scheduling two-machine no-wait open shops to minimize makespan
- Two-machine flow shop and open shop scheduling problems with a single maintenance window
- A contribution and new heuristics for open shop scheduling
- A note on the proof of the complexity of the little-preemptive open-shop problem
- Compiling finite linear CSP into SAT
- On the complexity of constructing multiprocessor little-preemptive schedules
- Almost nonpreemptive schedules
- On the geometry, preemptions and complexity of multiprocessor and shop scheduling
- Dense open-shop schedules with release times
- An optimal online algorithm for two-machine open shop preemptive scheduling with bounded processing times
- The museum visitor routing problem
- The two-machine open-shop problem with unit-time operations and time delays to minimize the makespan
- Scheduling subject to resource constraints: Classification and complexity
- A block approach for single-machine scheduling with release dates and due dates
- Openshop and flowshop scheduling to minimize sum of completion times
- Minimizing expected makespan in a two-machine stochastic open shop with Poisson arrival
- Shortest common superstrings and scheduling with coordinated starting times
- Some preemptive open shop scheduling problems with a renewable or a nonrenewable resource
- On the optimality of static policy in stochastic open shop
- Open shop scheduling with machine dependent processing times
- The generalized shifting bottleneck procedure
- Nonstrict vector summation in multi-operation scheduling
- A greedy open shop heuristic with job priorities
- On the solution region for certain scheduling problems with preemption
- Makespan minimization in open shops: A polynomial time approximation scheme
- A branch and bound algorithm for a single-machine scheduling problem with positive and negative time-lags
- Classical and new heuristics for the open-shop problem: A computational evaluation
- A heuristic for the two-machine open-shop scheduling problem with transportation times
- A tabu search algorithm for the open shop scheduling problem
- Two machine open shop scheduling problem to minimize an arbitrary machine usage regular penalty function
- Constructive heuristic algorithms for the open shop problem
- Open shops with jobs overlap
- A polynomial algorithm for the \([n/m/0,\;t_{ij}=1,\text{ tree}/C_{\max}\) open shop problem]
- Complexity analysis of job-shop scheduling with deteriorating jobs
- A branch \(\&\) bound algorithm for the open-shop problem
- Open shop problem with zero-one time operations and integer release date/deadline intervals
- Open shop scheduling with maximal machines
- A tabu search algorithm for the open shop problem
- On-line scheduling of two-machine open shops where jobs arrive over time
- Non-preemptive two-machine open shop scheduling with non-availability constraints
- Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity
- Competitive genetic algorithms for the open-shop scheduling problem
- Preemptive scheduling with rejection
- A hybrid genetic algorithm for the open shop scheduling problem
- Group technology approach to the open shop scheduling problem with batch setup times
- Feasible edge colorings of trees with cardinality constraints
- Using intelligent backtracking to improve branch-and-bound methods: An application to Open-Shop problems
- Flow shop and open shop scheduling with a critical machine and two operations per job
- Complexity of some special types of timetabling problems
- Local search with constraint propagation and conflict-based heuristics
- A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
- On the \(m\)-clique free interval subgraphs polytope: polyhedral analysis and applications
- Integrating employee timetabling with scheduling of machines and transporters in a job-shop environment: a mathematical formulation and an anarchic society optimization algorithm
- Partially concurrent open shop scheduling with integral preemptions
- New algorithms and complexity status of the reducibility problem of sequences in open shop scheduling minimizing the makespan
- Two-machine flow-shop scheduling with rejection
- Beam-ACO--hybridizing ant colony optimization with beam search: an application to open shop scheduling
- An introduction to multi-parameter complexity analysis of discrete problems
- A \(\frac 6 5\)-approximation algorithm for the two-machine routing open-shop problem on a two-node network
- Parameterized complexity of machine scheduling: 15 open problems
- Addendum: Some preemptive open shop scheduling problems with a renewable or a nonrenewable resource
- Two-machine shop scheduling problems with batch processing
- Polynomial time approximation algorithms for machine scheduling: Ten open problems
- A 3/2 algorithm for two-machine open shop with route-dependent processing times
- An iterative improvement approach for the nonpreemptive open shop scheduling problem
- 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
- The complexity of two group scheduling problems
- Scheduling shops to minimize the weighted number of late jobs
- Open shop scheduling with some additional constraints
- Restrictions and preassignments in preemptive open shop scheduling
- Open shop, satellite communication and a theorem by Egerváry (1931)
- A new lower bound for the open-shop problem
- 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
- On the set of solutions of the open shop problem
- On the hardness of the classical job shop problem
- Complexity of mixed shop scheduling problems: A survey
- How the difference in travel times affects the optima localization for the routing open shop
- Routing open shop with two nodes, unit processing times and equal number of jobs and machines
- A self-tuning variable neighborhood search algorithm and an effective decoding scheme for open shop scheduling problems with travel/setup times
- A two-level particle swarm optimisation algorithm for open-shop scheduling problem
- Makespan minimization for the \(m\)-machine ordered flow shop scheduling problem
- Coupled task scheduling with exact delays: literature review and models
- Shop scheduling problems with pliable jobs
- Multiagent Scheduling
- Non‐greedy heuristics and augmented neural networks for the open‐shop scheduling problem
- Minimizing the makespan in open‐shop scheduling problems with a convex resource consumption function
- A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process
- Completing Partial Schedules for Open Shop with Unit Processing Times and Routing
- Compact Scheduling In Open Shop With Zero-One Time Operations
- Bounding the Running Time of Algorithms for Scheduling and Packing Problems
- Scheduling
- Stochastic Algorithms: Foundations and Applications
- Open-shop scheduling for unit jobs under precedence constraints
- How good is a dense shop schedule?
- NP-hardness of compact scheduling in simplified open and flow shops.
- Scheduling batches with simultaneous job processing for two-machine shop problems
- On-line scheduling of small open shops
- Solving the open shop scheduling problem
- On the complexity of \(k\)-SAT
- Two-machine open shop scheduling with an availability constraint
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- No-idle, no-wait: when shop scheduling meets dominoes, Eulerian paths and Hamiltonian paths
- Two-machine open shop problem with agreement graph
- A cyclical search for the two machine flow shop and open shop to minimise finishing time
- Open shop scheduling problems with conflict graphs
- Benchmarks for basic scheduling problems
- Applying tabu search to the job-shop scheduling problem
- Two machine open shop scheduling problem with setup, processing and removal times separated
- The representation of partially-concurrent open shop problems
- Open-shop dense schedules: properties and worst-case performance ratio
- A complete 4-parametric complexity classification of short shop scheduling problems
- Scheduling the two-machine open shop problem under resource constraints for setting the jobs
- Complexity of shop-scheduling problems with fixed number of jobs: a survey
- Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard
- Three is easy, two is hard: Open shop sum-batch scheduling problem refined
- Two-machine open shop problem with controllable processing times
- Open-shop batch scheduling with identical jobs
- Complexity of the job insertion problem in multi-stage scheduling
- A heuristic approach to minimize expected makespan in open shops subject to stochastic processing times and failures
- A new particle swarm optimization for the open shop scheduling problem
- Mixed binary integer programming formulations for the reentrant job shop scheduling problem
- The routing open-shop problem on a network: complexity and approximation
- Network flow approaches to pre-emptive open-shop scheduling problems with time-windows
- Optimal scheduling for two-processor systems
- Two-machine shop scheduling: Compromise between flexibility and makespan value
- An algorithm with parameterized complexity of constructing the optimal schedule for the routing open shop problem with unit execution times
- Some positive news on the proportionate open shop problem
- A preemptive open shop scheduling problem with one resource
- On-line two-machine open shop scheduling with time lags
- On the optima localization for the three-machine routing open shop
- Solving the minimum-weighted coloring problem
- An Optimal Constraint Programming Approach to the Open-Shop Problem
- Scheduling Batches with Sequential Job Processing for Two-Machine Flow and Open Shops
- Performance analysis of rotation schedule and improved strategy for open shop problem to minimise makespan
- SCHEDULING PROPORTIONALLY DETERIORATING JOBS IN TWO-MACHINE OPEN SHOP WITH A NON-BOTTLENECK MACHINE
- Improved Approximation Algorithms for Routing Shop Scheduling
- Routing Open Shop with Unrelated Travel Times
- The 2-Machine Routing Open Shop on a Triangular Transportation Network
- Two-machine open shop scheduling with special transportation times
- Inequalities and Bounds in Stochastic Shop Scheduling
- Planning Machine Maintenance in Two-Machine Shop Scheduling
- SOLVING THE OPEN SHOP SCHEDULING PROBLEM VIA A HYBRID GENETIC-VARIABLE NEIGHBORHOOD SEARCH ALGORITHM
- Polynomial-time approximation schemes for two-machine open shop scheduling with nonavailability constraints
- Transporting jobs through a two‐machine open shop
- The Shifting Bottleneck Procedure for Job Shop Scheduling
- Scheduling Open Shops with Unit Execution Times to Minimize Functions of Due Dates
- Preemptive scheduling with staircase and piecewise linear resource availability
- Open-shop scheduling problems with dominated machines
- An Algorithm for Solving the Job-Shop Problem
- A Note on Open Shop Preemptive Schedules
- 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 expected makespan in stochastic open shops
- Minimizing Maximum Lateness in a Two-Machine Open Shop
- Unit Execution Time Shop Problems
- Open shop scheduling with delays
- Open shop problems with unit time operations
- Open Shop Scheduling to Minimize Finish Time
- On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- The open shop scheduling problem with a given sequence of jobs on one machine
- Approximation Algorithms for Three-Machine Open Shop Scheduling
- Scheduling Unit-Time Open Shops with Deadlines
- Some graph‐theoretical models for scheduling in automated production systems
- Nonpreemptive open shop with restricted processing times
- An Overview of Scheduling Problems Arising in Satellite Communications
- Edge-Chromatic Scheduling with Simultaneity Constraints
- Improved Approximation Algorithms for Shop Scheduling Problems
- Printed circuit board family grouping and component allocation for a multimachine, open-shop assembly cell
- On the number of feasible schedules of the open-shop-problem-an application of special latin rectangles
- Two-Machine Open Shops with Renewable Resources
- Stochastic scheduling for a two-machine open shop
- Short Shop Schedules
- Minimizing Makespan in a Class of Reentrant Shops
- Scheduling for parallel dedicated machines with a single server
- 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
- Vector Summation in Banach Space and Polynomial Algorithms for Flow Shops and Open Shops
- An Evolutionary Tabu Search Algorithm And The NHL Scheduling Problem
- Polynomial time algorithms for special open shop problems with precedence constraints and unit processing times
- Competitive two-agent scheduling problems to minimize the weighted combination of makespans in a two-machine open shop
- 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
