Zhang, An; Chen, Yong; Goebel, Randy; Lin, Guohui Open-shop scheduling for unit jobs under precedence constraints. (English) Zbl 1523.90222 Kim, Donghyun (ed.) et al., Combinatorial optimization and applications. 12th international conference, COCOA 2018, Atlanta, GA, USA, December 15–17, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11346, 329-340 (2018). Summary: We study open-shop scheduling for unit jobs under precedence constraints, where if one job precedes another job then it has to be finished before the other job can start to be processed. For the three-machine open-shop to minimize the makespan, we first present a simple 5/3-approximation based on a partition of the job set into agreeable layers using the natural layered representation of the precedence graph. We then show a greedy algorithm to reduce the number of singleton-job layers, resulting in an improved partition, which leads to a 4/3-approximation. Both approximation algorithms apply to the general \(m\)-machine open-shops too.For the entire collection see [Zbl 1407.68037]. MSC: 90B35 Deterministic scheduling theory in operations research 68W25 Approximation algorithms Keywords:open-shop scheduling; precedence constraint; directed acyclic graph; approximation algorithm PDFBibTeX XMLCite \textit{A. Zhang} et al., Lect. Notes Comput. Sci. 11346, 329--340 (2018; Zbl 1523.90222) Full Text: DOI