Complexity of mixed shop scheduling problems: A survey

DOI10.1016/S0377-2217(99)00161-7zbMath0949.90047WikidataQ57633958 ScholiaQ57633958MaRDI QIDQ1969835

Frank Werner, Natalia V. Shakhlevich, Yuri N. Sotskov

Publication date: 19 March 2000

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

zbMATH Keywords

polynomial algorithm; NP-hard problem; optimal scheduling; mixture of job and open shops

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C60: Abstract computational complexity for mathematical programming problems

90B35: Deterministic scheduling theory in operations research

Related Items

METAHEURISTICS FOR THE MIXED SHOP SCHEDULING PROBLEM, The complexity of two-job shop problems with multi-purpose unrelated machines., Job-shop scheduling with processing alternatives., Complexity of shop-scheduling problems with fixed number of jobs: a survey, Complete Complexity Classification of Short Shop Scheduling

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The mixed shop scheduling problem
• An efficient algorithm for the job-shop problem with two jobs
• The complexity of shop-scheduling problems with two or three jobs
• Preemptive job-shop scheduling problems with a fixed number of jobs
• Two machine open shop scheduling problem to minimize an arbitrary machine usage regular penalty function
• Scheduling two jobs with fixed and nonfixed routes
• A polynomial algorithm for the two machine job-shop scheduling problem with a fixed number of jobs
• Shop scheduling problems under precedence constraints
• On the complexity of two machine job-shop scheduling with regular objective functions
• NP-hardness of shop-scheduling problems with three jobs
• Shop-scheduling problems with fixed and non-fixed machine orders of the jobs
• Optimal two- and three-stage production schedules with setup times included
• Solution of the Akers-Friedman Scheduling Problem
• Preemptive Scheduling of Independent Jobs with Release and Due Times on Open, Flow and Job Shops
• Scheduling the Open Shop to Minimize Mean Flow Time
• Minimizing Maximum Lateness in a Two-Machine Open Shop
• Two-Machine Super-Shop Scheduling Problem
• Minimizing Mean Flow Time in Two-Machine Open Shops and Flow Shops
• Open Shop Scheduling to Minimize Finish Time
• Flowshop and Jobshop Schedules: Complexity and Approximation
• The Complexity of Flowshop and Jobshop Scheduling
• Computational Complexity of Discrete Optimization Problems
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• A Geometric Model and a Graphical Algorithm for a Sequencing Problem
• A Non-Numerical Approach to Production Scheduling Problems