First fit decreasing scheduling on uniform multiprocessors

AbstractIndependent tasks are nonpreemptively scheduled on m≥2 processors which are assumed to have different speeds. The purpose of this paper is to show that the worst case ratio of the multifit algorithm MF, which is based on the bin-packing method FFD (first fit decreasing), depends on the order of the processors and that the MF has a better worst case behavior than the well-known LPT algorithm for certain processor configurations