An Asymptotically Optimal Online Algorithm to Minimize the Total Completion Time on Two Multipurpose Machines

In the majority of works on online scheduling on multipurpose machines the objective is to minimize the makespan. We, in contrast, consider the objective of minimizing the total completion time. For this purpose, we analyze an online-list scheduling problem of n jobs with unit processing times on a set of two machines working in parallel. Each job belongs to one of two sets of job types. Jobs belonging to the first set can be processed on any of the two machines while jobs belonging to the second set can only be processed on the second machine. Our objective is to assign the jobs to the machines such that the total completion time criterion will be minimized. We suggest using an online algorithm which is based on exploiting the concept of machine flexibility where, as long as a desired competitive ratio is not violating, a job is assigned to the less flexible machine that can process it. We present an online algorithm with a competitive ratio of ρ{LB}+O((1/n)), where ρ{LB} is a lower bound on the competitive ratio of any online algorithm and is equal to 1+(((-α+√(4α³-α²+2α-1))/(2α²+1)))² where α=(1/3)+(1/6)(116-6√(78))^{1/3}+(((58+3√(78))^{1/3})/(3(2)^{2/3}))≈1.918. This yields that ρ{LB} is an irrational number of approximately 1.1573. Moreover, this result implies that our online algorithm is asymptotically optimal.