Journal of the ACM · 1981 · 146 citations · 9 references
ComputingComputer EngineeringComputer ScienceAlgorithmsParallel AlgorithmsSchedulingCpu SchedulingJob SchedulingMachine SchedulingTask SchedulingScheduling In Multiprocessor SystemsUnrelated Parallel Machine Scheduling
Several algorithms are presented for the nonpreemptlve assignment of n independent tasks to m unrelated processors One algorithm requires polynomial Ume in n and m and IS at most 2x/~ times worse than optimal in the worst case This is the best polynomial-time algorithm known for scheduling such sets of tasks. An algorithm with slightly better worst case performance requires polynomial time in n but exponential ume in m This 1s the best algorithm known that requires time O(nlogn) for every fixed value of m KEY WORDS AND PHRASES nonpreemptlve schedules, worst case fimshlng time, performance ratio, unrelated processors, largest processing time CR CATEGORIES' 4 32, 4 35, 5 25, 5 39
9
Algorithms for Scheduling Independent Tasks
Sartaj Sahni · Journal of the ACM · 1976 · 593 citations · Full text
Scheduling independent tasks to reduce mean finishing time
John Bruno, E. G. Coffman, Ravi Sethi · Communications of the ACM · 1974 · 500 citations · Full text