On scheduling cycle shops: Classification, complexity and approximation (Q1600002)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1751677
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On scheduling cycle shops: Classification, complexity and approximation |
scientific article; zbMATH DE number 1751677 |
Statements
On scheduling cycle shops: Classification, complexity and approximation (English)
0 references
27 July 2003
0 references
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.
0 references
scheduling
0 references
complexity
0 references
classification
0 references
cycle shop
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0.8626759648323059
0 references
0.8626613020896912
0 references
0.81300950050354
0 references
0.8091878890991211
0 references
