The problem of minimizing makespan (maximum completion time) on uniform machines with restricted assignment is considered. The machines differ in their speeds and functionalities. Each job has a set of machines to which it can be assigned, called its processing set. The goal is to finish the jobs as soon as possible. There exist 4/3-approximation algorithms for the cases of inclusive and tree-hierarchical assignment restrictions, under an assumption that machines with higher capabilities also run at higher speeds. We eliminate the assumption and present algorithms with approximation ratios 2 and 4/3 for both cases.
Keywords: inclusive restriction; makespan; scheduling; tree-hierarchical restriction; uniform machines.