Heuristic Algorithms for the 1-m-1 Hybrid Flow Shop Scheduling Problem with Lot Streaming, No-Wait, Blocking, and Sequence-Dependent Setup Times
Abstract
This study considers a 1-m-1 hybrid flow shop scheduling problem that simultaneously incorporates four practical constraints: lot streaming, no-wait, blocking, and sequence-dependent setup times. Although each of these characteristics has been studied individually in the literature, their joint consideration in a single HFS model has received little attention. The problem is motivated by a real-world order sequencing problem in insulation board manufacturing, where all four constraints arise simultaneously from the production process. To formally characterize the problem, we develop a mixed-integer programming formulation that captures all operational constraints. For practical-scale problems, we propose several dispatching heuristics that can obtain sufficiently good solutions within a short computation time. We further develop a genetic algorithm as an independent solution approach to obtain high-quality solutions close to the optimum within a reasonable computation time. Computational experiments on instances generated based on real insulation board production characteristics demonstrate that the proposed algorithms outperform a benchmark greedy rule, and sensitivity analyses reveal the effects of setup time magnitude and the number of parallel machines on scheduling performance.