Premium
Lower bound algorithms for multiprocessor task scheduling with ready times
Author(s) -
Caramia Massimiliano,
Dell'Olmo Paolo,
Iovanella Antonio
Publication year - 2005
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2005.00521.x
Subject(s) - multiprocessor scheduling , computer science , multiprocessing , scheduling (production processes) , job shop scheduling , broadcasting (networking) , parallel computing , processor scheduling , upper and lower bounds , task (project management) , distributed computing , algorithm , fair share scheduling , rate monotonic scheduling , mathematical optimization , computer network , quality of service , mathematics , resource (disambiguation) , mathematical analysis , routing (electronic design automation) , management , economics
In this paper, we deal with multiprocessor task scheduling with ready times and prespecified processor allocation. We consider an on‐line scenario where tasks arrive over time, and, at any point in time, the scheduler only has knowledge of the released tasks. An application of this problem arises in wavelength division multiplexing broadcasting where the main future will be in the so‐called one‐to‐many transmission . We propose algorithms to find lower bounds of the minimum makespan, and present experiments on various scenarios.