An Approximation Algorithm for the Parallel-Machine Customer Order Scheduling with Delivery Time and Submodular Rejection Penalties

doi:10.1007/s40305-022-00430-8

Journal of the Operations Research Society of China ›› 2024, Vol. 12 ›› Issue (2): 495-504.doi: 10.1007/s40305-022-00430-8

Previous Articles Next Articles

An Approximation Algorithm for the Parallel-Machine Customer Order Scheduling with Delivery Time and Submodular Rejection Penalties

Hong-Ye Zheng, Suo-Gang Gao, Wen Liu, Bo Hou

School of Mathematical Sciences, Hebei Normal University, Shijiazhuang 050024, Hebei, China

Received:2021-12-08 Revised:2022-06-04 Online:2024-06-30 Published:2024-06-12
Contact: Bo Hou, Hong-Ye Zheng, Suo-Gang Gao, Wen Liu E-mail:houbo1969@163.com;muronghongye1998@163.com;sggao@mail.hebtu.edu.cn;liuwen1975@126.com
Supported by:
This work was supported by the National Natural Science Foundation of China (No. 11971146), the Natural Science Foundation of Hebei Province of China (Nos. A2019205089 and A2019205092), Hebei Province Foundation for Returnees (No. CL201714) and the Graduate Innovation Grant Program of Hebei Normal University (No. CXZZSS2022053).

Abstract

Abstract: In this paper, we consider the parallel-machine customer order scheduling with delivery time and submodular rejection penalties. In this problem, we are given m dedicated machines in parallel and n customer orders. Each order has a delivery time and consists of m product types and each product type should be manufactured on a dedicated machine. An order is either rejected, in which case a rejection penalty has to be paid, or accepted and manufactured on the m dedicated machines. The objective is to find a solution tominimize the sum of themaximum delivery completion time of the accepted orders and the penalty of the rejected orders which is determined by a submodular function. We design an LP rounding algorithm with approximation ratio of n + 1 for this problem.

Key words: Order scheduling, Delivery time, Submodular rejection penalty, Approximation algorithm

CLC Number:

Hong-Ye Zheng, Suo-Gang Gao, Wen Liu, Bo Hou. An Approximation Algorithm for the Parallel-Machine Customer Order Scheduling with Delivery Time and Submodular Rejection Penalties[J]. Journal of the Operations Research Society of China, 2024, 12(2): 495-504.

TrendMD

References

[1] Ahmadi, R., Bagchi, U.:Scheduling of Multi-job Customer Orders in Multi-machine Environments. ORSA/TIMS, Philadelphia (1990)
[2] Chen, R., Li, S.:Minimizing maximum delivery completion time for order scheduling with rejection. J. Comb. Optim. 40, 1044-1064(2020)
[3] Leung, J.Y.T., Li, H., Pinedo, M.:Order scheduling in an environment with dedicated resources in parallel. J. Sched. 8(5), 355-386(2005)
[4] Shi, Z.,Huang, Z., Shi, L.:Customer order scheduling on batch processingmachineswith incompatible job families. Int. J. Prod. Res. 56, 795-808(2018)
[5] Leung, J.Y.T., Li, H., Pinedo, M.:Scheduling orders for multiple product types with due date related objectives. Eur. J. Oper. Res. 168(2), 370-389(2006)
[6] Wang, G., Cheng, E.T.C.:Customer order scheduling to minimize total weighted completion time. Omega 35(5), 623-626(2007)
[7] Xu, X., Ma, Y., Zhou, Z., Zhao, Y.:Customer order scheduling on unrelated parallel machines to minimize total completion time. IEEE Trans. Autom. Sci. Eng. 12(1), 244-257(2015)
[8] Bartal, S., Leonardi, S., Marchetti-Spaccamela, A., Sgall, J.S.L.:Multiprocessor scheduling with rejection. SIAM J. Discrete Math. 13, 64-78(2000)
[9] Li, S., Yuan, J.:Parallel-machine scheduling with deteriorating jobs and rejection. Theor. Comput. Sci. 411(40-42), 3642-3650(2010)
[10] Zhang, L., Lu, L.:Parallel-machine scheduling with release dates and rejection. 4OR 14, 165-172(2016)
[11] Zhong, X., Ou, J.:Improved approximation algorithms for parallel machine scheduling with release dates and job rejection. 4OR 15, 387-406(2017)
[12] Fujishige, S.:Submodular Functions and Optimization, 2nd ed. Elsevier, Amsterdam (2005)
[13] Lovász, L.:Submodular functions and convexity. In:Bachm, A., Grtschel, M., Korte, B.(eds.) Mathematical Programing the State of the Art, pp. 235-237. Springer, Berlin (1983)
[14] Liu, X., Li, W.:Approximation algorithms for the multiprocessor scheduling with submodular penalties. Optim. Lett. 15, 2165-2180(2021)
[15] Du, D., Lu, R., Xu, D.:A primal-dual approximation algorithm for the facility location problem with submodular penalties. Algorithmica 63(1-2), 191-200(2012)
[16] Xu, D., Wang, F., Du, D., Wu, C.:Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique. Theor. Comput. Sci. 630, 117-125(2016)
[17] Zhang, X., Xu, D., Du, D., Wu, C.:Approximation algorithms for precedence-constrained identical machine scheduling with rejection. J. Comb. Optim. 35(1), 318-330(2018)
[18] Liu, X., Li, W.:Approximation algorithm for the single machine scheduling problem with release dates and submodular rejection penalty. Mathematics 8, 133(2020)
[19] Zheng, H., Gao, S., Liu, W., Wu, W., Du, D., Hou, B.:Approximation algorithm for the parallelmachine scheduling problem with release dates and submodular rejection penalties. J. Comb. Optim.(2022). https://doi.org/10.1007/s10878-021-00842-x

