✦ LIBER ✦

An efficient parallel algorithm for scheduling interval ordered tasks

✍ Scribed by Yoojin Chung; Kunsoo Park

Publisher: Elsevier Science
Year: 2003
Tongue: English
Weight: 187 KB
Volume: 19
Category: Article
ISSN: 0885-064X
DOI: 10.1016/s0885-064x(03)00028-1

No coin nor oath required. For personal study only.

✦ Synopsis

We present an efficient parallel algorithm for scheduling n unit length tasks on m identical processors when the precedence graphs are interval orders. Our algorithm requires Oðlog 2 v þ ðn log nÞ=vÞ time and Oðnv 2 þ n 2 Þ operations on the CREW PRAM, where v can be any number between 1 and n: By choosing v ¼ ffiffi ffi n p

; we obtain an Oð ffiffi ffi n p log nÞ-time algorithm with Oðn 2 Þ operations. For v ¼ n=log n; we have an Oðlog 2 nÞ-time algorithm with Oðn 3 =log 2 nÞ operations. The previous solution takes Oðlog 2 nÞ time with Oðn 3 log 2 nÞ operations on the CREW PRAM. Our improvement is mainly due to a simple dynamic programming recurrence for computing the lengths of optimal schedules and a reduction of the m-processor scheduling problem for interval orders to that of finding a maximum matching in a convex bipartite graph.

📜 SIMILAR VOLUMES

Scheduling Interval Ordered Tasks in Par

Scheduling Interval Ordered Tasks in Parallel

✍ Sivaprakasam Sunder; Xin He 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 148 KB

We present the first NC algorithm for scheduling n unit length tasks on m identical processors for the case where the precedence constraint is an interval order. Our algorithm runs on a priority concurrent read, concurrent write parallel Ž 2 . Ž 5 . Ž 3 . random access machine in O log n with O n pr

An Optimal Algorithm for Scheduling Inte

An Optimal Algorithm for Scheduling Interval Ordered Tasks with Communication on N Processors

✍ H.H. Ali; H. Elrewini 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 506 KB

The problem of scheduling task graphs on multiprocessor systems have received considerable attention in recent years. This problem is known to be NP-hard in its general form as well as many restricted cases. Few polynomial algorithms have been developed for solving special cases of the scheduling pr

Approximation algorithms for general par

Approximation algorithms for general parallel task scheduling

✍ Oh-Heum Kwon; Kyung-Yong Chwa 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 281 KB

A general parallel task scheduling problem is considered. A task can be processed in parallel on one of several alternative subsets of processors. The processing time of the task depends on the subset of processors assigned to the task. We first show the hardness of approximating the problem for bot

Optimizing layer-based scheduling algori

Optimizing layer-based scheduling algorithms for parallel tasks with dependencies

✍ R. Kunis; G. Rünger 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 485 KB

An accurate parallel genetic algorithm t

An accurate parallel genetic algorithm to schedule tasks on a cluster

✍ Michelle Moore 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 234 KB

Recent breakthroughs in the mathematical estimation of parallel genetic algorithm parameters are applied to the NP-complete problem of scheduling multiple tasks on a cluster of computers connected by a shared bus. Numerous adjustments to the original method of parameter estimation were made in order

Efficient Scheduling of Arbitrary Task G

Efficient Scheduling of Arbitrary Task Graphs to Multiprocessors Using a Parallel Genetic Algorithm

✍ Yu-Kwong Kwok; Ishfaq Ahmad 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 492 KB

Given a parallel program represented by a task graph, the objective of a scheduling algorithm is to minimize the overall execution time of the program by properly assigning the nodes of the graph to the processors. This multiprocessor scheduling problem is NP-complete even with simplifying assumptio