Single-machine batch scheduling with split jobs and a maintenance activity
研究了带固定维护活动的单机批调度问题，作业可拆分到两个连续批次中，针对最小化最大完工时间和总完工时间两个目标，分别证明了NP困难性并给出了近似比为3/2的算法，实验显示平均误差仅0.36%。
Motivated by batch-dependent processing constraints in semiconductor testing and other time-critical industrial applications, we consider a single-machine batch scheduling problem with a fixed maintenance activity, where jobs have equal processing time but different sizes. Each job can be split and processed in two consecutive batches if necessary. For the objective of minimising the makespan, we prove the NP-hardness of the problem and provide an approximation algorithm with a worst-case ratio of 32, which is the best possible polynomial-time approximation algorithm under the assumption that P≠NP. For the objective of minimising the total completion time, we prove that the problem is NP-hard, and then present a pseudo-polynomial time dynamic programming algorithm and a 32-approximation algorithm. Moreover, through computational experiments, we demonstrate that the approximation algorithm performs very well in practice, achieving an average relative error of only 0.36%.