Improved Approximation Algorithm for Scheduling on a Serial Batch Machine with Split-Allowed Delivery

doi:10.1007/s40305-018-0210-x

Journal of the Operations Research Society of China ›› 2020, Vol. 8 ›› Issue (1): 133-143.doi: 10.1007/s40305-018-0210-x

所属专题： Scheduling

收稿日期:2017-09-06 修回日期:2018-01-17 出版日期:2020-03-30 发布日期:2020-02-18
通讯作者: Ling-Fa Lu, Ru-Bing Chen, Jin-Jiang Yuan, Li-Qi Zhang E-mail:lulingfa@zzu.edu.cn;zzucrb2009@163.com;yuanjj@zzu.edu.cn;zhangliqi2013@163.com
基金资助:
This research was supported by the National Natural Science Foundation of China (Nos. 11271338, 11771406, 11571321, U1504103).

Improved Approximation Algorithm for Scheduling on a Serial Batch Machine with Split-Allowed Delivery

Ru-Bing Chen¹, Ling-Fa Lu¹, Jin-Jiang Yuan¹, Li-Qi Zhang²

1 School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China;
2 College of Information and Management Science, Henan Agricultural University, Zhengzhou 450003, China

Received:2017-09-06 Revised:2018-01-17 Online:2020-03-30 Published:2020-02-18
Contact: Ling-Fa Lu, Ru-Bing Chen, Jin-Jiang Yuan, Li-Qi Zhang E-mail:lulingfa@zzu.edu.cn;zzucrb2009@163.com;yuanjj@zzu.edu.cn;zhangliqi2013@163.com

摘要/Abstract

Abstract: 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.

Key words: Scheduling, Production and delivery, Serial batch, Approximation algorithm

中图分类号:

90B35

. [J]. Journal of the Operations Research Society of China, 2020, 8(1): 133-143.

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.

[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)

相关文章 15

[1]	. [J]. Journal of the Operations Research Society of China, 2026, 14(2): 489-501.
[2]	. [J]. Journal of the Operations Research Society of China, 2026, 14(2): 547-564.
[3]	. [J]. Journal of the Operations Research Society of China, 2026, 14(2): 653-670.
[4]	. [J]. Journal of the Operations Research Society of China, 2026, 14(1): 129-148.
[5]	. [J]. Journal of the Operations Research Society of China, 2025, 13(4): 1157-1180.
[6]	. [J]. Journal of the Operations Research Society of China, 2025, 13(2): 590-602.
[7]	. [J]. Journal of the Operations Research Society of China, 2025, 13(2): 603-615.
[8]	. [J]. Journal of the Operations Research Society of China, 2024, 12(4): 1088-1102.
[9]	. [J]. Journal of the Operations Research Society of China, 2024, 12(4): 1126-1138.
[10]	. [J]. Journal of the Operations Research Society of China, 2024, 12(3): 681-693.
[11]	. [J]. Journal of the Operations Research Society of China, 2024, 12(2): 341-350.
[12]	. [J]. Journal of the Operations Research Society of China, 2023, 11(3): 693-706.
[13]	. [J]. Journal of the Operations Research Society of China, 2022, 10(1): 113-131.
[14]	. [J]. Journal of the Operations Research Society of China, 2021, 9(4): 909-914.
[15]	. [J]. Journal of the Operations Research Society of China, 2021, 9(2): 359-373.

Improved Approximation Algorithm for Scheduling on a Serial Batch Machine with Split-Allowed Delivery

PDF

可视化

摘要/Abstract

引用本文

使用本文

相关文章 15

编辑推荐

Metrics

本文评价