A computational evaluation of constructive and improvement heuristics for the blocking flow shop to minimise total flowtime |
| |
| Affiliation: | 1. Industrial Management, School of Engineering, University of Seville, Camino de los Descubrimientos s/n, 41092 Seville, Spain;2. Industrial Engineering, Faculty of Engineering, University of Duisburg-Essen, Bismarckstr. 90, 47057 Duisburg, Germany;1. Department of Industrial Engineering, Faculty of Engineering, Gazi University, Maltepe, 06570, Ankara, Turkey;2. Machine Intelligence Institute, Iona College, New Rochelle, NY 10805, USA;1. Faculty of Electrical Engineering, Warsaw University of Technology, Koszykowa 75, Warsaw, Poland;2. Military Institute of Medicine, Szaserow 128, Warsaw, Poland;3. Military University of Technology, Kaliskiego 2, Warsaw, Poland;1. Industrial Engineering and Management, Ariel University, Ariel 40700, Israel;2. Information Systems Engineering, Ben-Gurion University of the Negev, P.O.Box 653 Beer-Sheva 8410501, Israel;1. Faculty of Life Sciences and Computing, London Metropolitan University, Holloway Road, London N78DB, United Kingdom;2. STS Defence Ltd, Mumby Rd, Gosport PO12 1AF, United Kingdom |
| |
| Abstract: | This paper focuses on the blocking flow shop scheduling problem with the objective of total flowtime minimisation. This problem assumes that there are no buffers between machines and, due to its application to many manufacturing sectors, it is receiving a growing attention by researchers during the last years. Since the problem is NP-hard, a large number of heuristics have been proposed to provide good solutions with reasonable computational times. In this paper, we conduct a comprehensive evaluation of the available heuristics for the problem and for related problems, resulting in the implementation and testing of a total of 35 heuristics. Furthermore, we propose an efficient constructive heuristic which successfully combines a pool of partial sequences in parallel, using a beam-search-based approach. The computational experiments show the excellent performance of the proposed heuristic as compared to the best-so-far algorithms for the problem, both in terms of quality of the solutions and of computational requirements. In fact, despite being a relative fast constructive heuristic, new best upper bounds have been found for more than 27% of Taillard’s instances. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
