A Competitive Online Algorithm for Minimizing Total Weighted Completion Time on Uniform Machines. (14th April 2020) - Chu, Xuyang; Tao, Jiping
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.