A novel artificial intelligence search algorithm and mathematical model for the hybrid flow shop scheduling problem

Abstract

Hybrid flow shop (HFS) environments are prevalent in various industries, including glass, steel, paper, and textiles, posing complex scheduling challenges. This paper introduces a novel approach employing Variable Neighborhood Search (VNS) to address the HFS scheduling problem, with a primary focus on minimizing makespan. The fundamental innovation lies in the fusion of VNS with domain-specific strategies, harnessing the adaptability of VNS. Departing significantly from conventional HFS approaches, our methodology incorporates a special encoding that allows jobs to wait strategically, even when free machines are available. This approach trades immediate machine utilization for the potential of improved makespan. Additionally, using this encoding, a proper decomposition of the problem is feasible. This innovative strategy aims to balance machine load while optimizing the overall scheduling performance. Experimental testing demonstrates the effectiveness of the proposed approach in comparison to existing methods.