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

Previous Articles Next Articles

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

CLC Number:

90B35

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.

TrendMD

References

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

[1]	Wen-Chang Luo. On Scheduling a Deteriorating Rate-Modifying Activity to Minimize the Number of Tardy Jobs [J]. Journal of the Operations Research Society of China, 2020, 8(1): 165-175.
[2]	Qi Feng, Wei-Ping Shang, Cheng-Wen Jiao, Wen-Jie Li. Two-Agent Scheduling on a Bounded Parallel-Batching Machine with Makespan and Maximum Lateness Objectives [J]. Journal of the Operations Research Society of China, 2020, 8(1): 189-196.
[3]	Yao Xu, Yong Chen, Peng Zhang, Randy Goebel. Approximation Algorithms for Vertex Happiness [J]. Journal of the Operations Research Society of China, 2019, 7(3): 429-448.
[4]	Yong Chen, Guang-Ting Chen, Long-Cheng Liu, Yi-Wei Jiang, Zhi-Yi Tan, An Zhang. Online Scheduling with Unit Processing Times and Processing Set Restrictions [J]. Journal of the Operations Research Society of China, 2019, 7(3): 475-484.
[5]	Long Wan, Jin-Jiang Yuan. Simultaneous Approximation Ratios for Parallel Machine Scheduling Problems [J]. Journal of the Operations Research Society of China, 2019, 7(3): 485-500.
[6]	Jin-Jiang Yuan, Li-Li Ren, Ji Tian, Ru-Yan Fu. Online Scheduling on Two Uniform Unbounded Parallel-Batch Machines to Minimize Makespan [J]. Journal of the Operations Research Society of China, 2019, 7(2): 303-319.
[7]	Tao-Ran Fu, Jin-Yan Fan. Successive Partial-Symmetric Rank-One Algorithms for Almost Unitarily Decomposable Conjugate Partial-Symmetric Tensors [J]. Journal of the Operations Research Society of China, 2019, 7(1): 147-167.
[8]	Juan Zou, Jin-Jiang Yuan. Equivalence of Some Different Maintenance Activities in Single-Machine Scheduling [J]. Journal of the Operations Research Society of China, 2018, 6(4): 545-556.
[9]	Wen-Hua Li, Xing Chai. Online Scheduling on Bounded Batch Machines to Minimize the MaximumWeighted Completion Time [J]. Journal of the Operations Research Society of China, 2018, 6(3): 455-466.
[10]	Ling-Fa Lu, Li-Qi Zhang. Competitive Project Scheduling on Two Unbounded Parallel Batch Machines [J]. Journal of the Operations Research Society of China, 2018, 6(3): 473-483.
[11]	Xian-Yu Yu· De-Qun Zhou · Yu-Lin Zhang. The Study of Group Scheduling Problems with General Dual-Position-Based Job Processing Times [J]. Journal of the Operations Research Society of China, 2017, 5(4): 509-527.
[12]	Li-Ya Yang · Xi-Wen Lu. Two-Agent Supply Chain Scheduling Problem to Minimize the Sum of the Total Weighted Completion Time and Batch Cost [J]. Journal of the Operations Research Society of China, 2017, 5(2): 257-.
[13]	Lu Han · Da-Chuan Xu · Dong-Lei Du·Chen-Chen Wu. A Primal-Dual Algorithm for the Generalized Prize-Collecting Steiner Forest Problem [J]. Journal of the Operations Research Society of China, 2017, 5(2): 219-.
[14]	. The Shortest First Coordination Mechanism for a Scheduling Game with Parallel-Batching Machines [J]. Journal of the Operations Research Society of China, 2016, 4(4): 517-.
[15]	Jin-Jiang Yuan. Complexities of Some Problems on Multi-agent Scheduling on a Single Machine [J]. Journal of the Operations Research Society of China, 2016, 4(3): 379-.

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments