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 can be processed on any of the m machines while the second job type can be processed only on a subset of
machines. Moreover, we show that our online algorithm is 1‐competitive if the machines are not flexible, i.e., each machine can process only a single job type.
