1. Introduction
All jobs must be processed in classical scheduling problems. However, sometimes rejecting some jobs with low cost performance is possible and will bring more profit. This problem is called multiprocessor scheduling with rejection (MSR), which is first proposed by Bartal et al. [
1]. In this problem, a job is either accepted and processed on the machine, or rejected and paid a rejection penalty. The objective is to minimize the makespan of accepted jobs plus the overall penalty of rejected jobs. Bartal et al. [
1] proposed a 2-approximation algorithm running in
time and a polynomial-time approximation scheme (PTAS) for MSR. Ou et al. [
2] proposed a
-approximation algorithm with running time
for MSR, where
is a small given positive constant.
MSR and its variants have become increasingly popular in both academic and industrial community in the last two decades. Zhang and Lu [
3] considered parallel-machine scheduling with release dates and rejection, where jobs cannot be processed before their corresponding release dates. The objective of this problem to minimize the sum of makespan of accepted jobs and total penalty of rejected jobs. They developed a 2-approximation algorithm. This result is further improved by Zhong and Ou [
4] who designed a PTAS. Li et al. [
5] designed a PTAS for a variant of MSR, where the objective is to minimize the makespan when the rejection cost is bounded by a given constant.
Some studies considered the case when the number of machines is bounded. When there are exactly two machines. Zhong et al. [
6] developed a
-approximation algorithm for scheduling with release dates and rejection. When the number of machines is one, there are much more related results. Shabtay et al. [
7] handled the single machine with job rejection and positional penalties problem with a bicriteria approach. Zhang et al. [
8] proved the NP-hardness of single machine scheduling with release dates and rejection, which is a special case of the problem considered in [
3]. They presented a 2-approximation algorithm with running time of
, which was independently improved by He et al. [
9] and Ou et al. [
10] with running time of
. Zhang et al. [
11] developed a FPTAS for a variant of single machine scheduling with release dates and rejection, where the objective is to minimize the makespan when rejection penalty is bounded. Zou et al. [
12] considered single-machine scheduling with rejection and an operator non-availability interval where jobs are prohibited to start or complete in the operator non-availability interval, and presented a FPTAS. Shioura et al. [
13] studied a problem on a single machine with release dates and deadlines, where the processing can be accelerated by making additional cost. They utilized submodular optimization to achieve the best possible running time. Li and Cui [
14] designed a 1.58-approximation algorithm for vector scheduling on a single machine, where vector scheduling imply that multiple resources are needed for each job and the objective is to minimize the maximal cost over all resources plus the rejection cost. More related results can be found in the surveys [
15,
16].
Since submodular function has the property of decreasing marginal return and occurs in many mathematical models, classical combinatorial optimization problems with submodular rejection penalty receive more and more attentions [
17,
18,
19]. For the MSR problem, rejecting jobs frequently might lead to low prestige for the manufacturer. There is no linear relationship between the number of rejected jobs and the loss of the manufacturer’s prestige, but as the number of rejected jobs increases, it will have less and less impact on the manufacturer’s prestige. Recently, Zhang et al. [
20] proposed a 3-approximation algorithm for precedence-constrained scheduling with submodular rejection on parallel machines.
Motivated by the problems in [
8,
20], we propose a new scheduling problem, called single machine scheduling problem with release dates and submodular rejection penalty, where each job is either rejected or accepted and processed on the machine. The objective is to minimize the sum of the makespan of the accepted jobs and the rejection penalty of the rejected jobs which is determined by a submodular function. In this paper, we design a combinatorial 2-approximation algorithm by using the primal-dual scheme, generalizing the algorithm presented in [
8].
The remainder of this paper is structured as follows. In
Section 2, we provide a formal problem statement. In
Section 3, for single machine scheduling problem with release dates and submodular rejection penalty functions, we present a 2-approximation algorithm, based on a method similarly to the primal-dual algorithm. In addition, when all the jobs have the same release date, we present a polynomial-time exact algorithm. We provide conclusion in
Section 4.
2. Preliminaries
In this section, we present a formal description of single machine scheduling problem with release dates and submodular rejection penalty. Given a single machine and
n jobs,
, each job
has a processing time
and a release date
, where
and
are nonnegative real numbers. The rejection cost of a subset of jobs is determined by the nonmonotone submodular function
, which means that
without loss of generality, assume that
. Moreover, we assume that
can be computed within polynomial time for any subset
, where the ‘polynomial’ we use regard to the size
n.
The single machine scheduling problem with release dates and submodular rejection penalties is to choose a set
of rejected jobs and schedule the remaining jobs in
on the machine. The objective is to minimize the sum of the makespan of the accepted jobs and the penalty cost
of the rejected jobs. By using the general notation for scheduling problems, the problem is denoted by
. Clearly, if
, the problem
is exactly the problem
considered in [
8].
If rejection is not allowed, Lawler [
21] shows that the corresponding problem
can be solved using the earliest release date rule (ERD-rule for short). Thus, we have the following lemma.
Lemma 1 ([
21]).
For the problem , there exists an optimal schedule such that the accepted jobs in are processed using the ERD-rule. For any set
, let
be the total processing time of the jobs in
S. Based on Lemma 1, we first re-label the jobs such that
. For convenience, let
Assume that
. For each
, let
be the set of jobs with release date bigger than
r. Correspondingly, let
be the set of jobs such that
Obviously, if is monotone nondecreasing, . Otherwise, we have
Lemma 2. For every , can be computed in polynomial time.
Proof. Consider a given
. Clearly,
is a constant. For any subset
, construct an auxiliary function
such that
For any two subsets
, we have
where the inequality follows from that
is a submodular function. Therefore,
is a submodular function, which implies that
can be computed within polynomial time, using the method in [
22]. Since
is a constant,
can be computed within polynomial time. It implies that
can be computed within polynomial time. □
3. An Approximation Algorithm
In this section, we design a combination 2-approximation algorithm for . In particular, when all the jobs have the same release dates, we prove that can be solved exactly in polynomial time.
For each , use Process A, which is described later, to find a schedule , compute the objective value of schedule , and choose the best schedule as the output schedule.
In Process A
, similarly to the primal-dual algorithm in [
23], we introduce an auxiliary “dual” variable
for every job
and
r, where
r is an input value of Process A
. There is an auxiliary notion of time
t associated with Process A
.
Process A.
Input: An instance of and a fixed number r().
Output: a schedule and its objective value .
Step 1. Initially, set the variable for each job in J and the time .
Step 2. Compute the job set using the method described in the proof of Lemma 2. Reject every job in by setting , and freeze every job in by setting .
Step 3. While , we increase the variables for all unfrozen jobs in uniformly at unit rate with time t. As t increases, one of the following two cases may occur:
Case 1. There is a set
and
satisfying that
In this case, set for each job in and freeze those unfrozen jobs in , by setting . Reject all jobs in set , by setting .
Case 2. There is a job such that . In this case, set and freeze job by setting .
Step 4. Reject the jobs in and schedule all jobs in in time interval on the machine. The resulting schedule is denoted by , whose objective value is denoted by .
In Process A for any in the algorithm, at Step 2, we can find the exact set for a given value r, and will not change until Process A terminates. However, at Step 3 of Process A for any in the algorithm, the frozen job set and job set are changed as the change as time t. And the auxiliary “dual” variable for any and a given value r will increase with time t until job is frozen. Thus, at any time t in Process A for any , we introduce the following notations:
Lemma 3. For any , Process A can be implemented in polynomial time.
Proof. Consider Step 2 of Process A, by Lemma 2, can be found in polynomial time. Clearly, is a constant.
Consider Step 3 of Process A. For any time , let be the frozen job set at this time and be the next closest time, which is incurred by either Case 1 or Case 2.
For Case 1, the next closest time
is at most
where
,
and
for any subset
. For any two subsets
satisfying
and
, we have
and
Therefore,
and
are modular functions. Similarly to the proof of Lemma 2, we can prove that
is a submodular function. Therefore,
is a submodular function, which implies that the value of
can be computed in polynomial time by using the combinatorial algorithm for the ratio of a submodular and a modular function minimization problem [
24].
For Case 2, the next closet time
is at most
It is obvious that the value of
can be found in polynomial time.
Thus, the next time can be found in polynomial time. When the time increase from to , the algorithm freezes at least one unfrozen job, which implies that Step 3 of Process A can be completed in polynomial time. It is easy to verify other Steps can be implemented in polynomial time. Thus, the lemma holds. □
Lemma 4. For any , the rejected job set produced by Process A satisfies Proof. For any
, let
be the variable of job
at time
t which will increase with time
t until job
is frozen. Thus, if
is frozen at time
, we have
By Step 2 of Process A
, jobs in set
are found and are frozen, we have
is a constant and
By Case 1 of Process A
, for any time
t and any subset
, we have
where
is the frozen jobs set at time
t. At time points
and
(
) in Case 1, let
and
be the selected job sets, respectively. Thus, both
and
satisfy inequality (
1), i.e., we have
where all jobs in
(or
) are frozen at time
(or
) or even earlier.
Therefore, we have
where the first inequality follows from
, the second inequality follows from the submodularity of
, and the third inequality follows from inequality (
4).
Moveover,
following from inequality (
4). Any job
is frozen at
or even earlier, we have
By Process A
,
, where
is the set of subset satisfying inequality (
1), so the equality (
2) holds. □
Consider the optimal schedule . Let and be the sets of the accepted jobs and the rejected jobs in , respectively. Let be the maximum release date of the jobs in , where if .
Lemma 5. There is an optimal schedule satisfying .
Proof. For any optimal schedule , If , the lemma holds. Otherwise, let be a schedule that the jobs in are rejected and the jobs in are accepted and processed in ERD-rule. Clearly, we have , which implies that is an optimmal schedule to process the jobs in by Lemma 1. Thus, the makespan of is no more than that of .
By the definition of
, we have
. Since
, we have
By the definition of
, we have
for any
. That implies
Since function
is a submodular function, we have
Together with
, we have
Therefore, we have that the objective value of is no more than that of . Thus, is an optimal scheduling that is the rejected set of . The lemma holds. □
Let be the output schedule. Let Z and be the objective values of the schedule and the optimal schedule , respectively.
Theorem 1. and the bound is tight.
Proof. Let
be an optimal schedule such that
. If the optimal schedule
rejects all the jobs, then
is the output schedule of Process A
where
, which implies that the theorem holds. Otherwise, let
be the maximum release date of the jobs in
, we have
By Case 2 of Process A
, we have
where
is the frozen variable of job
and
is the accepted jobs produced by Process A
. Since
and
are the sets of the accepted jobs and the rejected jobs in optimal schedule
, we have
where the second inequality follows from inequality (
4) and the third inequality follows from inequality (
6).
Therefore, we have
where the second equality follows equality (
6) and Lemma 4, and the last inequality follows from inequalities (
5) and (
7).
To show that the bound is tight, consider the following instance with three jobs: , and . The submodular function is defined as following: , , , , , and .
Through the Process A, when , the resulting schedule is to reject , , . Thus, we have ; when (or ), the resulting schedule (or ) is to accept and reject , . Thus, we have ; when , the resulting schedule is to accept , and reject . Thus, we have . The optimal schedule is to accept ,, . And we have . Thus, we have . □
Then, we consider a special case for the problem where all the jobs have the same release date.
Theorem 2. The problem can be solved optitmally in polynomial time when all the jobs have the same release date.
Proof. If the optimal schedule
rejected all the jobs, then
is the output schedule of Process A
, where
, the theorem holds. Otherwise, assume
for any job
. The start processing time of machine is
and there is no job
in
J satisfying
. That implies that
Thus, we have
where the inequality follows from inequalities (
4) and (
6).
Through Step 3 of Process A
, we have
where the second equality follows equality (
6) and Lemma 4, and the last equality follows from
.
Therefore, , implying that the theorem holds. □