The general algorithm LPT(k) for scheduling identical parallel machines

The paper is devoted to investigate the general algorithm LPT(k). First the tasks are ordered to the LPT order. Then at the same time commonly k tasks are scheduled in a (locally) optimal way (when the increase of the makespan is minimal), and this step is iterated. As our main result, we give the tight value of the theoretical efficiency of the algorithm for every k and every 2 ⩽ m ⩽ 4, where m is the number of machines. Numerical results are also given.