Open-shop scheduling for unit jobs under precedence constraints

作     者：Chen, Yong Goebel, Randy Lin, Guohui Su, Bing Zhang, An 

作者机构：Hangzhou Dianzi Univ Dept Math Hangzhou Peoples R China Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada Xian Technol Univ Sch Econ & Management Xian Peoples R China 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2020年第803卷

页      面：144-151页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：NSFC [11571252, 11771114, 11971139] CSC [201508330054, 201908330090] NSERC Canada 

主　　题：Open-shop scheduling Precedence constraint Directed acyclic graph Approximation algorithm 

摘      要：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. (C) 2019 Elsevier B.V. All rights reserved.