No label defined (Q4336213)
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 1008459
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 1008459 |
Statements
22 April 1998
0 references
open shop
0 references
flow shop
0 references
job shop
0 references
super shop
0 references
makespan
0 references
precedence constraints
0 references
NP-hard
0 references
polynomial-time algorithms
0 references
0.9395430088043212
0 references
0.8482996821403503
0 references
0.8306573629379272
0 references
0.8261017799377441
0 references
The paper considers a scheduling model that generalizes the well-known open shop, flow shop and job shop models. For that model, called the super shop, we study the complexity of minimizing the makespan in both preemptive and nonpreemptive cases assuming that precedence constraints are imposed over the set of jobs. Two types of precedence constraints are considered. For the precedence relations of the first type, job \(J_i\) precedes job \(J_k\) if \(J_k\) may not start on any machine until \(J_i\) is completed on all machines. For the relations of the second type, job \(J_i\) precedes job \(J_k\) if \(J_k\) may not start on any machine until \(J_i\) is completed on that machines. Most of the studied problems are proved to be NP-hard, while for some of them polynomial-time algorithms are presented. For the entire collection see [Zbl 0861.00010].
0 references