Exact Algorithm for Batch Scheduling With Many-to-Many Job-Tool Matching and Job Release Time Constraints

Job-dependent tool switching is necessary in many batch processing systems (BPSs). Heterogeneous tool demand and extra time consumption for tool switch bring great challenge for high-performance production scheduling in BPSs. In this study, we present a novel batch scheduling problem derived from a satellite vibration test system. Different from basic scheduling problems in BPSs with tool switching, it has complications caused by many-to-many task-tool matching and job release time constraints. Specifically, each job has predetermined candidate tools. One of them should be selected and equipped to process a given job. Unlike sequence-dependent setup time that is only related to two adjacent jobs, tool switching time is additionally dependent on the tools selected by both jobs from their respective candidate tools. Both job sequence and tool selections need to be determined to minimize makespan. Mixed-integer linear programming (MILP) and constraint programming (CP) models are developed for formulating the problem. We prove that the problem is <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">NP</i>-hard. To obtain exact solutions, we propose a novel branch-andbound algorithm (B&B) based on the analysis and extraction of problem properties. It integrates a domain reduction mechanism, branching strategies, and dominance rules. Among them, the domain reduction mechanism reduces the number of jobs to be scheduled; the branching strategies accelerate solving speed; and the dominance rules save the memory consumption. Ablation studies and key influencing factor experiments are performed. The results show that the proposed B&B can optimally solve much larger instances than state-of-the-art methods (including some heuristics). It can optimally solve industrial-size problems in a short time, implying that it can well satisfy the performance demand of a satellite vibration test system and thus advancing the filed of optimal scheduling for BPSs.