This paper considers the integrated production and delivery scheduling on a serial batch machine, in which split is allowed in the delivery of the jobs. The objective is to minimize the makespan, i.e., the maximum delivery completion time of the jobs. Lu et al. (Theor Comput Sci 572:50-57, 2015) showed that this problem is strongly NP-hard, and presented a 3/2-approximation algorithm. In this paper, we present an improved 4/3-approximation algorithm for this problem. We also present a polynomial-time algorithm for the special case when all jobs have the identical weight.
Ru-Bing Chen, Ling-Fa Lu, Jin-Jiang Yuan, Li-Qi Zhang
. Improved Approximation Algorithm for Scheduling on a Serial Batch Machine with Split-Allowed Delivery[J]. Journal of the Operations Research Society of China, 2020
, 8(1)
: 133
-143
.
DOI: 10.1007/s40305-018-0210-x
[1] Potts, C.N.:Analysis of a heuristic for one machine sequencing with release dates and delivery times. Oper. Res. 28, 1436-1441(1980)
[2] 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(2002)
[3] van den Akker, M., Hoogeveen, H., Vakhania, N.:Restarts can help in the on-line minimization of the maximum delivery time on a single machine. J. Sched. 3, 333-341(2000)
[4] Lee, C.Y., Chen, Z.L.:Machine scheduling with transportation considerations. J. Sched. 4, 3-24(2001)
[5] Chang, Y.C., Lee, C.Y.:Machine scheduling with job delivery coordination. Eur. J. Oper. Res. 158, 470-487(2004)
[6] Lu, L.F., Yuan, J.J.:Single machine scheduling with job delivery to minimize makespan. Asia-Pacific J. Oper. Res. 25, 1-10(2008)
[7] Lu, L.F., Yuan, J.J.:Unbounded parallel batch scheduling problem with job delivery to minimize makespan. Oper. Res. Lett. 36, 477-480(2008)
[8] Pei, J., Pardalos, P.M., Liu, X.B., Fan, W.J., Yang, S.L.:Serial batching scheduling of deteriorating jobs in a two-stage supply chain to minimize the makespan. Eur. J. Oper. Res. 244, 13-25(2015)
[9] Chen,Z.-L.:Integrated production and outbound distribution scheduling:review and extensions.Oper. Res. 58, 130-148(2010)
[10] Dror, M., Trudeau, P.:Savings by split delivery routing. Transp. Sci. 23, 23-37(1989)
[11] Mullaseril, P., Dror, M., Leung, J.:Split-delivery routing heuristics in livestock feed distribution. J. Oper. Res. Soc. 48, 107-116(1997)
[12] Archetti, C., Speranza, M.G.:The split delivery vehicle routing problem:a survey. The vehicle routing problem:latest advances and new challenges. Oper. Res. Comput. Sci. Interfaces Ser. 43(Part I), 103-122(2008)
[13] Lu, L.F., Zhang, L.Q., Wan, L.:Integrated production and delivery scheduling on a serial batch machine to minimize the makespan. Theor. Comput. Sci. 572, 50-57(2015)
[14] Webster, S.T., Baker, K.R.:Scheduling groups of jobs on a single machine. Oper. Res. 43, 692-703(1995)
