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

The parallel-machine customer order scheduling problem with delivery time and submodular rejection penalties (PCOSP-DS) is given a set <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathcal{O}$</tex> of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n$</tex> customer orders and a set of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$m$</tex> exclusive machines. Each order has <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$m$</tex> product types and a delivery time, where each product type must be produced on a exclusive machine. Each customer order can be either processed on the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$m$</tex> exclusive machines, or rejected and paid a penalty. The PCOSP-DS is to find a customer order set <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$A$</tex> to minimize the sum of the maximum delivery completion time of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$A$</tex> and the penalty of rejected customer order set <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$R=\mathcal{O}\backslash A$</tex>, where the penalty is determined using a given submodular function. We present a randomized rounding algorithm and prove that its expected approximation factor is <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\max\{\frac{1}{\alpha}\cdot\ln(\frac{1}{1-\alpha}\overline{)}, \frac{1}{\alpha}\}$</tex>, where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\alpha\in(0,1)$</tex>. Then, we present a deterministic <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\frac{e}{e-1}$</tex> -approximation algorithm that is based on the randomized rounding algorithm.