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.
Dell'Olmo, P., Giordani, S., Speranza, M. (1997). An approximation result for a duo-processor task scheduling problem. INFORMATION PROCESSING LETTERS, 61(4), 195-200 [10.1016/S0020-0190(96)00196-2].
An approximation result for a duo-processor task scheduling problem
GIORDANI, STEFANO;
1997-01-01
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 tight.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
