The online scheduling on an unbounded parallel batch machine with delivery times and limited restarts is studied in this paper. Here, online means that jobs arrive over time and the characteristics of a job become known until it arrives. Limited restarts mean that once a running batch contains at least one restarted job, it cannot be restarted again. The goal is to minimize the time by which all jobs have been delivered. We consider a restricted model that the delivery time of each job is no more than its processing time. We present a best possible online algorithm with a competitive ratio of 3/2 for the problem.
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
.
DOI: 10.1007/s40305-021-00356-7
[1] Lee, C.Y., Uzsoy, R., Martin-Vega, L.A.:Efficient algorithms for scheduling semi-conductor burn-in operations. Oper. Res. 40(4), 764-775(1992)
[2] Hall, N.G., Potts, C.N.:Supply chain scheduling:batch and delivery. Oper. Res. 51, 566-583(2003)
[3] Tang, L.X., Gong, H.:The coordination of transportation and batching scheduling. Appl. Math. Model. 33(10), 3854-3862(2009)
[4] Shmoys, D.B., Wein, J., Williamson, D.P.:Scheduling parallel machines on-line. SIAM J. Comput. 24, 1313-1331(1995)
[5] 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(2000)
[6] Fu, R.Y., Tian, J., Yuan, J.J., He, C.:On-line scheduling on a batch machine to minimize makespan with limited restarts. Oper. Res. Lett. 36(2), 255-258(2008)
[7] Yuan, J.J., Li, S.S., Tian, J., Fu, R.Y.:A best on-line scheduling for the single machine parallel-batch scheduling with restricted delivery time. J. Comb. Optim. 17(2), 206-213(2009)
[8] Tian, J., Cheng, T.C.E., Ng, C.T., Yuan, J.J.:An improved on-line algorithm for single parallel-batch machine scheduling with delivery times. Discrete Appl. Math. 160(7-8), 1191-1210(2012)
[9] Yuan, J.J., Fu, R.Y., Ng, C.T., Cheng, T.C.E.:A best online algorithm for unbounded parallel-batch scheduling with restarts to minimize makespan. J. Sched. 14(4), 361-369(2011)
[10] Liu, H.L., Yuan, J.J., Li, W.J.:Online scheduling of equal length jobs on unbounded parallel batch processing machines with limited restart. J. Comb. Optim. 31, 1609-1622(2016)
