×

Online scheduling on the unbounded drop-line batch machines to minimize the maximum delivery completion time. (English) Zbl 1335.90043

Summary: We consider the online scheduling on \(m\) unbounded drop-line batch machines with delivery times. Here a drop-line batch machine can process several jobs in a batch so that the processing time of a batch is equal to the longest processing time of the jobs in the batch, the jobs in a batch have the same starting time, and the completion time of a job is equal to the sum of its starting time and its processing time. Once the processing of a job is completed on the machine, we immediately deliver it to the destination. The objective is to minimize the time by which all jobs have been delivered. For this problem, we present a best possible online algorithm with a competitive ratio of \(1 + \alpha_m\), where \(\alpha_m\) is the positive root of the equation \(\alpha^2 + m\alpha - 1 = 0\).

MSC:

90B35 Deterministic scheduling theory in operations research
68W27 Online algorithms; streaming algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Fang, Y.; Liu, P. H.; Lu, X. W., Online batch scheduling on parallel machines with delivery times, Theoret. Comput. Sci., 412, 5333-5339 (2011) · Zbl 1222.68049
[2] Lee, C. Y.; Uzsoy, R.; Martin-Vega, L. A., Efficient algorithms for scheduling semi-conductor burn-in operations, Oper. Res., 40, 764-775 (1992) · Zbl 0759.90046
[3] 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) · Zbl 1280.68298
[4] Liu, P. H.; Lu, X. W., Online unbounded batch scheduling on parallel machines with delivery times, J. Comb. Optim., 29, 228-236 (2015) · Zbl 1319.90034
[5] Tian, J.; Cheng, T. C.E.; Ng, C. T.; Yuan, J. J., Online scheduling on unbounded parallel-batch machines to minimize makespan, Inform. Process. Lett., 109, 1211-1215 (2009) · Zbl 1206.68072
[6] 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) · Zbl 1306.90060
[7] Zhang, G. C.; Cai, X. Q.; Wong, C. K., Optimal online algorithms for scheduling on parallel batch processing machines, IIE Trans., 35, 175-181 (2003)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.