J Comb Optim DOI 10.1007/s10878-016-0044-6
Approximation algorithms for precedence-constrained identical machine scheduling with rejection Xianzhao Zhang1 · Dachuan Xu2 · Donglei Du3 · Chenchen Wu4
© Springer Science+Business Media New York 2016
Abstract We study a precedence-constrained identical parallel machine scheduling problem with rejection. There is a communication delay between any two jobs connected in the precedence network where jobs may be rejected with penalty. The goal is to minimize the sum of the makespan and the rejection cost. We propose two 3approximation algorithms for this problem under linear and submodular rejection costs respectively. These two algorithms are both based on linear programming rounding technique. Keywords Scheduling · Rejection · Approximation algorithm · Linear programming · Rounding
1 Introduction Scheduling problems with communication delays between different processors have received extensive attention because of their vast applications. This class of scheduling problems arises with the development of parallel architecture, and the communication
This paper has been presented in the 2015 World Congress on Global Optimization (WCGO IV).
B
Dachuan Xu
[email protected]
1
College of Science, Linyi University, Linyi 276005, People’s Republic of China
2
Department of Information and Operations Research, College of Applied Sciences, Beijing University of Technology, Beijing 100124, People’s Republic of China
3
Faculty of Business Administration, University of New Brunswick, Fredericton, NB E3B 5A3, Canada
4
College of Science, Tianjin University of Technology, Tianjin 300384, People’s Republic of China
123
J Comb Optim
delay here may be interpreted as the time it takes to transmit information from one processor to the other. The scheduling problem with rejection arises in make-to-order production systems with limited production capacity and tight delivery requirements, where simultaneous job rejection and scheduling decisions have to be made for maximizing the total revenue. In such systems, accepting orders without considering their impact on the whole system may delay some of the orders beyond their due dates. To be able to preserve high quality of service to customers of accepted orders, the manufacturer has to determine which orders to accept and how to schedule them to maximize total revenue. In reality however, we often have to integrate the two constraints mentioned above together. For instance, construction company A is in charge of a large engineering project, which consists of a number of small projects with precedence relations. For technical reason, it has to transfer some small projects to other construction company, while paying the transportation cost. For example, Eighteen Bureau of China Railway Group is responsible for the construction of the world famous Qinghai Tibet Railway, which is composed of so many precedence-constrained small projects such as track construction, tunnel construction, etc. Yet we know that the construction of Qinghai Tibet Railway permafrost tunnel is undertaken by Twenty Bureau of China Railway Group. Also the design of the duration beam is designed by the Twelve Bureau of China Railway Group. These applications motivate us to consider our main scheduling problem, which is described as follows. Consider a precedence network G = (N , A, c). The node i ∈ N = {1, . . . , n} represents job i, characterized by processing time pi , the time we have to spend if we process i, and penalty qi , which we have to pay if we choose not to process i; each arc (i, j) ∈ A incurs a communication delay ci j , meaning that, after the completion of job i, a duration of ci j must be passed until job j can start; Here we assume that ci j ≤ p j . and any set of jobs J ⊆ N may be rejected for processing with a penalty cost q(J ). The precedence relation is transitive, i.e., (i, j) ∈ A and ( j, k) ∈ A implies that (i, k) ∈ A. The objective is to minimize the sum of the makespan (namely, the latest completion time) and the rejection cost. Following the notation of Graham et al., the scheduling problem can be denoted as P∞ | pr ec, r ej, ci j |Cmax (P) + q(R). Here P(R) stands for the set of processed (rejected) jobs. We consider this problem for both the linear and the submodular penalty function q(·).
1.1 Related work Kelley (1961) studies the precedence-constrained identical machine scheduling problem with infinite number of machines, and the objective is to minimize makespan, namely P∞ | pr ec|Cmax . He proves that this problem is polynomially solvable. Picouleau (1995) studies an extension of this problem where there is communication delay among jobs, namely P∞ | pr ec, ci j |Cmax . He showes that it is N P-hard to determine whether there is a schedule of length 8 when the processing time and the communication delay are both equal to 1. Hoogeveen et al. (1994) improve the previous result, and point out that it is N P-hard to determine whether there is a schedule of length 6, implying that no approximation algorithm exists with ratio less than 76 , unless P = N P. Munier and Konig (1997) propose a 43 -approximation
123
J Comb Optim
algorithm for the problem P∞ | pr ec; p j = ci j = 1|Cmax . Furthermore, they prove that the bound 43 is tight. Hanen and Munier (1995) give a 43 -approximation algorithm for the problem P∞ | pr ec; ci j |Cmax via the linear programming rounding method. Hanen and Munier (1995) study a closely related problem to ours. Their model assumes that among the predecessors of any job j, there is at most one which has no communication delay with j. This may arise when many customers are trying to reach a calling center with only one line operating at any given time, there is only one who may dial through, and the others have to wait. Similarly, there is at most 1 successor for j which has no communication delay with j. They prove that this problem is N P-hard. In this work we extend their model to include job rejection. Many important results concerning the parallel machine scheduling problems with rejection appear in recent years. Bartal et al. (2000) study the rejection problem with identical parallel machines. The objective is to minimize the makespan of the schedule for accepted jobs plus the sum of the penalties of rejected jobs. For the on-line version of this problem, they propose a 1 + φ ≈ 2.618 competitive algorithm, where φ is the golden ratio. For the off-line problem they present a fully polynomial approximation scheme for fixed m and a polynomial approximation scheme for arbitrary m. Seiden (2001) extends the problem of Bartal et al. (2000) by allowing preemption. √ 4 + 10 -competitive is presented. He also proves that An online algorithm which is 3 the competitive ratio of any online algorithm is at least 2.12457. He and Min (2000) consider the problem of on-line uniform machine scheduling with rejection, developing a deterministic algorithm that is optimal for two or three uniform machines that process at different speeds. Engels et al. (2003) develop some techniques to design approximation algorithm for the general problem with rejection. Their main technique is to reduce a problem with rejection to a scheduling problem without rejection based on the linear programming rounding method. Hoogeveen et al. (2003) consider the preemptive scheduling with rejection, and the goal is to optimize the preemptive makespan on the m parallel machines plus the sum of the penalties of the rejected jobs. They provide a complete classification of these scheduling problems with respect to complexity and approximability. On the variant with an arbitrary number of unrelated machines, which is APX-hard, they propose a 1.58-approximation algorithm for it. Moreover, their results for unrelated machines may be carried over to the corresponding preemptive open shop scheduling problem with rejection. Li and Yuan (2010) consider several parallel-machine scheduling problems with deteriorating jobs and rejection. The objective is to minimize the scheduling cost of the accepted jobs plus the total penalty of the rejected jobs. They propose two fully polynomial-time approximation schemes for the problems under consideration. Gerstl and Mosheiov (2012) study scheduling problems with rejection and general position-dependent processing times on parallel identical machines, and they introduce efficient algorithms for the problems, which run in O(n m+3 ) time (which is polynomial for a given number of machines). There are many other important results (Shabtay et al. 2013; Epstein and Haider 2011; Epstein and Haider 2014; Lu et al. 2011; Cheng and Sun 2009; Min et al. 2013; Slotnick 2011).
123
J Comb Optim
1.2 Our work The main contribution of this work is to formulate our problem as a {0, 1}-integer program, which degenerates to the program of Hanen and Munier (1995) when rejection is not allowed. Moreover, we present two 3-approximation algorithms for both linear and submodular penalty functions in Sects. 2 and 3, respectively, via the technique of linear programming rounding.
2 A 3-approximation algorithm with linear rejection We consider the linear penalty function where for any subset of jobs J ⊆ N , q(J ) =
qj.
j∈J
Intuitively, only processed jobs may determine the length of the schedule and rejected jobs have no effect on the makespan. Hence if job j is rejected, it has no communication delay with its predecessors(successors). Here the constraint on the communication delay applies only to those processed jobs, i.e., among the processed predecessors (successors) for each j ∈ P, there is at most one predecessor (successor) which has no communication delay with it. For convenience, add two dummy jobs 0 and n + 1, where p0 = pn+1 = 0, q0 = qn+1 = +∞. Furthermore, ∀1 ≤ j ≤ n, (0, j) ∈ A, ( j, n + 1) ∈ A, and c0 j = c j,n+1 = 0. This means that both 0 and n + 1 are to be processed. Furthermore, C0 = 0 is the earliest possible starting time for job j ( j = 1, 2, · · · , n), and the completion time of job n + 1 is the makespan. Introduce the following decision variables: – For each job j ∈ N : z j :=
1, if j is processed, 0, else.
– For each arc (i, j) ∈ A: xi j : = yi j : =
1, if there is communication delay between i and j, 0, else. 1, if both i and j are processed, 0, else.
– For each job j ∈ N : C j is the completion time. From now on, denote the set {1, 2, · · · , n} by [n]. Our problem can be formulated as the following integer program:
123
J Comb Optim
min Cn+1 +
n
q j (1 − z j )
j=1
s.t. C j − Ci ≥ p j z j + ci j xi j , ∀(i, j) ∈ A xki ≥ yki − 1, ∀i ∈ [n] k =0:(k,i)∈A
j =n+1:(i, j)∈A
k =0:(k,i)∈A
xi j ≥
yi j − 1, ∀i ∈ [n]
j =n+1:(i, j)∈A
xi j ≤ yi j , ∀(i, j) ∈ A yi j ≤ z i , yi j ≤ z j , ∀(i, j) ∈ A yi j ≥ z i + z j − 1, ∀(i, j) ∈ A C0 = 0, z 0 = z n+1 = 1 x0i = xi,n+1 = 0, ∀i ∈ [n] xi j , yi j ∈ {0, 1}, ∀(i, j) ∈ A z i ∈ {0, 1}, ∀i ∈ [n].
(1)
In the above integer program, for rejected job j, C j is defined as the maximum completion time among all its predecessors. Hence C j is either equal to the completion time of some processed predecessor, or 0. Moreover, if job j is rejected, it has no communication delay with its successors. The transitivity of the precedence relation implies that C j has no impact on the completion time of its processed successors. We have z i = 0 for those rejected jobs i. Hence ∀(k, i) ∈ A, (i, j) ∈ A, we have yki = yi j = 0, xki = xi j = 0. The second and third constraints hold obviously. If job i is processed, we have that yi j = 1 ⇐⇒ z i = z j = 1. Thus j =n+1:(i, j)∈A yi j = a(> 0) implies that besides n + 1, a successors for job i are processed. j =n+1:(i, j)∈A x i j takes value a − 1 or a due to the constraint xi j ≥ yi j − 1. j =n+1:(i, j)∈A
j =n+1:(i, j)∈A
For the former, all but one processed successor (besides n + 1) have communication delay with processed job i. For the latter, each processed successor (besides n + 1) has communication delay with processed job i. This is the similar to the predecessors (the second constraint). We declare that the integer program (1) is a formulation for the considered problem. Substituting the constraints xi j , yi j ∈ {0, 1}, ∀(i, j) ∈ A and z i ∈ {0, 1}, ∀i ∈ [n] by xi j , yi j ≥ 0, ∀(i, j) ∈ A and z i ≥ 0, ∀i ∈ [n], we get the linear program relaxation for the integer program (1), which is denoted by linear program (1). We may infer from the constraints in linear program (1) that z i ≤ 1, ∀i ∈ [n], xi j ≤ yi j ≤ 1, ∀(i, j) ∈ A.∀i ∈ [n]. On one hand we have y0i ≤ z i ; On the other hand we have y0i ≥ z 0 + z i − 1 = z i . Therefore we have z i = y0i ≤ z 0 = 1 for ∀i ∈ [n]. ∀(i, j) ∈ A, xi j ≤ yi j ≤ z i (z j ) ≤ 1. The optimal solution to the linear program (1) is denoted by (xi∗j , yi∗j , z i∗ ), clearly n ∗ + q j (1 − z ∗j ) ≤ O P T , where O P T is the optimal value for the we have Cn+1 j=1
123
J Comb Optim ∗ scheduling problem. Here Cn+1 is the length of the longest path from vertex 0 to n + 1 when the length of each arc (i, j) ∈ A is denied as p j z ∗j + ci j xi∗j in the directed graph G. We now round (xi∗j , yi∗j , z i∗ ) into a feasible solution (x i j , y i j , z i ) for the integer program (1) in the following way: ∀i ∈ [n], if z i∗ < α (0 < α < 1), then z i = 0 (i is rejected). At this time ∀(k, i) ∈ A, (i, j) ∈ A, we have x ki = y ki = 0, x i j = y i j = 0. We have z i = 1 for any i satisfying z i∗ ≥ α. Also ∀(i, j) ∈ A, y i j = 1 ⇐⇒ z i = z j = 1 ⇐⇒ z i∗ ≥ α, z ∗j ≥ α. Thus the set of processed jobs P is determined. Set P1 = P \ {0, n + 1}. The subgraph induced by the job nodes in P1 is denoted by G P1 . To determine the set of pairs (i, j) without communication delay, we apply the following procedure W C D(short for without communication delay). Pick an arbitrary arc (i, j) in G P1 , and let x i j = 0, which means there is no communication delay between job i and its successor j. For any other (i , j) with i = i and (i, j ) with j = j, let x i j = x i j = 1. Delete from G P1 all edges starting from node i and all edges ending at node j. Repeat the above process until all the edges are deleted from G P1 . We argue that for any j ∈ P1 , there is at most one i ∈ P1 satisfying (i, j) ∈ A and x i j = 0. Once the arc (i, j) is chosen and set x i j = 0 recursively, all the other remaining arcs (i , j) are set x i j = 1. All the remaining edges ending at node j are removed from G P1 . That is, once the arc (i, j) is set x i j = 0 recursively, the in-degree for node j becomes 0. Similarly, for any j ∈ P1 , there is at most one k ∈ P1 satisfying ( j, k) ∈ A and x jk = 0. Next we analyze the quality of the solution (x i j , y i j , z i ). We first consider the makespan C n+1 , which is the length of the longest path from vertex 0 to n + 1 when the length of each arc (i, j) ∈ A is denied as p j z j + ci j x i j in the directed graph G. Let ∗ be the corresponding makespan when the length of each (i, j) ∈ A is defined as Cn+1 p j z ∗j + ci j xi∗j in the directed graph G. We compare p j z j + ci j x i j with p j z ∗j + ci j xi∗j in the following three cases:
Case 1. z j = 1, x i j = 1. This implies that z ∗j ≥ α, z i∗ ≥ α. Hence we have
p j z j + ci j x i j = p j + ci j ≤ 2 p j ≤
2 p j z ∗j α
≤
2 p j z ∗j + ci j xi∗j . α
The first inequality follows from the assumption ci j ≤ p j . Case 2. z j = 1, x i j = 0. This implies that z ∗j ≥ α, moreover we have
p j z j + ci j x i j = p j ≤
123
p j z ∗j α
≤
2 ( p j z ∗j + ci j xi∗j ). α
J Comb Optim
Case 3. z j = 0, x i j = 0. Clearly we have p j z j + ci j x i j = 0 ≤
2 ( p j z ∗j + ci j xi∗j ). α
∗ . From the discussion above we conclude that C n+1 ≤ α2 Cn+1 We now consider the total rejection cost for the rejected jobs. We have
qj =
j:z ∗j <α
j:z j =0
<
qj =
qj
j:1−z ∗j >1−α
q j (1 − z ∗j ) 1−α
j:1−z ∗j >1−α
≤
n 1 q j (1 − z ∗j ). 1−α j=1
Therefore we have ⎞ ⎛ n 1 2 ∗ ⎝Cn+1 , C n+1 + q j ≤ max + q j (1 − z ∗j )⎠ α 1−α j=1 j:z j =0 1 2 , O P T. ≤ max α 1−α
The approximation ratio for this rounding algorithm is max
2 1 α , 1−α
, which is
minimized when = i.e., α = implying that the approximation ratio is 3 with this choice of α. To summarize, we have the following algorithm for P∞ | pr ec, r ej, ci j |Cmax (P) + q(R) with approximation ratio 3. 2 α
1 1−α ,
2 3,
Algorithm 1 Step 1: Formulate the scheduling problem as a {0, 1}-integer programming. Step 2: Relax the integer programming as a linear program. Step 3: Solve the linear program to obtain an optimal solution (xi∗j , yi∗j , z i∗ ). Step 4: Set z i = 1 whenever z i∗ ≥ 23 . ∀(i, j) ∈ A, y i j = 1 ⇐⇒ z i = z j = 1. y i j = 0 ⇒ x i j = 0. Step 5:For the set of processed jobs, apply procedure W C D to determine the set of pairs (i, j) without communication delay. Step 6:Construct a feasible solution for the scheduling problem from (x i j , y i j , z i ). Theorem 2 Algorithm 1 is a 3-approximation algorithm for the scheduling problem with linear rejection.
123
J Comb Optim
3 An approximation algorithm with submodular rejection In this section we extend the problem discussed in Sect. 2 to the one with submodular rejection, namely, the penalty function q(S) is a non-negative, increasing, submodular function defined on the ground set {1, 2, · · · , n}, satisfying (1) q(∅) = 0; (2) ∀S ⊆ T ⊆ {1, 2, · · · , n}, q(S) ≤ q(T ); and (3) ∀S, T ⊆ {1, 2, · · · , n}, q(S) + q(T ) ≥ q(S ∪ T ) + q(S ∩ T ). The objective is to decide the set of rejected jobs so that the sum of makespan for the accepted jobs and the penalty for the rejected job set is minimized. Similar as before, add two dummy jobs 0 and n + 1. We regulate that p0 = pn+1 = 0, q0 = qn+1 = +∞. Furthermore, for ∀1 ≤ j ≤ n, we have (0, j) ∈ A, ( j, n + 1) ∈ A, and c0 j = c j,n+1 = 0. Define an indicator variable z S for each subset S ⊆ {0, 1, · · · , n + 1} as follows: z S :=
1, if jobs in S are all rejected, 0, otherwise.
From the definitions for variable z S and jobs 0 and n + 1, we have z S:0∈S = z S:n+1∈S = 0. The meaning for variables xi j , yi j is the same as that in Section 2, and we are now ready to give the following {0, 1}-integer program. min Cn+1 +
q(S)z S
S:S⊆[n]
s.t. C j − Ci ≥ p j (1 −
z S ) + ci j xi j , ∀(i, j) ∈ A
S: j∈S
xki ≥
k =0:(k,i)∈A
yki − 1, ∀i ∈ [n]
k =0:(k,i)∈A
xi j ≥
j =n+1:(i, j)∈A
yi j − 1, ∀i ∈ [n]
j =n+1:(i, j)∈A
xi j ≤ yi j , ∀(i, j) ∈ A z S , yi j ≤ 1 − z S , ∀(i, j) ∈ A yi j ≤ 1 − S:i∈S
yi j ≥ (1 −
S:i∈S
S: j∈S
z S ) + (1 −
z S ) − 1, ∀(i, j) ∈ A
S: j∈S
C0 = 0, z S:0∈S = z S:n+1∈S = 0 x0i = xi,n+1 = 0, ∀i ∈ [n] xi j , yi j ∈ {0, 1}, ∀(i, j) ∈ A z S ∈ {0, 1}, ∀S ⊆ [n].
123
(2)
J Comb Optim
We claim that integer program (2) is a formulation for our scheduling problem from the standpoint of optimal value. Given an optimal solution π ∗ to the scheduling problem, and the rejected job set in π ∗ is S ∗ , we can construct a feasible solution (x i j , y i j , z S ) for integer program (2) in the following way, zS : = yi j : = xi j : =
1, if S = S ∗ , 0, otherwise. 1, both i and j are processed in π ∗ , 0, otherwise. 1, if y i j = 1, and there is delay between i and j in π ∗ , 0, otherwise.
It is easy to verify that (x i j , y i j , z S ) is a feasible solution for integer program (2). Note that from the construction of z S , x i j , and y i j , we only need to check constraints 2 and 3. We now prove the former, and the latter is analogous. For all i ∈ [n], If job i is processed, then the definition of y ki implies that y ki = 1 if and only if job k is also processed. Hence k =0:(k,i)∈A y ki is the number of processed predecessors (besides 0) for job i, while k =0:(k,i)∈A x ki is the number of processed predecessors (besides 0) having communication delays with job i. Among the processed predecessors (besides is at most one with 0) for job i, there out any communication delay with i. So k =0:(k,i)∈A x ki ≥ k =0:(k,i)∈A y ki − 1 x = y = 0. Clearly we have holds clearly. If job i is rejected, ki ki k =0:(k,i)∈A x ki ≥ y − 1. k =0:(k,i)∈A ki Moreover, the objective value for (x i j , y i j , z S ) in integer program (2) is equal to O P T (S), which is the optimal objective value for the scheduling problem. So the optimal value for integer program (2), denoted by O P T (I P), has the following: O P T (I P) ≤ O P T (S). On the other hand, assume (xi∗j , yi∗j , z ∗S ) is an optimal solution for integer program (2), we claim that there is only one set S1 with z ∗S1 = 1. First, for any two sets S1 and S2 satisfying z ∗S1 = z ∗S2 = 1, we have S1 ∩ S2 = φ. Otherwise suppose there ∗ ≤ y∗ ≤ existsan element i 0 with i 0 ∈ S1 ∩ S2 , then we may infer that 0 = x0i 0i 0 0 ∗ ∗ ∗ 1 − S:i0 ∈S z S ≤ −1, a contradiction. Assume z S1 = z S2 = · · · = z ∗Sk = 1, and let S = S1 ∪ · · · ∪ Sk , z S = 1, z S = 0 for ∀S = S. Because the function q(S) z S ) is an is a submodular function, it is easy to verify that the solution (xi∗j , yi∗j , optimal solution for integer program (2). We reject job i whenever i ∈ S, i.e., S is the index set for the rejected jobs. For any two processed jobs i, j, and (i, j) ∈ A, there is communication delay between i and j whenever xi∗j = 1. Hence we obtain a solution for the scheduling problem, with the objective value for this solution equal to O P T (I P). Certainly we have O P T (S) ≤ O P T (I P). Therefore the integer program (2) is equivalent to our scheduling problem from the standpoint of optimal value. Substituting the last two constraints in integer program (2) by xi j , yi j ≥ 0, ∀(i, j) ∈ A and z S ≥ 0, ∀S ⊆ [n], we get the linear program relaxation for integer program (2), which is denoted by linear program (2).
123
J Comb Optim
Note that there are exponential number of variables in linear program (2). To claim that this linear program is polynomially solvable, we give the dual program for linear program (2). Note that the dual variables corresponding to the constraints in linear program (2) are denoted by αi j , si , ti , βi j , u i j , vi j , γi j respectively. max
p j αi j −
j i:(i, j)∈A
s.t.
αki −
k:(k,i)∈A
n
si −
i=1
n
ti −
ui j −
(i, j)∈A
i=1
vi j +
(i, j)∈A
γi j
(i, j)∈A
αi j ≤ 0, ∀i ∈ [n]
j:(i, j)∈A
αi,n+1 ≤ 1
i
−ci j αi j + s j + ti − βi j ≤ 0, ∀(i, j) ∈ A −s j − ti + βi j − u i j − vi j + γi j ≤ 0, ∀(i, j) ∈ A (γi j − vi j + p j αi j ) + (γi j − u i j ) ≤ q(S), ∀S ⊆ [n] j: j∈S i:(i, j)∈A
i:i∈S j:(i, j)∈A
αi j , βi j , u i j , vi j , γi j ≥ 0, ∀(i, j) ∈ A si , ti ≥ 0, ∀i ∈ [n].
(3)
We show that the submodular constraint above can be checked in polynomial time. We rewrite this constraint as follows: i:i∈S
⎡
⎣
(γki − vki + pi αki ) +
k:(k,i)∈A
⎤ (γi j − u i j )⎦ ≤ q(S), ∀S ⊆ [n]. (4)
j:(i, j)∈A
Denote f i :=
(γki − vki + pi αki ) +
k:(k,i)∈A
(γi j − u i j ).
j:(i, j)∈A
The inequality (4) is equivalent to the following: min
S:S⊆[n]
q(S) −
fi
≥ 0.
i:i∈S
This may be checked in polynomial time. Denote the optimal solution for linear program (2) by (xi∗j , yi∗j , z ∗S ), and the opti ∗ ∗ + S:S⊆[n] q(S)z ∗S . Clearly we have Cn+1 + S:S⊆[n] q(S)z ∗S ≤ mal value by Cn+1 O P T (S) (recall that O P T (S) is the optimal value for our scheduling problem). ∗ ≤ z ∗S ≤ 1. From the constraints y0i We claim that for any i ∈ [n], we have S:i∈S ∗ ≥ (1− ∗ ∗ ∗ 1− S:i∈S z ∗S , y0i S:0∈S z S )+(1− S:i∈S z S )−1 = 1− S:i∈S z S , we know
123
J Comb Optim
∗ = 1− ∗ ∗ ∗ that y0i S:i∈S z S . Furthermore, y0i ≥ 0. Thus we may infer S:i∈S z S ≤ 1 for any i ∈ [n]. Next we round (xi∗j , yi∗j , z ∗S ) into a feasible solution (x i j , y i j , z S ) for the scheduling problem as follows: Reject job j whenever S: j∈S z ∗S > α (0 < α < 1). Thus we determine the set of rejected jobs R. We have z R = 1, z S = 0 for any S with S = R. Moreover ∀(i, j) ∈ A, y i j = 1 ⇐⇒
z ∗S ≤ α,
S:i∈S
z ∗S ≤ α.
S: j∈S
y i j = 0 ⇒ x i j = 0. We apply the same procedure to determine the set of pairs (i, j) without communication delay for i, j ∈ P, which is the set of processed jobs. We now analyze the performance of the solution (x i j , y i j , z S ). First we look at the makespan C n+1 . Similar as before, C n+1 is the length of the longest path from vertex 0 to n + 1 z S ) + ci j x i j in the when the length for each arc (i, j) ∈ A is defined as p j (1 − S: j∈S
∗ is the counterpart when the length for each arc (i, j) ∈ A directed graph G. And Cn+1 z ∗S ) + ci j xi∗j in the directed graph G. is defined as p j (1 − S: j∈S We compare p j (1 − S: j∈S z S ) + ci j x i j with p j (1 − S: j∈S z ∗S ) + ci j xi∗j in the following three cases: Case 1. 1 − S: j∈S z S = 1, x i j = 1. This implies that S: j∈S z ∗S ≤ α, 1 − S: j∈S z ∗S ≥ 1 − α. Hence we have
p j (1 −
z S ) + ci j x i j
S: j∈S
= p j + ci j ≤ 2 p j ∗ zS 2pj 1 − ≤
S: j∈S
1−α ⎡ ⎛
⎞ ⎤ 2 ⎣ ⎝ z ∗S ⎠ + ci j xi∗j ⎦ . ≤ pj 1 − 1−α S: j∈S
The first inequality follows from the assumption ci j ≤ p j . Case 2.1 − S: j∈S z S = 1, x i j = 0. This implies that S: j∈S z ∗S ≤ α, 1 − S: j∈S z ∗S ≥ 1 − α. Therefore ⎛ p j ⎝1 −
S: j∈S
⎞ z S ⎠ + ci j x i j
⎞ ⎤ ⎡ ⎛ 2 ⎣ ⎝ ≤ z ∗S ⎠ + ci j xi∗j ⎦ . pj 1 − 1−α S: j∈S
123
J Comb Optim
Case 3. 1 − S: j∈S z S = 0, x i j = 0. Clearly we have ⎛
p j ⎝1 −
⎞ z S ⎠ + ci j x i j
S: j∈S
⎞ ⎤ ⎡ ⎛ 2 ⎣ ⎝ =0≤ z ∗S ⎠ + ci j xi∗j ⎦ . pj 1 − 1−α S: j∈S
2 ∗ . From the discussion above we conclude that C n+1 ≤ 1−α Cn+1 As for the total penalty for the rejected jobs, we have
qR ≤
qi <
i∈R
i∈R
qi
S:i∈S
z ∗S
α
≤
1 1 q S z ∗S ≤ q(S)z ∗S . α α i∈R S:i∈S
S⊆J
Hence we have C n+1 + q R ≤ max
2 1 ∗ (Cn+1 + q(S)z ∗S ), , 1−α α S⊆J
2 2 and the approximation ratio is max{ 1−α , α1 }, which is minimized when 1−α = α1 , i.e., α = 13 , implying that approximation ratio is 3. Finally, we present an approximation algorithm for this scheduling problem with submodular rejection with an approximation ratio 3.
Algorithm 3 Step 1: Formulate the scheduling problem as a {0, 1}-integer programming. Step 2: Relax the integer program as a linear program. Step 3: Solve the linear programming relaxation to obtain the optimal solution (xi∗j , yi∗j , z ∗S ). Step 4:Reject job j whenever S: j∈S z ∗S > 13 . Denote by R the set of rejected jobs. Set z R = 1, z S = 0 for any S with S = R. 1 1 ∗ ∗ Step 5:∀(i, j) ∈ A, y i j = 1 ⇐⇒ S:i∈S z S ≤ 3 , S: j∈S z S ≤ 3 . x i j = 0 whenever y i j = 0. Step 6:For the set of processed jobs, apply procedure W C D to determine the set of arcs (i, j) without communication delay. Step 7:Construct a feasible solution for the scheduling problem from (x i j , y i j , z S ). Theorem 4 Algorithm 3 is a 3-approximation algorithm for the scheduling problem with submodular rejection.
4 Conclusion In this paper we study a precedence-constrained identical parallel machine scheduling problem with rejection. There is a communication delay between any two jobs connected in the precedence network; and jobs may be rejected with penalty. The
123
J Comb Optim
goal is to minimize the sum of the makespan and the rejection cost. We propose two 3-approximation algorithms for this problem under linear rejection and submodular rejection respectively. These two algorithms are both based on linear programming rounding technique. Acknowledgments The research of the second author is supported by NSFC (No. 11531014) and Collaborative Innovation Center on Beijing Society-Building and Social Governance. The third author’s research is supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) Grant 283106. The fourth author’s research is supported by NSFC (No. 11501412).
References Bartal Y, Leonardi S, Marchetti-Spaccamela A, Sgall J, Stougie L (2000) Multiprocessor scheduling with rejection. SIAM J Discret Math 13:64–78 Cheng YS, Sun SJ (2009) Scheduling linear deteriorating jobs with rejection on a single machine. Eur J Op Res 194:18–27 Engels DW, Karger DR, Kolliopoulos SG, Sengupta S, Uma RN, Wein J (2003) Techniques for scheduling with rejection. J Algorithms 49:175–191 Epstein L, Haider HZ (2011) Online scheduling with rejection and withdrawal. Theor Comput Sci 412:6666– 6674 Epstein L, Haider HZ (2014) Preemptive online scheduling with rejection of unit jobs on two uniformly related machines. J Sched 17:87–93 Gerstl E, Mosheiov G (2012) Scheduling on parallel identical machines with job-rejection and positiondependent processing times. Inf Process Lett 112:743–747 Hanen C, Munier A (1995) An approximation algorithm for scheduling dependent tasks on m processors with small communication delays. In: Proceedings of the INREA/IEEE symposium on emerging technologies and factory automation, pp 167–190 He Y, Min X (2000) On-line uniform machine scheduling with rejection. Computing 65:1–12 Hoogeveen JA, Lenstra JK, Veltman B (1994) Three, four, five, six, or the complexity of scheduling with communication delays. Op Res Lett 16:129–137 Hoogeveen H, Skutella M, Woeginger GJ (2003) Preemptive scheduling with rejection. Math Progr Ser B 94:361–374 Kelley J (1961) Critical-path planning and scheduling: mathematical basis. Op Res 9:296–320 Li SS, Yuan JJ (2010) Parallel-machine scheduling with deteriorating jobs and rejection. Theor Comput Sci 411:3642–3650 Lu LF, Ng CT, Zhang LQ (2011) Optimal algorithms for single-machine scheduling with rejection to minimize the makespan. Int J Prod Econ 130:153–158 Min X, Wang YQ, Liu J, Jiang M (2013) Semi-online scheduling on two identical machines with rejection. J Comb Optim 26:472–479 Munier A, Konig J (1997) A heuristic for a scheduling problem with communication delays. Op Res 45:145–147 Picouleau C (1995) New complexity results on scheduling with small communication delays. Discr Appl Math 60:331–342 Seiden SS (2001) Preemptive multiprocessor scheduling with rejection. Theor Comput Sci 262:437–458 Shabtay D, Gaspar N, Kaspi M (2013) A survey on offline scheduling with rejection. J Sched 16:3–28 Slotnick SA (2011) Order acceptance and scheduling: a taxonomy and review. Eur J Op Res 212:1–11
123