کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1135671 | 956107 | 2008 | 10 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Makespan minimization for multiple uniform machines Makespan minimization for multiple uniform machines](/preview/png/1135671.png)
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.
Journal: Computers & Industrial Engineering - Volume 54, Issue 4, May 2008, Pages 983–992