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.
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
.
DOI: 10.1007/s40305-022-00430-8
[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
