An Almost-Optimal Algorithm for the Assembly Line Scheduling Problem
- 1 November 1974
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-23 (11) , 1169-1174
- https://doi.org/10.1109/t-c.1974.223825
Abstract
This paper considers a solution to the multiprocessor scheduling problem for the case where the ordering relation between tasks can be represented as a tree. Assume that we have n identical processors, and a number of tasks to perform. Each task Tirequires an amount of time μito complete, 0 < μi≤ k, so that k is an upper bound on task time. Tasks are indivisible, so that a processor once assigned must remain assigned until the task completes (no preemption). Then the "longest path" scheduling method is almost-optimal in the following sense.Keywords
This publication has 0 references indexed in Scilit: