Abstract:
Assigning jobs onto identical machines with the objective to minimize the maximal load is one of the most basic problems in combinatorial optimization and has many practical applications in manufacturing, parallel computation, service industries among others. Motivated by its utilization in product planing and data placement we study a natural extension called Class Constrained Scheduling (CCS). In this problem each job additionally admits a class and each machine can only schedule jobs from at most c different classes for some number c. Even though this problem is closely related to the Class Constraint Bin Packing, the Class Constraint Knapsack and the Cardinality Constraint variants, CCS lacks results regarding approximation algorithms despite being also NP-hard. We fill this gap by analyzing the problem considering three different ways to feasibly allot the jobs: The non-preemptive case, where we have to place the jobs as a whole; the splittable case, where we are allowed to split and allot the jobs arbitrarily as long as they do not overlap on a machine; and finally the preemptive case, where jobs can be split but pieces belonging to the same job are not allowed to be scheduled in parallel. For each case we introduce the first PTAS where neither c nor the number of all classes have to be a constant. In order to achieve this goal, we give new insights about the structure of optimal solutions. In particular we prove that there always exists an optimal solution where the jobs are split evenly and the number of pieces for each job is bounded. Further these job pieces will be placed in just a few specific positions. Moreover, by preprocessing the instance appropriately, we manage to set up a configuration Integer Linear Program (ILP) with a specific form of the constraint matrix called N-fold ILP. These N-fold ILPs can then be solved efficiently. Additionally, we developed the first simple approximation algorithms with constant approximation ratios running in more efficient, polynomial time. The algorithm for the non-preemptive case has a ratio of 7/3 and a running time of O(n2 log(n) + n log2(pmax)). The splittable and the preemptive case admit algorithms with ratio 2 and a running time of O(n2 log(n)). All results also hold when the number of machines cannot be bounded by a polynomial in n.
