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 

机构地区：[1]School of Mathematical Sciences,Hebei Normal University,Shijiazhuang 050024,Hebei,China

出　　处：《Journal of the Operations Research Society of China》2024年第2期495-504,共10页中国运筹学会会刊（英文）

基　　金：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);the Graduate Innovation Grant Program of Hebei Normal University(No.CXZZSS2022053).

摘　　要：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 to minimize the sum of the maximum 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.

关 键 词：Order scheduling Delivery time Submodular rejection penalty Approximation algorithm 

分 类 号：O17[理学—数学]