𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An approximation result for a duo-processor task scheduling problem

✍ Scribed by P. Dell'Olmo; S. Giordani; M.G. Speranza

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
479 KB
Volume
61
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

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. @

πŸ“œ SIMILAR VOLUMES

Complexity and approximation results for
Complexity and approximation results for scheduling multiprocessor tasks on a ring
✍ Giuseppe Confessore; Paolo Dell'Olmo; Stefano Giordani πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 398 KB

We study a multiprocessor task scheduling problem, in which each task requires a set of processors with consecutiveness constraints to be executed. This occurs, for example, when multiple processors are interconnected by communication means, and the minimization of communication time may require the