Affiliations: [a] Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, IL 60201, U.S.A. | [b] Universität Paderborn, Department of Mathematics and Computer Science, Warburger Strasse 100, 4790 Paderborn, F.R.G.
Note: [*] Author’s present address: Computer Science Program, University of Texas at Dallas, P.O. Box 688, Richardson, TX 75080, U.S.A.
Note: [**] Part of this work was done while the second author visited the Department of Electrical Engineering and Computer Science, Northwestern University, Evanston.
Abstract: We consider the computational complexity of finding an optimal deadlock recovery. It is known that for an arbitrary number of resource types the problem is NP-hard even when the total cost of deadlocked jobs and the total number of resource units are “small” relative to the number of deadlocked jobs. It is also known that for one resource type the problem is NP-hard when the total cost of deadlocked jobs and the total number of resource units are “large” relative to the number of deadlocked jobs. In this paper we show that for one resource type the problem is solvable in polynomial time when the total cost of deadlocked jobs or the total number of resource units is “small” relative to the number of deadlocked jobs. For fixed m ⩾ 2 resource types, we show that the problem is solvable in polynomial time when the total number of resource units is “small” relative to the number of deadlocked jobs. On the other hand, when the total number of resource units is “large”, the problem becomes NP-hard even when the total cost of deadlocked jobs is “small” relative to the number of deadlocked jobs. The results in the paper, together with previous known ones, give a complete delineation of the complexity of this problem under various assumptions of the input parameters.
