Metaheuristic algorithms hybridised with variable neighbourhood search for solving the response time variability problem |
| |
Authors: | Albert Corominas Alberto García-Villoria Rafael Pastor |
| |
Affiliation: | 1. Institute of Industrial and Control Engineering (IOC), Universitat Politècnica de Catalunya (UPC), Av. Diagonal 647 (Edif. ETSEIB), 11th floor, 08028, Barcelona, Spain
|
| |
Abstract: | The response time variability problem (RTVP) is a scheduling problem with a wide range of real-world applications: mixed-model assembly lines, multi-threaded computer systems, network environments, broadcast of commercial videotapes and machine maintenance, among others. The RTVP arises whenever products, clients or jobs need to be sequenced in such a way that the variability in the time between the points at which they receive the necessary resources is minimised. Since the RTVP is NP-hard, several heuristic and metaheuristic techniques are needed to solve non-small instances. The published metaheuristic procedure that obtained the best solutions, on average, for non-small RTVP instances is an algorithm based on a variant of the variable neighbourhood search (VNS), called Reduced VNS (RVNS). We propose hybridising RVNS with three existing algorithms based on tabu search, multi-start and particle swarm optimisation. The aim is to combine the strengths of the metaheuristics. A computational experiment is carried out and it is shown that, on average, all proposed hybrid methods are able to improve the best published solutions. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|