Scheduling with storage constraints

Cumulative memory occupation is a quite intuitive but not so studied constraint in scheduling. The interest in such a constraint is present in multi-system-on-chip, embedded systems for storing instruction code, or in scientific computation for storing results. Memory occupation seen as a constraint...

Full description

Saved in:
Bibliographic Details
Main Authors: Saule, E., Dutot, P.-F., Mounie, G.
Format: Conference Proceeding
Language:English
Subjects:
Approximation algorithms
Computer aided instruction
Constraint optimization
Cost function
Embedded computing
Embedded system
Memory management
Physics
Processor scheduling
Scheduling algorithm
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Cumulative memory occupation is a quite intuitive but not so studied constraint in scheduling. The interest in such a constraint is present in multi-system-on-chip, embedded systems for storing instruction code, or in scientific computation for storing results. Memory occupation seen as a constraint is impossible to solve with approximation algorithms. We believe that transforming the constraint into a second objective to optimize helps to deal with such constraints. The problem addressed in this paper is to schedule tasks on identical processors in order to minimize both maximum completion time and maximum cumulative memory occupation. For independent tasks, a family of algorithms with good approximation ratios based on a PTAS is given. Several approximation ratios are proved to be impossible to achieve with any schedule. The precedence constrained case is then studied and a family of performance guaranteed algorithms based on List Scheduling is proposed. Finally, optimizing the mean completion time as a third objective is also studied and a tri-objective algorithm is given.
ISSN:1530-2075
DOI:10.1109/IPDPS.2008.4536292