On contiguous and non-contiguous parallel task scheduling

In this paper we study differences between contiguous and non-contiguous parallel task schedules. Parallel tasks can be executed on more than one processor simultaneously. In the contiguous schedules, indices of the processors assigned to a task must be a sequence of consecutive numbers. In the non-...

Full description

Saved in:
Bibliographic Details
Published in:Journal of scheduling 2015-10, Vol.18 (5), p.487-495
Main Authors: Błądek, Iwo, Drozdowski, Maciej, Guinand, Frédéric, Schepler, Xavier
Format: Article
Language:English
Subjects:
Analysis
Approximation
Artificial Intelligence
Business and Management
Calculus of Variations and Optimal Control
Optimization
Computer Science
Job shops
Microprocessors
Network topologies
Operations Research/Decision Theory
Optimization
Parallel processing
Schedules
Scheduling
Studies
Supply Chain Management
Task scheduling
Tasks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper we study differences between contiguous and non-contiguous parallel task schedules. Parallel tasks can be executed on more than one processor simultaneously. In the contiguous schedules, indices of the processors assigned to a task must be a sequence of consecutive numbers. In the non-contiguous schedules, processor indices may be arbitrary. Optimum non-preemptive schedules are considered. Given a parallel task instance, the optimum contiguous and non-contiguous schedules can be of different lengths. We analyze minimal instances where such a difference may arise, provide bounds on the difference of the two schedules lengths, and prove that deciding whether the difference in schedule length exists is NP-complete.
ISSN:1094-6136
1099-1425
DOI:10.1007/s10951-015-0427-z