On scheduling cycle shops: Classification, complexity and approximation (Q1600002)

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.