A Best Possible Online Algorithm for Single-Machine Scheduling with Non-delayed Processing Constraint and Bounded Delivery Times

doi:10.1007/s40305-024-00541-4

Journal of the Operations Research Society of China ›› 2026, Vol. 14 ›› Issue (2): 489-501.doi: 10.1007/s40305-024-00541-4

Previous Articles Next Articles

A Best Possible Online Algorithm for Single-Machine Scheduling with Non-delayed Processing Constraint and Bounded Delivery Times

Yan-Jun Qu, Ji Tian, Ru-Yan Fu, Kai-Jie Ge

School of Mathematics, China University of Mining and Technology, Xuzhou 221116, Jiangsu, China

Received:2023-10-23 Revised:2024-03-11 Online:2026-06-30 Published:2026-07-06
Contact: Ji Tian E-mail:jitian@cumt.edu.cn
Supported by:
This paper was supported by Key Program of the National Natural Science Foundation of China (No. 62333016).

Abstract

Abstract: We investigate the problem of the online scheduling with non-delayed processing constraint and bounded delivery times on a single machine where jobs arrive over time. The non-delayed processing (NDP) constraint means that the available jobs cannot be delayed for processing when a machine is idle. Each job's information, such as processing time and delivery time, becomes known at its release time. Once the processing of a job is completed on the machine, we deliver it to the destination by a vehicle. The objective is to minimize the time by which all jobs have been delivered. In this paper, we assume that all jobs have bounded delivery times, i.e., $\beta q_j \leqslant p_j$ for each job $J_j$, where $p_j$ and $q_j$ denote the processing time and delivery time of $J_j$, respectively, and $\beta$ is a given non-negative real number. We present a best possible online algorithm with a competitive ratio of $1+\frac{1}{\beta+2}$.

Key words: Online scheduling, NDP constraint, Bounded delivery times, Competitive ratio

CLC Number:

90B35

Yan-Jun Qu, Ji Tian, Ru-Yan Fu, Kai-Jie Ge. A Best Possible Online Algorithm for Single-Machine Scheduling with Non-delayed Processing Constraint and Bounded Delivery Times[J]. Journal of the Operations Research Society of China, 2026, 14(2): 489-501.

TrendMD

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.jorsc.shu.edu.cn/EN/10.1007/s40305-024-00541-4

https://www.jorsc.shu.edu.cn/EN/Y2026/V14/I2/489

References

