Constraint Programming Models For Serial Batch Scheduling With Minimum Batch Size

In serial batch (s-batch) scheduling, jobs are grouped in batches and processed sequentially within their batch. This paper considers multiple parallel machines, nonidentical job weights and release times, and sequence-dependent setup times between batches of different families. Although s-batch has been widely studied in the literature, very few papers have taken into account a minimum batch size, typical in practical settings such as semiconductor manufacturing and the metal industry. The problem with this minimum batch size requirement has been mostly tackled with dynamic programming and meta-heuristics, and no article has ever used constraint programming (CP) to do so. This paper fills this gap by proposing, three CP models for s-batching with minimum batch size: (i) an Interval Assignment model that computes and bounds the size of the batches using the presence literals of interval variables of the jobs. The computational experiments on standard cases compare the three CP models with two existing mixed-integer programming (MIP) models from the literature. The results demonstrate the versatility of the proposed CP models to handle multiple variations of s-batching; and their ability to produce, in large instances, better solutions than the MIP models faster. Introduction In the current and highly competitive landscape of the manufacturing industry, companies are under growing pressure to minimize production costs and reduce cycle times. One effective strategy to improve efficiency is to process similar tasks, called jobs, together in groups known as batches [1]. There are two main ways to process these batches. In parallel batching (p-batch), all jobs in a batch are processed simultaneously [2]. In contrast, in serial batching (s-batch), jobs in a batch are processed sequentially one after another [3]. The benefits of p-batching are obvious since it saves time by processing multiple jobs at once. Similarly, s-batching is especially useful when grouping similar jobs can prevent repetitive machine setups, which are time-consuming and costly [4]. Serial batching appears in many industries, including metal processing [5], additive manufacturing (3D printing) [5, 6], paint [7] and pharmaceutical production [8], chemical manufacturing [9], and semiconductor manufacturing [10, 11].