Parallel machine scheduling of machine-dependent jobs with unit-length

In this paper we study the parallel machine scheduling problem with unit-length jobs in which each job j is only allowed to be processed on a specified subset ℳj of machines. For the problem P|pj = 1, ℳj|Cmax where the subset family {ℳj} is nested, Pinedo established a least flexible job first algorithm. We further present polynomial algorithms for the problem with general subset family {ℳj}. As a generalization of the problem for nested family, we consider the problem for convex subset family {ℳj} and present an efficient algorithm for solving it.