The Constrained Parallel-Machine Scheduling Problem with Divisible Processing Times and Penalties

Abstract

We consider the constrained parallel-machine scheduling problem with divisible processing times and penalties (the CPS-DTP problem, for short). Specifically, given a set $M=\{a_{1},a_{2},\ldots ,a_{m}\}$ of m identical machines, and a set $J=\{b_{1},b_{2},\ldots ,b_{n}\}$ of n jobs, each job $b_{j}\in J$ has a processing time $p_{j} \in Z^{+}$ and a penalty $e_{j} \in Z^{+}$, and the job processing times are divisible, i.e., either $p_{i}|p_{j}$ or $p_{j}|p_{i}$ for any two different jobs $b_{i}$ and $b_{j}$ in J. Each job $b_{j}$ is either executed in processing time $p_{j}$ with which we schedule this job on one of m machines, or rejected with its penalty $e_{j}$ that we must pay for, it is asked to determine a subset $A\subseteq J$ such that each job $b_{j}\in A$ has to be scheduled only on one of m machines and each job $b_{j}\in J\backslash A$ has to be rejected. We consider three versions of the CPS-DTP problem, respectively. (1) The constrained parallel-machine scheduling problem with divisible processing times and total penalties (the CPS-DTTP problem, for short) is asked to determine a subset $A\subseteq J$ to satisfy the constraint mentioned-above, the objective is to minimize the makespan of the schedule T for accepted jobs in A plus the value of total penalties of the rejected jobs in $J\backslash A$; (2) The constrained parallel-machine scheduling problem with divisible processing times and maximum penalty (the CPS-DTMP problem, for short) is asked to determine a subset $A\subseteq J$ to satisfy the constraint mentioned-above, the objective is to minimize the makespan of the schedule T for accepted jobs in A plus the maximum penalty paid for rejected jobs in $J\backslash A$; (3) The constrained parallel-machine scheduling problem with divisible processing times and bounded penalty (the CPS-DTBP problem, for short) is asked to determine a subset $A\subseteq J$ to satisfy the constraint mentioned-above and the value of total penalties of the rejected jobs in $J\backslash A$ is no more than a given bound, the objective is to minimize the makespan of the schedule T for accepted jobs in A.

In this paper, we design an exact algorithm in pseudo-polynomial time to solve the CPS-DTTP problem, an exact algorithm in strongly polynomial time to solve the CPS-DTMP problem and an exact algorithm in polynomial time to solve the CPS-DTBP problem, respectively.

This paper is fully supported by the National Natural Science Foundation of China [Nos.11861075,12101593] and Project for Innovation Team (Cultivation) of Yunnan Province [No.202005AE160006]. Junran Lichen is also supported by Fundamental Research Funds for the Central Universities (buctrc202219), and Jianping Li is also supported by Project of Yunling Scholars Training of Yunnan Province.