Open-shop scheduling for unit jobs under precedence constraints
Full Text: 1-s2.0-S0304397519306164-main.pdf
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 algorithm based on a partition of the job set into agreeable layers using the natural layered representation of the precedence graph, which is directed acyclic. 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 algorithm. Both approximation algorithms apply to the general m-machine open-shops too.
Citation
Y. Chen, R. Goebel, G. Lin, B. Su, A. Zhang. "Open-shop scheduling for unit jobs under precedence constraints". Theoretical Computer Science, 803, pp 144-151, January 2019.| Keywords: | Open-shop scheduling, Precedence constraint, Directed acyclic graph, Approximation algorithm |
| Category: | In Journal |
| Web Links: | DOI |
| Elsevier |
BibTeX
@article{Chen+al:19,
author = {Yong Chen and Randy Goebel and Guohui Lin and Bing Su and An Zhang},
title = {Open-shop scheduling for unit jobs under precedence constraints},
Volume = "803",
Pages = {144-151},
journal = {Theoretical Computer Science},
year = 2019,
}Last Updated: September 10, 2020Submitted by Sabina P
