Single machine scheduling with maintenance and position-based job eligibility constraints for battery manufacturing

We address a single machine scheduling problem with the objective of minimizing the makespan considering position-based job eligibility where the position that each job can be assigned depends on the machine state. The machine deteriorates each time it processes a job and requires maintenance when there is no job that can be processed. This problem has been newly defined from the pressing operation of the battery manufacturing. We introduce a position limit for a job, which is defined as the maximum allowable position after the machine's last maintenance. Additionally, we analyze special cases where a specific number of maintenance operations are needed, such as scenarios without any maintenance requirements or those with a single maintenance requirement, and propose optimal solutions. We then provide an optimal polynomial algorithm for the problem.