An asymptotically optimal online algorithm to minimize the total completion time on two multipurpose machines with unit processing times

An asymptotically optimal online algorithm to minimize the total completion time on two multipurpose machines with unit processing times

0.00 Avg rating0 Votes
Article ID: iaor20125787
Volume: 9
Issue: 4
Start Page Number: 241
End Page Number: 248
Publication Date: Nov 2012
Journal: Discrete Optimization
Authors: ,
Keywords: combinatorial optimization, scheduling
Abstract:

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 equ1 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 either of the two machines while jobs belonging to the second set can only be processed on the second machine. We present an online algorithm with a competitive ratio of ρ L B + O ( 1 n ) equ2, where ρ L B equ3 is a lower bound on the competitive ratio of any online algorithm and is equal to 1 + ( α + 4 α 3 α 2 + 2 α 1 2 α 2 + 1 ) 2 equ4 where α = 1 3 + 1 6 ( 116 6 78 ) 1 / 3 + ( 58 + 3 78 ) 1 / 3 3 ( 2 ) 2 / 3 1.918 equ5. This result implies that our online algorithm is asymptotically optimal.

Reviews

Required fields are marked *. Your email address will not be published.