✦ LIBER ✦

Complexity and approximation results for scheduling multiprocessor tasks on a ring

✍ Scribed by Giuseppe Confessore; Paolo Dell'Olmo; Stefano Giordani

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 398 KB
Volume: 133
Category: Article
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(03)00432-3

No coin nor oath required. For personal study only.

✦ Synopsis

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 processors to be physically adjacent and each multiprocessor task to use only one subset of adjacent processors. In particular, we consider the case in which we have m processors arranged in a ring, and we want to ÿnd a schedule with minimum makespan. We investigate problem complexity, showing that the problem is NP-hard in almost all the possible cases, and provide an approximation algorithm that ÿnds a feasible schedule whose makespan is not greater than two times the optimal value.

📜 SIMILAR VOLUMES

An approximation result for a duo-proces

An approximation result for a duo-processor task scheduling problem

✍ P. Dell'Olmo; S. Giordani; M.G. Speranza 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 479 KB

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 theoreti

A comparison of heuristics for schedulin

A comparison of heuristics for scheduling multiprocessor tasks on three dedicated processors

✍ A.K. Amoura; E. Bampis; Y. Manoussakis; Zs. Tuza 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 266 KB

We consider the problem of scheduling a set of independent multiprocessor tasks on three dedicated processors in order to minimize the makespan. We propose a new heuristic, called Divide Uniprocessor Tasks (DUT), and we provide simulation results comparing the eectiveness of DUT with previously know

Reverse scheduling—an effective method f

Reverse scheduling—an effective method for scheduling tasks of parallel programs employing a divide-and-conquer strategy onto multiprocessors

✍ A Sreenivas; KN Balasubramanya Murthy; C Siva Ram Murthy 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 445 KB

A 53-approximation algorithm for schedul

A 53-approximation algorithm for scheduling vehicles on a path with release and handling times

✍ Daya Ram Gaur; Arvind Gupta; Ramesh Krishnamurti 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 78 KB

A novel time computation model based on

A novel time computation model based on algorithm complexity for data intensive scientific workflow design and scheduling

✍ Jing He; Yanchun Zhang; Guangyan Huang; Chaoyi Pang 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 162 KB 👁 1 views

2-Approximation algorithms for the multi

2-Approximation algorithms for the multi-vehicle scheduling problem on a path with release and handling times

✍ Yoshiyuki Karuno; Hiroshi Nagamochi 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 180 KB

In this paper, given a path G with n vertices v1; v2; : : : ; vn and m identical vehicles, we consider a scheduling problem of the vehicles on the path. Each vertex vj in G has exactly one job j. Any of the n jobs must be served by some vehicle. Each job j has a release time rj and a handling time h