Journal
INTERNATIONAL JOURNAL OF SYSTEMS SCIENCE
Volume 42, Issue 7, Pages 1143-1153Publisher
TAYLOR & FRANCIS LTD
DOI: 10.1080/00207720903308397
Keywords
open shop problem; makespan; asymptotical analysis; worst case analysis
Categories
Funding
- National Natural Science Foundation for Distinguished Young Scholars of China [70425003]
- National 863 High-Tech Research and Development Program of China [2006AA04Z174]
- National Natural Science Foundation of China [60674084]
Ask authors/readers for more resources
This article addresses the open shop scheduling problem with the objective to minimise the maximum completion time, or makespan. Both asymptotical analysis and worst case analysis are conducted for the heuristic, rotation schedule (RS) algorithm. In the asymptotical analysis, we prove that the RS algorithm is asymptotically equal to the optimal solution when the problem size is large enough. In the worst case analysis, we show that the tight worst case performance ratio of RS algorithm is equal to the machine number m. To accelerate the convergence of the RS algorithm for medium size problems, the improved version of the heuristic, the modified RS (MRS) algorithm is presented. At the end of this article, the asymptotical optimality of the RS algorithm and the practical effectiveness of the MRS algorithm are shown by numerical simulations.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available