Linear and quadratic algorithms for scheduling chains and opposite chains

Linear and quadratic algorithms for scheduling chains and opposite chains

0.00 Avg rating0 Votes
Article ID: iaor20023210
Country: Netherlands
Volume: 137
Issue: 2
Start Page Number: 248
End Page Number: 264
Publication Date: Mar 2002
Journal: European Journal of Operational Research
Authors: ,
Abstract:

One basic scheduling problem of parallel systems is the scheduling of chains, the simplest form of precedence constraints between tasks. When tasks have unit-execution-times, the simple level algorithm minimizes the schedule length (or makespan). However, the time complexity is linear in the number of tasks and exponential in the size of the problem if a succinct coding is used. If some tasks are multiprocessor tasks, which require more than one processor at a time, the problem becomes more complicated and several NP-hardness results as well as polynomial algorithms (in the number of tasks) for practically important special cases (e.g. opposite chains) were obtained in the literature. Again, these solutions are exponential in the size of the problem if a succinct coding is used. In this paper we re-address the problem of scheduling chains and opposite chains. We consider both preemptive and nonpreemptive schedules. We first propose variants of largest remaining task and highest level first algorithms for chains of unit-width tasks. We than apply these new algorithms to the scheduling of unit-width chains and opposite chains. For the case of unit-width chains, we assume that tasks may have different ready (arrival) times. For both preemptive and nonpreemptive tasks, we obtain optimal scheduling algorithms of quadratic time complexity in the number of chains.

Reviews

Required fields are marked *. Your email address will not be published.