Single machine scheduling with variable maintenance in the battery manufacturing
研究了电池制造中压延工序的单机调度问题，考虑机器滚轮磨损和基于位置的作业资格约束，提出整数规划模型和分支定界算法以最小化最大延迟，并设计了启发式算法处理大规模实例。
We address a single-machine scheduling problem with variable maintenance and a position-based job eligibility constraint, considering ready times and due dates, inspired by the pressing process in battery manufacturing. During pressing, the machine's roll gradually wears out with each job, and the machine's processing capability depends on the roll's wear condition. When the wear becomes excessive, the roll needs to be replaced. In our problem, we define the roll's wear state as the machine's state value, which decreases each time a job is processed. Each job has a specific requirement for this state value, and if it is insufficient, the job cannot be processed. Maintenance resets the machine's state value to its initial level. This constraint is referred to as position-based job eligibility. We propose an integer programming (IP) model with the objective of minimising maximum lateness. We then solve it using a branch and bound (B&B) algorithm, for which we develop dominance properties, define conditions to prune unnecessary branches, and establish tight lower bounds. Additionally, we propose and analyse a simple and practical heuristic algorithm to address larger problem instances. Through experiments, we demonstrate the performance improvements achieved by the developed components of the proposed B&B algorithm. In particular, the proposed B&B algorithm outperforms the IP model and efficiently finds the optimal solution for small to medium-sized instances within a reasonable time. Furthermore, for large-scale instances, the heuristic algorithm provides an effective and computationally efficient alternative. This paper makes a significant contribution by being one of the first to address and solve the pressing process scheduling problem within the relatively unexplored field of battery manufacturing.