AN IMPROVED 2.11-COMPETITIVE ALGORITHM FOR ONLINE SCHEDULING ON PARALLEL MACHINES TO MINIMIZE TOTAL WEIGHTED COMPLETION TIME

摘要

We revisit the classical online scheduling problem on parallel machines for minimizing total weighted completion time. In the problem, a set of independent jobs arriving online over time has to be scheduled on identical machines, where the information of each job including its processing time and weight is not known in advance. The goal is to minimize the total weighted completion time of the jobs. For this problem, we propose an improved 2:11-competitive online algorithm based on a kind of waiting strategy.