Short Communication

摘要

In this note, we derive the tight worst case bound 6/2+)1/2~k for scheduling with the MULTIFIT heuristic on tow parallel uniform machines with k calls of FFD within MULTIFIT. When MULTIFIT is combined with LPT as an incumbent algorithm the worst case bound decreases to 2/1+-2+(1/2)~k.