Abstract: This paper focuses on the online production scheduling of the steel rolling processes in a single-machine environment with objective to minimize the maximum delivery completion time of all of the jobs, subject to the job deterioration effect and nondelayed processing constraint. The deterioration is reflected in the processing time of the job. Specifically, the job's processing time is a linear function of its start time and can be denoted as $p_j=a_j(A+B t)$, where $A>0, B>0$ and $a_j>0$ represents the job's processing deterioration rate. For this problem, we firstly show that the competitive ratio of any deterministic online algorithm is not less than $1+B a_{\text {max }}$. Then, we design an online algorithm called Modified-Largest Delivery Time (M-LDT) and show the algorithm M-LDT is $(1+\alpha)\left(1+B a_{\max }\right)$-competitive, where $\alpha$ is the positive root of $\alpha^2-\alpha-1=0$. Finally, we use the combination of graphs and tables to give the simulation results of multiple instances, and then verify the correctness and effectiveness of our proposed online algorithm.

Key words: Scheduling, Online algorithm, Delivery time, Deteriorating effect, Non-delayed processing constraint