摘要
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.
基金
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).
