TY - GEN
T1 - Scheduling fully parallel jobs with integer parallel units
AU - Chau, Vincent
AU - Li, Minming
AU - Wang, Kai
N1 - Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
N2 - 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 jobs, where each job j has sj units of workload, and each unit workload could be executed on any machine at any time unit. A job is said completed when its whole workload has been executed. The objective is to find a schedule that minimizes the total weighted completion time wj Cj, where wj is the weight of job j and Cj is the completion time of job j. We first give a PTAS of this problem when m is constant. Then we study the approximation ratio of a greedy algorithm, Largest-Ratio-First algorithm. Any permutation is a possible outcome of this algorithm when wj = sj for each job j, and for this special case we show that the approximation ratio depends on the instance size, i.e. n and m. Finally, when jobs have arbitrary weights, we prove that the upper bound of the approximation ratio is 1 +m−1.
AB - 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 jobs, where each job j has sj units of workload, and each unit workload could be executed on any machine at any time unit. A job is said completed when its whole workload has been executed. The objective is to find a schedule that minimizes the total weighted completion time wj Cj, where wj is the weight of job j and Cj is the completion time of job j. We first give a PTAS of this problem when m is constant. Then we study the approximation ratio of a greedy algorithm, Largest-Ratio-First algorithm. Any permutation is a possible outcome of this algorithm when wj = sj for each job j, and for this special case we show that the approximation ratio depends on the instance size, i.e. n and m. Finally, when jobs have arbitrary weights, we prove that the upper bound of the approximation ratio is 1 +m−1.
UR - https://www.scopus.com/pages/publications/85018402350
U2 - 10.1007/978-3-319-55911-7_11
DO - 10.1007/978-3-319-55911-7_11
M3 - 会议稿件
AN - SCOPUS:85018402350
SN - 9783319559100
T3 - Lecture Notes in Computer Science
SP - 144
EP - 157
BT - Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings
A2 - Gopal, T.V.
A2 - Jager, Gerhard
A2 - Steila, Silvia
PB - Springer Verlag
T2 - 14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017
Y2 - 20 April 2017 through 22 April 2017
ER -