An Aligned Constraint Programming Model For Serial Batch Scheduling With Minimum Batch Size

Abstract--In serial batch (s-batch) scheduling, jobs from similar families are grouped into batches and processed sequentially to avoid repetitive setups that are required when processing consecutive jobs of different families. Despite its large success in scheduling, only three Constraint Programming (CP) models have been proposed for this problem considering minimum batch sizes, which is a common requirement in many practical settings, including the ion implantation area in semiconductor manufacturing. These existing CP models rely on a predefined virtual set of possible batches that suffers from the curse of dimensionality and adds complexity to the problem. This paper proposes a novel CP model that does not rely on this virtual set. Instead, it uses key alignment parameters that allow it to reason directly on the sequences of same-family jobs scheduled on the machines, resulting in a more compact formulation. This new model is further improved by exploiting the problem's structure with tailored search phases and strengthened inference levels of the constraint propagators. The extensive computational experiments on nearly five thousand instances compare the proposed models against existing methods in the literature, including mixed-integer programming formulations, tabu search meta-heuristics, and CP approaches. The results demonstrate the superiority of the proposed models on small-to-medium instances with up to 100 jobs, and their ability to find solutions up to 25% better than the ones produces by existing methods on large-scale instances with up to 500 jobs, 10 families, and 10 machines. In the current and highly competitive landscape of the manufacturing industry, companies are under growing pressure to minimize production costs and reduce cycle times. A crucial approach to achieving these goals and boosting production efficiency is processing multiple similar jobs in groups called batches [1]. Two types of batching can be distinguished in the scheduling literature, depending on how the jobs are processed inside their batch: (i) parallel batching (p-batch), where jobs inside a batch are processed in parallel at the same time [2]; and (ii) serial batching (s-batch), where jobs inside a batch are processed sequentially, one after the other [3]. The benefits of p-batching in the manufacturing industry are straightforward due to the parallelized processing of the jobs inside a batch. In contrast, the benefits of s-batching usually come from grouping jobs that require similar machine configurations to avoid repetitive setups [4].