Makespan minimization for multiple uniform machines

Makespan minimization for multiple uniform machines

0.00 Avg rating0 Votes
Article ID: iaor2009968
Country: Netherlands
Volume: 54
Issue: 4
Start Page Number: 983
End Page Number: 992
Publication Date: May 2008
Journal: Computers & Industrial Engineering
Authors: ,
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.