Classical and new heuristics for the open-shop problem: A computational evaluation

✍ Scribed by Christelle Guéret; Christian Prins

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 111 KB
• Volume: 107
• Category: Article
• ISSN: 0377-2217
• DOI: 10.1016/s0377-2217(97)00332-9

✦ Synopsis

We study the problem of constructing minimum makespan schedules for the Open-Shop problem. This paper presents two new heuristics: the ®rst one is a list scheduling algorithm with two priorities. The second is based on the construction of matchings in a bipartite graph. We develop several versions of these two heuristics. A computational evaluation shows that around 90% of randomly generated instances are solvable optimally, whereas classical (list scheduling) heuristics achieve less than 20% on average. Therefore, our algorithms make most Open-Shop instances easy to solve in practice, and this raises the problem of generating hard instances. We extend the evaluation to two kinds of such instances: the results are not so good, but remain better than classical heuristics.