An Approximation Algorithm for the Parallel-Machine Customer Order Scheduling with Delivery Time and Submodular Rejection Penalties

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Fan Yuan, Da-Chuan Xu, Dong-Lei Du, Dong-Mei Zhang. Local search yields a PTAS for fixed-dimensional k-means problem with penalties [J]. Journal of the Operations Research Society of China, 2024, 12(2): 351-362.
[2]	Wen-Zhao Liu, Min Li. An Approximation Algorithm Based on Seeding Algorithm for Fuzzy k-Means Problem with Penalties [J]. Journal of the Operations Research Society of China, 2024, 12(2): 387-409.
[3]	Bin Liu, Hui Su, Shu-Fang Gong, Qi-Zhi Fang. Adaptive Algorithms on Maximizing Monotone Nonsubmodular Functions [J]. Journal of the Operations Research Society of China, 2024, 12(2): 428-445.
[4]	Zhong-Zheng Tang, Zhuo Diao. Approximation Algorithms on k-Correlation Clustering [J]. Journal of the Operations Research Society of China, 2023, 11(4): 911-924.
[5]	Amina Sabir, Peng-Fei Huang, Qing-Zhi Yang. The Low-Rank Approximation of Fourth-Order Partial-Symmetric and Conjugate Partial-Symmetric Tensor [J]. Journal of the Operations Research Society of China, 2023, 11(4): 735-758.
[6]	Jin-Shuang Guo, Wen Liu, Bo Hou. An Approximation Algorithm for P-prize-collecting Set Cover Problem [J]. Journal of the Operations Research Society of China, 2023, 11(1): 207-218.
[7]	Wei Yu, Rui-Yong Dai, Zhao-Hui Liu. Approximation Algorithms for Multi-vehicle Stacker Crane Problems [J]. Journal of the Operations Research Society of China, 2023, 11(1): 109-132.
[8]	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.
[9]	Zhong-Zheng Tang, Zhuo Diao. Approximation Algorithms on k-Cycle Transversal and k-Clique Transversal [J]. Journal of the Operations Research Society of China, 2021, 9(4): 883-892.
[10]	Yu-Zhong Zhang, Shu-Guang Li. Scheduling Jobs with Release and Delivery Times Subject to Nested Eligibility Constraints [J]. Journal of the Operations Research Society of China, 2021, 9(1): 63-77.
[11]	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.
[12]	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.
[13]	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.
[14]	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-.
[15]	Jian Li· Yu Liu. Approximation Algorithms for Stochastic Combinatorial Optimization Problems [J]. Journal of the Operations Research Society of China, 2016, 4(1): 1-.