We investigate the problem of the online scheduling with kind release times and job compatibilities on a single unbounded parallel-batch machine to minimize makespan. The kind release times (KRT) means that under the online setting no jobs can be released when the machine is busy. What associated with each job \begin{document}$ J_{j} $\end{document} are its normal processing time \begin{document}$ p_j $\end{document} and release time \begin{document}$ r_j $\end{document}. Two jobs \begin{document}$ J_i $\end{document} and \begin{document}$ J_j $\end{document} are called compatible if \begin{document}$ \max \{p_i, p_j\} \leqslant (1+a) \min \{p_i, p_j\} $\end{document}, where a is a given positive constant. Compatible jobs could be processed in the same batch. We derive a best possible online algorithm with a competitive ratio of \begin{document}$ 1+\sqrt{\lambda ^{2}-\lambda +1}-\lambda $\end{document}, where \begin{document}$ \lambda =\frac{a}{1+a} $\end{document}.
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
.
DOI: 10.1007/s40305-023-00480-6
[1] Lee, C.Y., Uzsoy, R., Martin-Vega, L.A.: Efficient algorithms for scheduling semiconductor burn-in operations. Oper. Res. 40, 764-775 (1992)
[2] Brucker, P., Gladky, A., Hoogveen, H., Kovalyov, M.Y., Potts, C.N., Tautenhahn, T., van de Velde, S.L.: Scheduling a batching machine. J. Sched. 1, 31-54 (1998)
[3] Zhang, G.C., Cai, X.Q., Wong, C.K.: On-line algorithms for minimizing makespan on batch processing machines. Nav. Res. Log. 48, 241-258 (2001)
[4] Dobson, G., Nambimadom, R.S.: The batch loading and scheduling problem. Oper. Res. 49, 52-65 (2001)
[5] Deng, X.T., Poon, C.K., Zhang, Y.Z.: Approximation algorithms in batch processing. J. Comb. Optim. 7, 247-257 (2003)
[6] Poon, C.K., Yu, W.C.: A flexible on-line scheduling algorithm for batch machine with infinite capacity. Ann. Oper. Res. 133, 175-181 (2005)
[7] Liu, P.H., Lu, X.W., Fang, Y.: A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines. J. Sched. 15, 77-81 (2012)
[8] 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)
[9] Li, W.H., Chai, X.: Online scheduling on bounded batch machines to minimize the maximum weighted completion time. J. Oper. Res. Soc. China 6, 455-465 (2018)
[10] Yuan, J.J., Ren, L.L., Tian, J., Fu, R.Y.: Online scheduling on two uniform unbounded parallel-batch machines to minimize makespan. J. Oper. Res. Soc. China 7, 303-319 (2019)
[11] 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)
[12] Bellanger, A., Janiak, A., Kovalyov, M.Y., Oulamara, A.: Scheduling an unbounded batching machine with job processing time compatibilities. Discrete Appl. Math. 160, 15-23 (2012)
[13] Boudhar, M., Finke, G.: Scheduling on a batch machine with job compatibilities. Belg. J. Oper. Res. Stat. Comput. Sci. 40, 69-80 (2000)
[14] Boudhar, M.: Scheduling a batch processing machine with bipartite compatibility graph. Math. Method. Oper. Res. 57, 327-513 (2003)
[15] Finke, G., Jost, V., Queyranne, M., Sebo, A.: Batch processing with interval compatibilities between tasks. Discrete Appl. Math. 156, 556-568 (2008)
[16] Li, S.S., Cheng, T.C.E., Ng, C.T., Yuan, J.J.: Single-machine batch scheduling with job processing time compatibilities. Theor. Comput. Sci. 583, 57-66 (2015)
[17] Fu, R.Y., Tian, J., Yuan, J.J., Li, S.S.: An optimal online algorithm for the parallel-batch scheduling with job processing time compatibilities. J. Comb. Optim. 34, 1187-1197 (2017)
[18] Li, W.J., Yuan, J.J.: \begin{document}$ \text{ LPT } $\end{document} online strategy for parallel-machine scheduling with kind release times. Optim. Lett. 10, 159-168 (2016)
[19] Li, W.J., Li, S.S., Feng, Q.: Online batch scheduling with kind release times and incompatible families to minimize makespan. Optim. Lett. 12, 301-310 (2018)
