Complexity results for flow shop problems with synchronous movement

DOI10.1016/j.ejor.2014.09.053zbMath1341.90055OpenAlexW2090781654MaRDI QIDQ726218

Sigrid Knust, Stefan Waldherr

Publication date: 8 July 2016

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2014.09.053

zbMATH Keywords

complexityflow shopdominating machinessynchronous movement

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Flow shop scheduling with flexible processing times ⋮ Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches ⋮ The assignment problem with nearly Monge arrays and incompatible partner indices ⋮ Solution algorithms for synchronous flow shop problems with two dominating machines ⋮ Open shop scheduling with synchronization ⋮ Decomposition algorithms for synchronous flow shop problems with additional resources and setup times ⋮ Analysis of flow shop scheduling anomalies ⋮ Synchronous flow shop scheduling with pliable jobs ⋮ The evolution of schematic representations of flow shop scheduling problems ⋮ Three-stage ordered flow shops with either synchronous flow, blocking or no-idle machines

Cites Work

• Unnamed Item
• Flowshop scheduling with dominant machines
• Assembly line balancing in a mixed-model sequencing environment with synchronous transfers.
• No-wait or no-idle permutation flowshop scheduling with dominating machines
• Minimizing Total Tardiness on One Machine is NP-Hard
• Some new results in flow shop scheduling
• A concise survey of efficiently solvable special cases of the permutation flow-shop problem
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
• Flow shop-sequencing problem with synchronous transfers and makespan minimization
• An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs
• A Functional Equation and its Application to Resource Allocation and Sequencing Problems