A Mixed-Integer Programming and Genetic Algorithm Approach for a Two-Stage Hybrid Flow Shop with Shared Machines in Cardboard Cutting Operations

This paper addresses pattern scheduling within cutting stock problems, treating it as a specialized instance of a two-stage hybrid flow shop (HFS) problem with unrelated parallel machines at each stage. Originating from a real industrial case in the corrugated cardboard-cutting industry (UNIPACK), the problem incorporates machine eligibility restrictions, shared bi-functional machines across stages, and a novel positional constraint that prevents job splitting on shared machines. To address these complexities, we propose a mixed-integer programming (MIP) model that minimizes production costs comprising weighted job flow-time costs and makespan-related labor costs. We complement this with a genetic algorithm (GA) metaheuristic for larger instances. The MIP achieves optimality for instances with up to ۲۰ jobs; for instances with ۲۲–۳۲ jobs, it returns the best feasible solution found within a ۲۲۵-second time limit. For all instances where an MIP reference exists (up to ۳۲ jobs), the GA solutions deviate from the MIP reference by an average of ۵.۲%. For larger instances (up to ۲۰۰ jobs), the GA produces near-optimal solutions in under ۱۲۰ seconds, demonstrating strong scalability. Computational experiments on ۱۶ benchmark instances confirm the effectiveness of both approaches and highlight their complementary strengths.

کلیدواژه ها:

Cutting stock ، scheduling ، hybrid flow shop ، eligible machine ، shared machine ، positional constraint ، setup time ، mixed-integer programming ، genetic algorithm.