[1] Akker, M.V.D., Hoogeveen, H., Vakhania, N.: Restarts can help in the online minimization of the maximum delivery time on a single machine. J. Sched. 3, 333–341(2003)
[2] Hall, L., Shmoys, D.: Approximation algorithms for constrained scheduling problems. In: Proceedings of the 30th IEEE symposium on foundations of computer science, pp. 134–139 IEEE Computer Society Press, New York (1989)
[3] Hoogeveen, J.A., Vestjens, A.P.A.: A best possible deterministic on-line algorithm for minimizing maximum delivery time on a single machine. Siam J. Discrete Math. 13, 56–63(2000)
[4] Lawler, E.L., Lenstra, J.K., Rinnooy, Kan, A.H.G., Shmoys, D.B.: Sequencing and scheduling: algorithms and complexity. In: Graves, S.C., Zipkin, P.H., Rinnooy Kan, A.H.G. (eds.), Logistics of Production and Inventory, Handbooks in Operation Research Management Science, North-Holland, Amsterdam, pp. 445-522(1993)
[5] Li, W.J., Liu, H.L.: Online NDP-constraint scheduling of jobs with delivery times or weights. Optim. Lett. 17, 591–612(2023)
[6] Li, W.J., Yuan, J.J.: Single-machine online scheduling of jobs with non-delayed processing constraint. J. Comb. Optim. 41, 830–843(2021)
[7] Liu, H.L., Lu, X.W.: Online scheduling on a parallel batch machine with delivery times and limited restarts. J. Oper. Res. Soc. China. 10, 113–131(2022)
[8] Liu, M., Chu, C.B., Xu, Y.F., Zheng, F.F.: An optimal online algorithm for single machine scheduling with bounded delivery times. Eur. J. Oper. Res. 201, 693–700(2010)
[9] Liu, P.H., Lu, X.W.: Online unbounded batch scheduling on parallel machines with delivery times. J. Comb. Optim. 29, 228–236(2015a)
[10] Liu, P.H., Lu, X.W.: Online scheduling on two parallel machines with release dates and delivery times. J. Comb. Optim. 30, 347–359(2015b)
[11] Tan, Z.Y., Zhang, A.: Online and semi-online scheduling. In: Pardalos, P.M., et al. (eds.) Handbook of combinatorial optimization. Springer, New York (2013)
[12] Tian, J., Fu, R.Y., Yuan, J.J.: A best on-line algorithm for single machine scheduling with small delivery times. Theor. Comput. Sci. 393, 287–293(2008)
[13] Tian, J., Fu, R.Y., Yuan, J.J.: Online over time scheduling on parallel-batch machines: a survey. J. Oper. Res. Soc. China. 2, 445–454(2014)
[14] Vestjens, A.P.A.: Online machine scheduling. Ph.D. Thesis, Department of Mathematics and Computing Science, Eindhoven University of Technology, Eindhoven (1997)
[15] Yuan, J.J., Li, S.S., Tian, J., Fu, R.Y.: A best possible on-line algorithm for the single machine parallel-batch scheduling with restricted delivery times. J. Comb. Optim. 17, 206–213(2009)

A Best Possible Online Algorithm for Single-Machine Scheduling with Non-delayed Processing Constraint and Bounded Delivery Times

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 8

Recommended Articles

Metrics

Comments

[1]	Li-Yun Miao, Ji Tian, Ru-Yan Fu. A Best Possible Online Algorithm For Parallel-Batch Scheduling with Kind Release Times and Job Compatibilities [J]. Journal of the Operations Research Society of China, 2025, 13(2): 603-615.
[2]	Man Xiao, Yu-Fei Du, Wei-Dong Li, Jin-Hua Yang. Semi-online Machine Covering Problem on Three Hierarchical Machines with Bounded Processing Times [J]. Journal of the Operations Research Society of China, 2024, 12(4): 1126-1138.
[3]	Shuang Cai, Ke Liu. Online Scheduling on Two Parallel Identical Machines Under a Grade of Service Provision [J]. Journal of the Operations Research Society of China, 2022, 10(4): 689-702.
[4]	Hai-Ling Liu, Xi-Wen Lu. Online Scheduling on a Parallel Batch Machine with Delivery Times and Limited Restarts [J]. Journal of the Operations Research Society of China, 2022, 10(1): 113-131.
[5]	Yong Chen, Guang-Ting Chen, Long-Cheng Liu, Yi-Wei Jiang, Zhi-Yi Tan, An Zhang. Online Scheduling with Unit Processing Times and Processing Set Restrictions [J]. Journal of the Operations Research Society of China, 2019, 7(3): 475-484.
[6]	Jin-Jiang Yuan, Li-Li Ren, Ji Tian, Ru-Yan Fu. Online Scheduling on Two Uniform Unbounded Parallel-Batch Machines to Minimize Makespan [J]. Journal of the Operations Research Society of China, 2019, 7(2): 303-319.
[7]	Wen-Hua Li, Xing Chai. Online Scheduling on Bounded Batch Machines to Minimize the MaximumWeighted Completion Time [J]. Journal of the Operations Research Society of China, 2018, 6(3): 455-466.
[8]	Ji Tian · Ruyan Fu · Jinjiang Yuan. Online Over Time Scheduling on Parallel-Batch Machines: A Survey [J]. Journal of the Operations Research Society of China, 2014, 2(4): 445-.