On scheduling cycle shops: Classification, complexity and approximation
The articie treats so called ``cycle shop scheduling problems with \(m\) machines. Cycle shop problems are between flow shop problems and job shop problems. For flow shop problems the machine order is fixed for all jobs and each machine is visited once, for job shop problems any job may have a different processing order on the machines. For cycle shops the machine order is fixed for all jobs, but some machines may be visited several times. In the article an overview about previous complexity results for cycle shop scheduling problems is presented and a classification is given. The classification contains also new results for complexity status (hard or polynomial) of several cycle shop problems, periodic and non-peridiodic problems are analyzed. The authors conjectured that possibly all results about complexity of cycle shop problems are included in this article, since these kind of problems are not well studied yet. At least the article provides a comprehensive overview about cycle shop problems and their complexity.
- A heuristic algorithm for two-machine re-entrant shop scheduling
- A Mathematical Model for Periodic Scheduling Problems
- A new approximation algorithm for UET-scheduling with chain-type precedence constraints.
- A polynomial-time algorithm for the two-machine unit-time release-date job-shop schedule-length problem
- A strongly polynomial algorithm for no-wait cyclic robotic flowshop scheduling
- A study of the cyclic scheduling problem on parallel processors
- An improved algorithm for cyclic flowshop scheduling in a robotic cell
- Complexity of Scheduling under Precedence Constraints
- Complexity results for scheduling chains on a single machine
- Complexity results for single-machine problems with positive finish-start time-lags
- Computational Complexity of Discrete Optimization Problems
- Cyclic Schedules for Job Shops with Identical Jobs
- Cyclic scheduling in robotic flowshops
- Cyclic Scheduling of Identical Parts in a Robotic Cell
- Deterministic Scheduling with Pipelined Processors
- scientific article; zbMATH DE number 1374865 (Why is no real title available?)
- scientific article; zbMATH DE number 3748388 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 830382 (Why is no real title available?)
- Is a unit-job shop not easier than identical parallel machines?
- Makespan minimization for flow-shop problems with transportation times and a single robot
- Minimizing Makespan in a Class of Reentrant Shops
- Minimizing the number of late jobs for the two-machine unit-time job-shop scheduling problem
- Minimizing Total Tardiness on a Single Machine with Precedence Constraints
- NP-complete scheduling problems
- On the complexity of minimizing the number of late jobs in unit time open shop
- Optimization of multistage cyclic service of a production line by a transmanipulator
- Performance Measures and Schedules in Periodic Job Shops
- Preemptive scheduling to minimize mean weighted flow time
- Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness
- Scheduling in Robotic Cells: Classification, Two and Three Machine Cells
- Scheduling in robotic cells: Complexity and steady state analysis
- Scheduling no-wait robotic cells with two and three machines
- Scheduling of parts and robot activities in a two machine robotic cell
- Some complexity results in cyclic scheduling
- Some no-wait shops scheduling problems: Complexity aspect
- Study of a NP-hard cyclic scheduling problem: The recurrent job-shop
- The complexity of a cyclic scheduling problem with identical machines and precedence constraints
- Total completion time minimization in two-machine job shops with unit-time operations
- V-shop scheduling
- Some complexity results in cyclic scheduling
- Minimizing flow time in cyclic schedules for identical jobs with acyclic precedence: The bottleneck lower bound.
- Robotic-cell scheduling: special polynomially solvable cases of the traveling salesman problem on permuted Monge matrices
- Alternation graphs
- Converging to periodic schedules for cyclic scheduling problems with resources and deadlines
- Complete Complexity Classification of Short Shop Scheduling
- Complexity results for weighted timed event graphs
- Complexity of cyclic job shop scheduling problems for identical jobs with no-wait constraints
- The cycle shop scheduling: mathematical model, properties and solution algorithms
- A graph-based analysis of the cyclic scheduling problem with time constraints: schedulability and periodicity of the earliest schedule
- Makespan minimization in reentrant flow shop problem with identical jobs
- On the computational complexity of (maximum) shift class scheduling
- Flow shops with reentry: the total weighted completion time objective
- Throughput-optimal sequences for cyclically operated plants
- Scheduling in reentrant robotic cells: algorithms and complexity
- Semi-transitive orientations and word-representable graphs
- High-multiplicity cyclic job shop scheduling
This page was built for publication: On scheduling cycle shops: Classification, complexity and approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1600002)
