In this paper, we consider the parallel-machine customer order scheduling with weighted and submodular rejection penalties, which is formally defined as follows. We are given a set \( \mathcal {O} \) of n customer orders and a set of m dedicated machines. Each order consists of m different product types and has an associated weight, where each product type must be processed on a corresponding dedicated machine. Each order can either be rejected, in which case a rejection penalty must be paid, or accepted and processed on the m dedicated machines. If an order is accepted, the weighted completion time is computed as the product of its completion time and its weight. The completion time of an order is defined as the maximum completion time among all its product types. The objective is to select a rejected order set \(\mathcal {R}\subseteq \mathcal {O}\) and schedule the remaining orders \(\mathcal {A}=\mathcal {O}\setminus \mathcal {R}\) such that the sum of the maximum weighted completion time \( W_{\max }(\mathcal {A}) \) of the accepted orders in \( \mathcal {A} \) and the penalty \( \pi (\mathcal {R}) \) is minimized, where the penalty is determined by a nondecreasing submodular function \( \pi (\cdot ) \) . We present a deterministic polynomial-time \( \frac{e}{e-1} \) -approximation algorithm based on the randomized \((\alpha ,\beta )\) -rounding algorithm.