Scheduling Partially Ordered Jobs Faster than 2 n
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Michał Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk · Algorithmica · 2012
In a scheduling problem, denoted by 1|prec|∑C i in the Graham notation, we are given a set of n jobs, together with their processing times and precedence constraints. The task is to order the jobs so that their total completion time is minimized. 1|prec|∑C i is a special case of the Traveling Repairman Problem with precedences. A natural dynamic programming algorithm solves both these problems in 2 n n O(1) time, and whether there exists an algorithms solving 1|prec|∑C i in O(c n ) time for some constant c<2 was an open problem posted in 2004 by Woeginger. In this paper we answer this question positively.