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}$.
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
.
DOI: 10.1007/s40305-024-00541-4
[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)
