Online scheduling of two job types on a set of multipurpose machines with unit processing times

Publication year: 2012
Source: Computers & Operations Research, Volume 39, Issue 2, February 2012, Pages 405-412

Dvir, Shabtay , Shlomo, Karhi

We study a problem of scheduling a set of n jobs with unit processing times on a set of m multipurpose machines in which the objective is to minimize the makespan. It is assumed that there are two different job types, where each job type can be processed on a unique subset of machines. We provide an optimal offline algorithm to solve the problem in constant time and an online algorithm with a competitive ratio that equals the lower bound. We show that the worst competitive ratio is obtained for an inclusive job-machine structure in which the first job type…