Robust Scheduling on Parallel Semi-Continuous Batching Machines with Incompatible Job Families

Abstract

Motivated by walking beam heating systems, this paper studies the Parallel Semi-Continuous Batch Scheduling Problem with Incompatible Job Families (PSCBSP-IF) under processing time uncertainty. In this problem, the processing duration of each batch is jointly determined by the longest job in the batch, the batch size, and the machine capacity. The objective is to minimize the worst-case makespan by determining machine assignments and family-compatible batches before uncertainty is realized. To address this problem, we formulate a two-stage robust optimization model with a budgeted uncertainty set and develop two complementary solution approaches. The first approach is a strengthened inexact column-andconstraint generation (i-C&CG) framework, in which familylevel cuts are incorporated by exploiting problem-specific structural properties. The second approach is a Memetic framework that integrates assignment-only encoding, scenariopool-guided decoding, bottleneck-guided mutation, and tabubased intensification to obtain high-quality robust schedules within limited computation time. Computational experiments on generated steel-production instances show that the proposed Memetic framework consistently outperforms both the i-C&CG approach and its tabu-free variant across all tested uncertaintybudget levels, while maintaining stable performance under different budget settings.