Scheduling fully parallel jobs

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalNot applicablepeer-review

View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)619–631
Journal / PublicationJournal of Scheduling
Volume21
Issue number6
Early online date16 Apr 2018
Publication statusPublished - Dec 2018

Abstract

We consider the following scheduling problem. We have m identical machines, where each machine can accomplish one unit of work at each time unit. We have a set of n fully parallel jobs, where each job j has sj units of workload, and each unit workload can be executed on any machine at any time unit. A job is considered complete when its entire workload has been executed. The objective is to find a schedule that minimizes the total weighted completion time ∑wjCj, where wj is the weight of job j and Cj is the completion time of job j. We provide theoretical results for this problem. First, we give a PTAS of this problem with fixed m. We then consider the special case where wj = sj for each job j, and we show that it is polynomial solvable with fixed m. Finally, we study the approximation ratio of a greedy algorithm, the Largest-Ratio-First algorithm. For the special case, we show that the approximation ratio depends on the instance size, i.e. n and m, while for the general case where jobs have arbitrary weights, we prove that the upper bound of the approximation ratio is 1 + (m−1/m+2).

Research Area(s)

  • Approximation ratio, Integer parallel units, Parallel jobs, Total weighted completion time

Citation Format(s)

Scheduling fully parallel jobs. / Wang, Kai; Chau, Vincent; Li, Minming.

In: Journal of Scheduling, Vol. 21, No. 6, 12.2018, p. 619–631.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalNot applicablepeer-review