Heuristic algorithms for scheduling independent tasks on nonidentical processors

ABSTRACt. The finishing time properties of several heuristic algorithms for scheduhng n independent tasks on m nonidentical processors are studied In particular, for m = 2 an n log n time-bounded algorithm is given which generates a schedule having a fimshmg Ume of at most (.,/5 + 1)/2 of the optimal hmshmg time A simplified scheduling problem involving identical processors and restricted task sets is shown to be P-complete However, the LPT algorithm applied to this problem yields schedules which are near optimal for large n KEY WORDS AND PHRASES finishing time, heuristic algorithm, scheduling independent tasks, nonidentical processors, identical processors, time-bounded algorithm, LPT schedule, SPT schedule, P-complete prob-lem, time complexity CR CATEGORIES. 4 32, 5 39 1