Single-Machine Online Scheduling with Non-delayed Processing Constraint and Deterioration Effect in the Steel Rolling Process

期刊论文
发表日期：

2024年7月19日

查看全文

Lan-Meng Meng,
Ran Ma,
Yu-Zhong Zhang

摘要

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 non-delayed 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+Bt)$ $p_{j} = a_{j} (A + B t)$ , where $A>0,B>0$ $A > 0, B > 0$ and $a_{j}>0$ $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+Ba_{\max }$ $1 + B a_{max}$ . Then, we design an online algorithm called Modified-Largest Delivery Time (M-LDT) and show the algorithm M-LDT is $(1+\alpha )(1+Ba_{\max })$ $(1 + α) (1 + B a_{max})$ -competitive, where $\alpha $ $α$ is the positive root of $\alpha ^{2}-\alpha -1=0$ $α^{2} - α - 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.