Scheduling fully parallel jobs

Kai Wang (), Vincent Chau () and Minming Li ()
Additional contact information
Kai Wang: City University of Hong Kong
Vincent Chau: Shenzhen Institutes of Advanced Technology
Minming Li: City University of Hong Kong

Journal of Scheduling, 2018, vol. 21, issue 6, No 6, 619-631

Abstract: 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 $$s_j$$ s j 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 $$\sum w_j C_j$$ ∑ w j C j , where $$w_j$$ w j is the weight of job j and $$C_j$$ C j 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 $$w_j = s_j$$ w j = s j 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 + \frac{m-1}{m+2}$$ 1 + m - 1 m + 2 .

Keywords: Approximation ratio; Total weighted completion time; Parallel jobs; Integer parallel units (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10951-018-0563-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:21:y:2018:i:6:d:10.1007_s10951-018-0563-3

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-018-0563-3

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().