A BRILS metaheuristic for non-smooth flow-shop problems with failure-risk costs. (February 2016)

• Record Type: Journal Article
• Authors: Ferrer, A.; Guimarans, D.; Ramalhinho, H.; Juan, A.A.
• Is Part Of: Expert systems with applications. Volume 44(2016)
• Page Start: 177
• Page End: 186
• Publication Date: 2016-02
• Subjects: 65K05 -- 90C26 -- 90C27 -- 90C59; Heuristic algorithms -- Biased randomization -- Iterated Local Search -- Scheduling -- Flow-shop -- Non-smooth objective functions; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2015.09.011
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: Our approach of PFSP includes risk of machine failures due to lack of breaks. We model the problem as a non-smooth optimization problem. We propose the use of a biased-randomized algorithm to solve it. We combine Iterated Local Search with biased randomization of classical heuristics. Our approach outperforms other approaches just based on the makespan. Abstract: This paper analyzes a realistic variant of the Permutation Flow-Shop Problem (PFSP) by considering a non-smooth objective function that takes into account not only the traditional makespan cost but also failure-risk costs due to uninterrupted operation of machines. After completing a literature review on the issue, the paper formulates an original mathematical model to describe this new PFSP variant. Then, a Biased-Randomized Iterated Local Search (BRILS) algorithm is proposed as an efficient solving approach. An oriented (biased) random behavior is introduced in the well-known NEH heuristic to generate an initial solution. From this initial solution, the algorithm is able to generate a large number of alternative good solutions without requiring a complex setting of parameters. The relative simplicity of our approach is particularly useful in the presence of non-smooth objective functions, for which exact optimization methods may fail to reach their full potential. The gains of considering failure-risk costs during the exploration of the solution space are analyzed throughout a series of computational experiments. To promote reproducibility, these experiments are based on a set of traditional benchmark instances. Moreover, the performance of the proposed algorithm is compared against other state-of-the-art metaheuristic approaches, which have been conveniently adapted to consider failure-risk costs during the solving process. The proposed BRILS approach can be easily extended to other combinatorial optimization problems with similar non-smooth objective functions.