Exact and heuristic approaches for single machine scheduling with inventory constraints and sequence-dependent setup times

Abstract

This work addresses the single machine scheduling problem with release dates, sequence-dependent setup times, and inventory constraints, 1|rj , sij , inv|Cmax. Four mixed-integer programming formulations are proposed: position-indexed, arc- indexed, arc-inventory-indexed, and arc-time-indexed. Computational experiments were performed, and the results show that the arc-indexed formulation provides the best performance among the models. Building on this formulation, a branch-and-cut algorithm incorporating inventory capacity cuts is developed, along with a branch-cut-and-price algorithm that extends an existing branch-and-price framework for scheduling problems. Among the exact methods, the branch-cut-and-price approach solves the largest number of instances to optimality, while the branch-and-cut method attains the lowest average gaps. Two heuristic methods based on the Iterated Local Search framework are also pro- posed, using ruin-and-recreate and SISRs-inspired perturbation strategies. Both heuristics consistently generate feasible solutions, with the ruin-and-recreate variant achieving particularly competitive performance.