Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorRen, Runtianen_US
dc.contributor.authorZhu, Yuqingen_US
dc.contributor.authorLi, Chuanyouen_US
dc.contributor.authorTang, Xueyanen_US
dc.identifier.citationRen, R., Zhu, Y., Li, C. & Tang, X. (2020). Interval job scheduling with machine launch cost. IEEE Transactions On Parallel and Distributed Systems, 31(12), 2776-2788.
dc.description.abstractWe study an interval job scheduling problem in distributed systems. We are given a set of interval jobs, with each job specified by a size, an arrival time and a processing length. Once a job arrives, it must be placed on a machine immediately and run for a period of its processing length without interruption. The homogeneous machines to run jobs have the same capacity limits such that at any time, the total size of the jobs running on any machine cannot exceed its capacity. Launching each machine incurs a fixed cost. After launch, a machine is charged a constant cost per time unit until it is terminated. The problem targets to minimize the total cost incurred by the machines for processing the given set of interval jobs. We focus on the algorithmic aspects of the problem in this article. For the special case where all the jobs have a unit size equal to the machine capacity, we propose an optimal offline algorithm and an optimal 2-competitive online algorithm. For the general case where jobs can have arbitrary sizes, we establish a non-trivial lower bound on the optimal solution. Based on this lower bound, we propose a 5-approximation algorithm in the offline setting. In the non-clairvoyant online setting, we design a O(μ)-competitive Modified First-Fit algorithm which is near optimal (μ is the max/min job processing length ratio). In the clairvoyant online setting, we propose an asymptotically optimal O(logμ)-competitive algorithm based on our Modified First-Fit strategy.en_US
dc.description.sponsorshipMinistry of Education (MOE)en_US
dc.relation.ispartofIEEE Transactions on Parallel and Distributed Systemsen_US
dc.rights© 2020 IEEE. All rights reserved.en_US
dc.subjectEngineering::Computer science and engineeringen_US
dc.titleInterval job scheduling with machine launch costen_US
dc.typeJournal Articleen
dc.contributor.schoolSchool of Computer Science and Engineeringen_US
dc.subject.keywordsJob Schedulingen_US
dc.subject.keywordsOnline Algorithmen_US
dc.description.acknowledgementThis work was supported by the Singapore Ministry of Education Academic Research Fund Tier 1 under Grant 2019-T1002-042, by the NationalNatural Science Foundation of China under Grant 61902063, and by the Provincial Natural Science Foundation of Jiangsu, China under Grant BK20190342.en_US
item.fulltextNo Fulltext-
Appears in Collections:SCSE Journal Articles

Citations 50

Updated on Feb 29, 2024

Web of ScienceTM
Citations 50

Updated on Oct 30, 2023

Page view(s)

Updated on Mar 4, 2024

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.