Performance analysis of rotation schedule and improved strategy for open shop problem to minimise makespan

Danyu Bai and Lixin Tang

International Journal of Systems Science, 2011, vol. 42, issue 7, 1143-1153

Abstract: 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.

Date: 2011
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/10.1080/00207720903308397 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tsysxx:v:42:y:2011:i:7:p:1143-1153

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TSYS20

DOI: 10.1080/00207720903308397

Access Statistics for this article

International Journal of Systems Science is currently edited by Visakan Kadirkamanathan

More articles in International Journal of Systems Science from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().