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

In this paper, we consider the parallel-machine customer order scheduling with delivery time and submodular rejection penalties. In this problem, we are given mdedicated machines in parallel and ncustomer orders. Each order has a delivery time and consists of mproduct 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 mdedicated 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+1for this problem.