MultiProcessor Scheduling is PLS-Complete

We consider two natural models of local improvement. We show that the MULTIPROCESSOR SCHEDULING problem, i.e., the problem of scheduling weighted jobs on identical machines with the objective to minimize the makespan, is PLS-complete for a sufficiently large neighborhood. In the first model, in an improvement step, either the makespan decreases or the makespan remains unchanged and the number of makespan machines decreases. In the second model, we consider the selfish version of the problem, where the jobs are viewed as selfish agents. The cost of an agent is the load of the machine to which it is assigned. Agents may form arbitrary, non-fixed coalitions. The cost of a coalition is defined to be the maximum cost of its members. In an improvement step, the cost of the coalition of reallocating agents decreases. Both these problems are PLS-complete for local improvement algorithms with steps which include reallocating up to 33 jobs/agents. We show these results by reduction from the MAXCONSTRAINTASSIGNMENT problem (p,q,r)-MCA, which is an extension of weighted, generalized MAXSAT to higher valued variables. Here, p is the maximum number of variables occurring in a constraint, q is the maximum number of appearances of a variable, and r is the valuedness of the variables. In detail, we use a reduction from (2, 3, r)-MCAbipartite, which is the restriction of (2,3,r)-MCA to instances I, where the graph defined by I is bipartite, and we use some local version of the well-known weighted 3DIMENSIONALMATCHING problem as an intermediate problem in our reduction. In contrast to our results, for k = 1 and k /spl epsilon'/ IN, the solution computed by Graham's LPT-algorithm is locally optimal for both models. To the best of our knowledge, MULTIPROCESSOR SCHEDULING is the first problem, which is known to be solvable in polynomial time for a small neighborhood and PLS-complete for a larger, but still constant, neighborhood.