We consider the problem of scheduling tasks on a set of dedicated processors, where each task requires a subset of two processors be simultaneously available for a given processing time. The objective is to determine a nonpreemptive schedule with minimum completion time. By means of a graph theoretical formulation, we show that instances with up to 4 processors can be solved in polynomial time. With m = 2s + 1 processors (for s = 2, 3, . . .) and a minimum of m task types, we prove that the problem is NP-hard. Moreover, for this class of NP-hard instances, a simple O(m) approximation algorithm, whose performance ratio is bounded by 3s/(2s + 1), is given. The bound is shown to be tight
An Approximation Result for a Duo-Processor Task Scheduling Problem / Dell'Olmo, Paolo; Giordani, S.; Speranza, M. G.. - In: INFORMATION PROCESSING LETTERS. - ISSN 0020-0190. - 61:(1997), pp. 195-200.
An Approximation Result for a Duo-Processor Task Scheduling Problem
DELL'OLMO, Paolo;
1997
Abstract
We consider the problem of scheduling tasks on a set of dedicated processors, where each task requires a subset of two processors be simultaneously available for a given processing time. The objective is to determine a nonpreemptive schedule with minimum completion time. By means of a graph theoretical formulation, we show that instances with up to 4 processors can be solved in polynomial time. With m = 2s + 1 processors (for s = 2, 3, . . .) and a minimum of m task types, we prove that the problem is NP-hard. Moreover, for this class of NP-hard instances, a simple O(m) approximation algorithm, whose performance ratio is bounded by 3s/(2s + 1), is given. The bound is shown to be tightI documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
