EXACT BOUNDS OF THE MODIFIED LPT ALGORITHMS APPLYING TO PARALLEL MACHINES SCHEDULING WITH NONSIMULTANEOUS MACHINE AVAILABLE TIMES

摘要

In this paper, we consider Parallel Machines Scheduling with nonsimultaneous machine available time. We give the exact worst case performance bound of MLPT proposed by Lee. Fur- thermore, two other modified LPT algorithms are discussed. The paper is ended by numerical ex- periments of these algorithms.