A Competitive Online Algorithm for Minimizing Total Weighted Completion Time on Uniform Machines
Joint Authors
Source
Mathematical Problems in Engineering
Issue
Vol. 2020, Issue 2020 (31 Dec. 2020), pp.1-9, 9 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2020-04-14
Country of Publication
Egypt
No. of Pages
9
Main Subjects
Abstract EN
We consider the classic online scheduling problem on m uniform machines in the online setting where jobs arrive over time.
Preemption is not allowed.
The objective is to minimize total weighted completion time.
An online algorithm based on the directly waiting strategy is proposed.
Its competitive performance is proved to be max2smax1−1/2∑si,2smax/1+smax2.5−1/2m by the idea of instance reduction, where sm is the fastest machine speed after being normalized by the slowest machine speed.
American Psychological Association (APA)
Chu, Xuyang& Tao, Jiping. 2020. A Competitive Online Algorithm for Minimizing Total Weighted Completion Time on Uniform Machines. Mathematical Problems in Engineering،Vol. 2020, no. 2020, pp.1-9.
https://search.emarefa.net/detail/BIM-1198050
Modern Language Association (MLA)
Chu, Xuyang& Tao, Jiping. A Competitive Online Algorithm for Minimizing Total Weighted Completion Time on Uniform Machines. Mathematical Problems in Engineering No. 2020 (2020), pp.1-9.
https://search.emarefa.net/detail/BIM-1198050
American Medical Association (AMA)
Chu, Xuyang& Tao, Jiping. A Competitive Online Algorithm for Minimizing Total Weighted Completion Time on Uniform Machines. Mathematical Problems in Engineering. 2020. Vol. 2020, no. 2020, pp.1-9.
https://search.emarefa.net/detail/BIM-1198050
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1198050
