Online scheduling of two job types on a set of multipurpose machines

We study an online-list scheduling problem on a set of m multipurpose machines for which the objective is to minimize the makespan. It is assumed that there are two different job types, and each job type can be processed on a unique subset of machines. We provide an online algorithm with a competitive ratio of 1+k(m−1)/(k(m−s)+s2) where M1={M1,…,Mk} is the set of machines eligible to process jobs of type 1 and where M2={Ms+1,…,Mm} is the set of machines eligible to process jobs of type 2 with k≥s. By analyzing the competitive ratio function, we show that the worst competitive ratio is obtained for an inclusive processing set structure in which the number of machines (m) is even, the first job type can be processed on any of the m machines and the second job type can be processed only on a subset of m/2 machines. Moreover, we provide a lower bound as a function of the processing set structure.