1 Introduction The multiprocessor scheduling problem, whether it is possible to nonpreemptively schedule a set of independent tasks on m processors to meet a given deadline (with m considered to be an input parameter), is strongly NP-hard [5], and so are most related problems. As a consequence, the study of this area has been mainly concentrating on approximation algorithms: the largest processing time first (LPT) algorithm was first proposed [6] and shown to generate schedules the makespans of which are within {formula} the optimal makespan, and later the Multifit algorithm was introduced in [2], and shown to generate schedules which end within 13/11 the optimal schedule's makespan in [14].
展开▼
