The Parallel Assignment Problem Redefined

Abstract

We redefine the parallel assignment problem slightly, using a subtler cost function that tends to reduce the number of extra assignments required. We show that the new problem, like the classical, is NP-hard. We then solve the new problem for the restricted case of assignment from invertible functions of single variables. For this restricted case an optimum solution can be found in linear time for both the classical problem and the new problem: but the number of extra assignments required for the classical problem is equal to the number of cycles in the dependency graph, while for the new problem it is equal to the number of isolated cycles in the dependency graph, which may be less. © 1989 IEEE