Generalized multifit-type methods for scheduling parallel identical machines

We investigate a very well known NP-complete problem of the scheduling-theory: scheduling of parallel independent machines, that is: How to distribute n tasks among m < n machines as to minimise the overall finishing time. We give a common generalization of two heuristical methods called LPT due to Graham and the method called Multifit. We change the algorithm FFDH (which is an inner part of Multifit) with other algorithms, whereas the theoretical upper bound of the algorithm is the same as the upper bound of LPT. Numerical aspects are also investigated: the results show that the new method often gives better solutions than the others.