Makespan minimization for multiple uniform machines

摘要

We consider a classical scheduling problem with makespan minimization on uniform parallel machines. From the viewpoint of workload, instead of completion time, two important theorems are developed for the problem. The first theorem provides an improved lower bound as the starting point for the search, and the second theorem further accelerates the search speed in the algorithm. Incorporating the two useful theorems, an algorithm is developed for obtaining the optimal solution. Although the developed algorithm has an exponential time complexity, extensive computational experiments demonstrate that it is quite efficient for various sizes of the problem. With the optimal algorithm, we also examine the effectiveness of the popular LPT heuristic.