×

Open-shop scheduling for unit jobs under precedence constraints. (English) Zbl 1436.90047

The authors present approximation algorithms for the open-shop scheduling problem \(O | p_{ij} = 1, \prec | C_{\max} \) with unit processing times and arbitrary precedence constraints minimizing the makespan.
At first, for the problem \(O3 | p_{ij} = 1, \prec | C_{\max} \) with three machines, a polynomial-time 5/3-approximation algorithm is proposed which is then improved to have approximation ratio 4/3. Finally, the idea is generalized to the \(m\)-machine case leading to the approximation ratio of \(2-\frac{2}{m}\).

MSC:

90B35 Deterministic scheduling theory in operations research
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bräsel, H.; Kluge, D.; Werner, F., A polynomial algorithm for the \([n / m / 0, t_{i j} = 1, t r e e / C_{\max}]\) open shop problem, Eur. J. Oper. Res., 72, 125-134 (1994) · Zbl 0798.90081
[2] Brucker, P., Scheduling Algorithms (2007), Springer: Springer New York · Zbl 1126.90001
[3] Brucker, P.; Jurisch, B.; Jurisch, M. Z., Open shop problems with unit time operations, Oper. Res., 37, 59-73 (1993) · Zbl 0776.90033
[4] Brucker, P.; Knust, S., Complexity results for scheduling problems (2009) · Zbl 0946.90026
[5] Dürr, C., The scheduling zoo (2016)
[6] Gonzalez, T.; Sahni, S., Open shop scheduling to minimize finish time, J. ACM, 23, 665-679 (1976) · Zbl 0343.68031
[7] Graham, R. L., Combinatorial scheduling theory, (Steen, L. A., Mathematics Today Twelve Informal Essays (1978), Springer: Springer New York)
[8] Lenstra, J. K.; Rinnooy Kan, A. H.G., Complexity of scheduling under precedence constraints, Oper. Res., 26, 22-35 (1978) · Zbl 0371.90060
[9] Pinedo, M., Scheduling: Theory, Algorithm and Systems (2016), Springer: Springer New York
[10] Prot, D.; Bellenguez-Morinea, O., A survey on how the structure of precedence constraints may change the complexity class of scheduling problems, J. Sched., 21, 3-16 (2018) · Zbl 1406.90006
[11] Sevastianov, S. V.; Woeginger, G. J., Makespan minimization in open shops: a polynomial time approximation scheme, Math. Program., 82, 191-198 (1998) · Zbl 0920.90075
[12] Sevastianov, S. V.; Woeginger, G. J., Linear time approximation scheme for the multiprocessor open shop problem, Discrete Appl. Math., 114, 273-288 (2001) · Zbl 1020.68016
[13] Tanaev, V. S.; Sotskov, Y. N.; Strusevich, V. A., Scheduling Theory: Multi-Stage Systems (1994), Springer · Zbl 0925.90224
[14] Timkovsky, V. G., Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity, Eur. J. Oper. Res., 149, 355-376 (2003) · Zbl 1030.90027
[15] Williamson, D. P.; Hall, L. A.; Hoogeveen, J. A.; Hurkens, C. A.J.; Lenstra, J. K.; Sevastianov, S. V.; Shmoys, D. B., Short shop schedules, Oper. Res., 45, 288-294 (1997) · Zbl 0890.90112
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.