A Competitive Online Algorithm for Minimizing Total Weighted Completion Time on Uniform Machines. (14th April 2020)

• Record Type: Journal Article
• Authors: Chu, Xuyang; Tao, Jiping
• Other Names: Soldovieri Francesco Academic Editor.
• Is Part Of: Mathematical problems in engineering. Volume 2020(2020)
• Publication Date: 2020-04-14
• Subjects: Engineering mathematics -- Periodicals; 510.2462
• DOI: 10.1155/2020/7527862
• Languages: English
• ISSNs: 1024-123X

Abstract

Abstract : 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.