A Competitive Online Algorithm for Minimizing Total Weighted Completion Time on Uniform Machines.
- Resource Type
- Article
- Authors
- Chu, Xuyang; Tao, Jiping
- Source
- Mathematical Problems in Engineering. 4/14/2020, p1-9. 9p.
- Subject
- *TARDINESS
*ONLINE algorithms
*TIME
- Language
- ISSN
- 1024-123X
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 max 2 s max 1 − 1 / 2 ∑ s i , 2 s max / 1 + s max 2.5 − 1 / 2 m by the idea of instance reduction, where s m is the fastest machine speed after being normalized by the slowest machine speed. [ABSTRACT FROM AUTHOR]