Single machine flow-time scheduling with scheduled maintenance (Q811593)
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 4216198
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Single machine flow-time scheduling with scheduled maintenance |
scientific article; zbMATH DE number 4216198 |
Statements
Single machine flow-time scheduling with scheduled maintenance (English)
0 references
1992
0 references
We investigate a single machine scheduling problem of minimizing the sum of job flow times subject to scheduled maintenance. We first provide NP- completeness proof for the problem. This proof is much shorter than the one given in the literature. The Shortest Processing Time (SPT) sequence is then shown to have a worst case error bound of 2/7. Furthermore, an example is provided to show that the bound is tight.
0 references
single machine scheduling
0 references
NP-completeness proof
0 references
0.8671872615814209
0 references
0.8510039448738098
0 references
0.8482297658920288
0 references
0.844357430934906
0 references
0.8440997004508972
0 references
