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.
Lan-Meng Meng, Ran Ma, Yu-Zhong Zhang
. Single-Machine Online Scheduling with Non-delayed Processing Constraint and Deterioration Effect in the Steel Rolling Process[J]. Journal of the Operations Research Society of China, 2026
, 14(2)
: 653
-670
.
DOI: 10.1007/s40305-024-00552-1
[1] Cheng, T.C.E., Ding, Q., Lin, B.M.: A concise survey of scheduling with time-dependent processing times. Eur. J. Oper. Res. 152(1), 1–13(2004)
[2] Chai, X., Li, W., Yuan, H., Wang, L.: Online scheduling on a single machine with linear deteriorating processing times and delivery times. J. Comb. Optim. 44, 1900–1912(2020)
[3] Gawiejnowicz, S.: A review of four decades of time-dependent scheduling: main results, new topics, and open problems. J. Sched. 23(1), 3–47(2020)
[4] Gupta, J.N.D., Gupta, S.K.: Single facility scheduling with nonlinear processing times. Comput. Ind. Eng. 14(4), 387–393(1988)
[5] Kong, M., Pei, J., Xu, J., Liu, X., Yu, X., Pardalos, P.M.: A robust optimization approach for integrated steel production and batch delivery scheduling with uncertain rolling times and deterioration effect. Int. J. Prod. Res. 58(17), 5132–5154(2020)
[6] Li, W., Liu, H.: Online NDP-constraint scheduling of jobs with delivery times or weights. Optim. Lett. 17, 591–612(2023)
[7] Li, K., Tian, H.: Integrated scheduling of reheating furnace and hot rolling based on improved multiobjective differential evolution. Complexity 2018, 1–19(2018)
[8] Lin, R., Wang, J.-Q., Oulamara, A.: Online scheduling on parallel-batch machines with periodic availability constraints and job delivery. Omega 116, 102804(2023)
[9] Li, W., Yuan, J.: Single-machine online scheduling of jobs with non-delayed processing constraint. J. Comb. Optim. 41, 830–843(2021)
[10] Liu, M., Zheng, F., Wang, S., Huo, J.: Optimal algorithms for online single machine scheduling with deteriorating jobs. Theoret. Comput. Sci. 445, 75–81(2012)
[11] Mosheiov, G.: Scheduling jobs under simple linear deterioration. Comput. Oper. Res. 21(6), 653–659(1994)
[12] Mönch, L., Shen, L.: Parallel machine scheduling with the total weighted delivery time performance measure in distributed manufacturing. Comput. Oper. Res. 127, 105126(2021)
[13] Ma, R., Tao, J., Yuan, J.: Online scheduling with linear deteriorating jobs to minimize the total weighted completion time. Appl. Math. Comput. 273, 570–583(2016)
[14] Peng, G., Wu, Y., Zhang, C., Shen, W.: Integrated optimization of storage location assignment and crane scheduling in an unmanned slab yard. Comput. Ind. Eng. 161, 107623(2021)
[15] Tang, L., Ren, H., Yang, Y.: Reheat furnace scheduling with energy consideration. Int. J. Prod. Res. 53(6), 1642–1660(2015)
[16] Wang, J., Cheng, T.C.E.: Scheduling problems with the effects of deterioration and learning. AsiaPacific J. Oper. Res. 24(2), 245–261(2007)
[17] Yang, X., Ma, R., Zhang, Y.: A best possible algorithm for an online scheduling problem with deteriorating effect in steel box girder section production. J. Ind. Manag. Optim. 19(8), 5969–5983(2023)
[18] Zhang, C., Li, Y., Cao, J., Yang, Z., Coelho, L.C.: Exact and matheuristic methods for the parallel machine scheduling and location problem with delivery time and due date. Comput. Oper. Res. 147, 105936(2022)
