Uma heurística híbrida para o problema de flow shop com bloqueio e minimização do makespan

Abstract

Maximizing operational effciency has become a priority for modern companies, driving the need to optimize the production flow, which plays a fundamental role in an organization's ability to meet market demands in an agile and pro table manner. In this regard, enhancing the job sequencing process is essential to increase productivity and reduce waste in a highly competitive market. Within this scope, this work addresses the blocking flow shop scheduling problem with makespan minimization. In this problem, n jobs must be scheduled in an environment of m machines ordered in series, in which all jobs must follow the same processing order. Furthermore, unlike the permutational flow shop problem, the intermediate buffers between these machines are considered zero. Thus, a machine can only release a job to the subsequent machine if this one is not occupied. A hybrid population heuristic that combines a ruin-and-recreate operator with a local search based on Variable Neighborhood Descent which makes use of acceleration methods is proposed to solve the problem. In this sense, a literature method for the insertion neighborhood was adapted for the block insertion and swap neighborhoods. Furthermore, lower bounds for the swap neighborhoods are also proposed with the purpose of avoiding the evaluation of moves that would not lead to an improvement of the current solution. Finally, a tie-breaking criterion and a population diversity control mechanism are employed to prevent the method from getting stuck in local optima. Extensive computational experiments were carried out on 150 benchmark instances, encompassing parameter calibration, evaluation of the tie-breaking criterion, performance of the neighborhood used, and other components of the method, such as the ruin-and-recreate operator and the diversity of the population. In short, the proposed method was able to obtain competitive solutions, with 94.67% being the best or equal to those found in the literature.