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

Ben REBAH, Oumaima; Elloumi, Abdelkarim; Mellouli, Racem

doi:10.22068/ijiepr.37.3.2601

IN PRESS Back to the articles list | Back to browse issues page

‎ 10.22068/ijiepr.37.3.2601

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

Oumaima Ben REBAH¹

, Abdelkarim Elloumi²

, Racem Mellouli²

1- Department of ManagementGraduate School of Commerce of Sfax, University of Sfax.Sfax, Tunisia. , imaoumaima@gmail.com
2- Department of Quantitative MethodsFaculty of Economics and Management, University of Sfax.Sfax, Tunisia.

Abstract: (68 Views)

— 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 20 jobs; for instances with 22–32 jobs, it returns the best feasible solution found within a 225-second time limit. For all instances where an MIP reference exists (up to 32 jobs), the GA solutions deviate from the MIP reference by an average of 5.2%. For larger instances (up to 200 jobs), the GA produces near-optimal solutions in under 120 seconds, demonstrating strong scalability. Computational experiments on 16 benchmark instances confirm the effectiveness of both approaches and highlight their complementary strengths.

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

Full-Text [PDF 604 kb] (22 Downloads)

Type of Study: Research | Subject: Optimization Techniques
Received: 2025/10/30 | Accepted: 2026/07/1