Skip to Main content Skip to Navigation
Conference papers

An improved approximation algorithm for scheduling under arborescence precedence constraints

Abstract : We consider a scheduling problem on unrelated machines with precedence constraints. There are m unrelated machines and n jobs and every job has to be processed non-preemptively in some machine. Moreover, jobs have precedence constraints; specifically, a precedence constraint j ≺ j' requires that job j' can only be started whenever job j has been completed. The objective is to minimize the total completion time. The problem has been widely studied in more restricted machine environments such as identical or related machines. However, for unrelated machines, much less is known. In the paper, we study the problem where the precedence constraints form a forest of arborescences. We present a O((log n)2/(log log n)3)-approximation algorithm - that improves the best-known guarantee of O((log n)2/log log n) due to Kumar et al. [12] a decade ago. The analysis relies on a dual-fitting method in analyzing the Lagrangian function of non-convex programs.
Document type :
Conference papers
Complete list of metadatas
Contributor : Frédéric Davesne <>
Submitted on : Sunday, September 20, 2020 - 7:20:08 PM
Last modification on : Wednesday, October 14, 2020 - 4:21:54 AM



Kim Thang Nguyen. An improved approximation algorithm for scheduling under arborescence precedence constraints. 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), Aug 2020, Prague, Czech Republic. pp.MFCS-2020-84, ⟨10.4230/LIPIcs.MFCS.2020.84⟩. ⟨hal-02943776⟩



Record views