J Comb Optim DOI 10.1007/s10878-013-9643-7

Approximation algorithms for maximizing the weighted number of early jobs on a single machine with non-availability intervals Imed Kacem · Hans Kellerer · Yann Lanuel

© Springer Science+Business Media New York 2013

Abstract In this paper we consider the maximization of the weighted number of early jobs on a single machine with non-availability constraints. We deal with the resumable and the non-resumable cases. We show that the resumable version of this problem has a fully polynomial time approximation scheme (FPTAS) even if the number of the non-availability intervals is variable and a subset of jobs has deadlines instead of due dates. For the non-resumable version we remark that the problem cannot admit an FPTAS even if all due dates are equal and only one non-availability interval occurs. Nevertheless, we show in this case that it admits a polynomial time approximation scheme (PTAS) for a constant number of non-availability intervals and arbitrary due dates. Keywords Scheduling · Non-availability intervals · Late jobs · Approximation algorithms

1 Introduction The single machine scheduling model with machine availability constraints with the objective of minimizing the weighted number of late jobs is defined as follows. We

I. Kacem (B) · Y. Lanuel LCOMS EA 7603, Université de Lorraine, Ile du Saulcy, 57000 Metz, France e-mail: [email protected] Y. Lanuel e-mail: [email protected] H. Kellerer ISOR, University of Graz, Graz, Austria e-mail: [email protected]

123

J Comb Optim

are given a set J of n jobs J = {1, 2, . . . , n}. Every job j has a processing time p j , a due date d j and a weight w j . The jobs have to be performed  on a single machine. It is required to minimize the weighted number of late jobs nj=1 w j U j where the unit penalty U j is defined as  Uj =

1 0

if if

Cj > dj, Cj ≤ dj.

where C j is the completion time of job j.  We can consider an equivalent objective function nj=1 w j U¯ j of maximizing the weighted number of early jobs where U¯ j is defined as U¯ j =



1 0

if if

Cj ≤ dj, Cj > dj.

Without loss of generality, we consider that jobs are sorted in the Earliest Due Date (EDD) order, i.e., d1 ≤ d2 ≤ · · · ≤ dn . Assume that for the processing machine there are k known non-availability intervals Ih = [ah , bh ] , h = 1, . . . , k, during which the machine cannot perform any job. If there is only one non-availability interval, we will shortly denote it by [a, b]. Equivalently, we define k + 1 availability time intervals Th = [bh−1 , ah ], h = 1, . . . , k + 1. with b0 = 0 and ak+1 = +∞. Note that if for a given job j, its due date d j belongs to some non-availability interval Ih , then we set d j := ah . The non-availability intervals can be due to some scheduled activity other than processing (a maintenance period, a rest period, etc.). A job that is affected by a nonavailability interval is called crossover job. There are several possible scenarios to handle a crossover job. Under the non-resumable scenario, the crossover job that cannot be completed by time ah is restarted from scratch at time bh . Under the resumable scenario the crossover job is interrupted at time ah and resumed from the point of interruption at time bh . Extending standard scheduling notation, we denote the resulting problem for minimizing the weighted number of late jobs under the non-resumable sce U , and that underthe resumable scenario by nario by 1|h(k), N − r es| w j j  ¯ 1|h(k), Res| w j U j . For problem 1|h(k), N − r es| w j U j we will shortly write ¯ nr , and we will abbreviate 1|h(k), Res| w j U j by r . We will also consider the case that some jobs j have deadlines d¯ j instead of due dates d j . If a job j has a deadline d¯ j , it is not allowed that the job is late. Consequently, it is not clear whether an instance with deadlines admits a feasible solution. The extension of problem r to deadlines is denoted by 1|h(k), d¯ j , Res| w j U¯ j and abbreviated by r d . Since 1|h(1), N −r es|Cmax is binary NP-hard (see e.g., Lee (1996)), it follows that also 1|h(1), N − r es| U j is binary NP-hard. The fact that this problem under consideration is NP-hard, stimulates the search of approximation algorithms that deliver

123

J Comb Optim

solutions fairly close to the optimum. Recall some relevant definitions for a given minimization problem. A polynomial-time algorithm that creates a solution with the objective function value that is at most ρ ≥ 1 times the optimal value is called a ρ−approximation algorithm; the value of ρ is called a worst-case ratio bound. A family of algorithms is called a polynomial-time approximation scheme, or a PTAS if for a given ε > 0 it contains an algorithm that has the running time that is polynomial in the length of the problem input and delivers a worst-case ratio bound of 1 + ε. If additionally the running time is polynomial in 1/ε, a PTAS is called a fully polynomialtime approximation scheme (FPTAS). For maximization problems the definitions have to be changed accordingly.  It is well-known that problem 1| · | U j can besolved by the Moore-Hodgson algorithm in O(n log n) time, while problem 1| · | w j U j is binary NP-hard, see e.g. Pinedo (2012). However, it is pseudopolynomially solvable by a dynamic pro gramming algorithm by Lawler and Moore (1969). An FPTAS for 1| · | w j U¯ j is presented by  Sahni (1976). Gens and Levner (1978, 1981) propose FPTAS’s for problem 1| · | w j U j .  As mentioned by Lee (1996) problem 1|h(1), Res| U j can be solved by applying the Moore-Hodgson algorithm and adding the unavailable time b − a to the completion times of those jobs finished after a. If we apply Moore and Hodgson to the resumable case and delete the crossover job, we get a feasible solution to the nonresumable problem which has one more tardy job than the optimal solution for the resumable case.  Hence, the absolute difference between this solution for problem 1|h(1), N − r es| U j and the optimal solution is at most one (see Lee (1996)). We refer to the surveys by Lee (2004), by Ma et al. (2010) and by Schmidt (2000) for general reviews of deterministic scheduling under availability constraints. Obviously, 1|h(k), N − r es| w j U j is equivalent to problem nr , but for analyzing approximation algorithms it is preferable to consider nr instead  of  1|h(k), N − r es| w j U j . Notice that even the basic problem 1|h(1), N − r es| U j is not approximable within a constant factor. This will be shown in the beginning of nSect. 3. Therefore, we will concentrate in the following on the objective function ¯ j=1 w j U j of maximizing the weighted number of early jobs. This paper is organized as follows. In the next section we will present a dynamic programming algorithm and an FPTAS for the resumable problem with deadlines r d . In Sect. 3 itis shown that there is no FPTAS for the non-resumable problem 1|h(1), N − r es| U¯ j and a PTAS is provided for problem nr with a fixed number of non-availability intervals k. 2 The resumable problem with deadlines 1|h(k), d¯ j , Res|



w j U¯ j

In this section we will consider the resumable problemwith deadlines r d . Obviw j U¯ j ously, every optimal solution for the problems 1|Res| w j U j or 1|Res|  is non-preemptive. Hence, from the binary NP-hardness of 1| · | w j U j follows that also problems r and r d are binary NP-hard. In the beginning we will show how to transform the problem with deadlines r d into a problem r without deadlines. Then, we propose a dynamic program for problem r which

123

J Comb Optim

has pseudopolynomial running time and we convert this dynamic program into an FPTAS. Consequently, this gives us also a dynamic program and an FPTAS for r d . Let t ∈ [0, a1 ] ∪ [b1 , a2 ] ∪ · · · ∪ [bk−1 , ak ] ∪ [bk , +∞]. We define the function F = F(t, p) as the completion time of a job with processing time p and starting time t when this job is not interrupted by any other job (but possibly by a non-availability interval). The computation of any value F(t, p) can be done in O(k) time. It is easy to handle a resumable problem with deadlines since jobs with deadlines in EDD order can be scheduled in an optimal schedule as late as possible. Let J  be the subset of jobs with deadlines and n  be the cardinality of J  . Algorithm TA computes the completion times of jobs in J  by processing them as late as possible or it shows that no schedule exists which meets all deadline constraints. Without loss of generality, the scheduled jobs of J  can be seen as non-availability intervals. Thus, Algorithm TA transforms a problem r d in a problem r without deadlines but additional non-availability intervals. Note that the calculation of ti in Step 3 of Algorithm TA can be done easily in the same way as for F by reversing the time scale. Algorithm 1 Transformation Algorithm TA Assume jobs in J  are sorted in non-decreasing order of their deadlines: J  = { j1 , j2 , . . . , jn  } such that d j1 ≤ d j2 ≤ · · · ≤ d j  n 1. C = d j  ; S = ∅; i = n  + 1 (initialization) n 2. i = i − 1; C ji = C; S = S ∪ { ji } 3. Calculate ti such that F(ti , p ji ) = C. 4. If ti < 0, STOP, there is no feasible solution. 5. If i = 1, STOP, output the transformed instance without deadlines. 6. Set C = min{ti , d ji−1 } and goto 2.

2.1 Dynamic programming algorithm In this section, we describe an exact algorithm DP based on dynamic programming to solve r . DP consists in n iterations j = 1, 2, . . . , n. At every iteration j, we consider the scheduling of job j and we generate a set χ j of states corresponding to some partial schedules of {1, 2, . . . , j}. Every state from χ j , 1 ≤ j ≤ n, can be reduced to a vector [t, w] where t is the completion time of the last early job and w is the sum of weights of early jobs. It is easy to see that the algorithm has a pseudopolynomial time complexity.   Set P = nj=1 p j and W = nj=1 w j . Let z denote the total time in [0, t] which is not blocked by non-availability intervals. Since z and w can respectively be bounded by min{dn , P} and W , the number of generated states can be bounded by W min{dn , P}. The number of generated states can be reduced to O(W ) by keeping for every value w the state [t, w] with the smallest value t at each iteration. This results in a total running time of O(knW ) since the calculation of each value F(t, p) takes O(k) time. By keeping for every value t the state [t, w] with the greatest value w at each iteration the running time is reduced to O(kn min{dn , P}).

123

J Comb Optim

Algorithm 2 Dynamic Programming Algorithm DP χ0 = {[0, 0]} for every j = 1, 2, . . . , n do χj = ∅ for every state [t, w] ∈ χ j−1 do χ j = χ j ∪ {[t, w]} if F(t, p j ) ≤ d j then χ j = χ j ∪ {[F(t, p j ), w + w j ]} end if end for end for Output the optimal solution value max{w| [t, w] ∈ χn }

2.2 A fully polynomial time approximation scheme The proposed FPTAS is denoted by Aε where ε > 0 is the required error. Aε is based on a conversion of algorithm DP by modifying the dynamic programming range. The technique of conversion has been successfully applied in the literature to other combinatorial problems. A sample of related works includes Sahni (1977), Potts and Wassenhove (1992), Kacem  and Kellerer (2011), Kellerer and Strusevich (2006). The weight range [0, W ] of w j U¯ j is partitioned into m + 1 intervals: U0 = {0} and Ur = [(1 + ε)

r −1 n

r

, (1 + ε) n [, r = 1, . . . , m

with m := n log1+ε W . Note that m = O( nε log W ) and hence polynomial in the length of the encoded input. The crux of this construction is to guarantee that every 1 point in each interval is at least the upper interval endpoint divided by (1 + ε) n . Algorithm Aε generates a subset χ˜j of states at every iteration j, j = 1, . . . , n, in a similar way compared to the construction of χ j in algorithm DP. The difference ˜ in the consists in the simplification introduced in Aε by keeping a single state [t˜, w] interval Ur with the smallest value of t˜ where w˜ ∈ Ur , r = 1, 2, . . . , m. Algorithm 3 FPTAS Aε χ˜ 0 = {[0, 0]} for every j = 1, 2, . . . , n do χ˜ j = ∅ for every state [t, w] ∈ χ˜ j−1 do χ˜ j = χ˜ j ∪ {[t, w]} if F(t, p j ) ≤ d j then χ˜ j = χ˜ j ∪ {[F(t, p j ), w + w j ]} end if end for For every r = 1, 2, . . . , m find the state [t, w] with the smallest value of t where w ∈ Ur and keep only this state in χ˜ j end for return the best solution from χ˜ n

123

J Comb Optim

Since we keep only O(m) states in χ˜ j at iteration j, the complexity of algorithm 2 Aε is in O(knm) = O(k nε log W ). 1

Lemma 2.1 Let δ = (1 + ε) n . For every state [t, w] ∈ χ j there exists at least a state [t˜, w] ˜ ∈ χ˜ j such that t˜ ≤ t and w˜ ≥ δ − j w. Proof (By induction) For j = 0, we have χ˜ 0 = χ0 . Then, the statement is true for j = 0. Assume the result holds for r = 0, 1, . . . , j − 1. Let [t, w] ∈ χ j . Two cases can hold: Case 1 : [t, w] = [t  , w  ] where [t  , w  ] ∈ χ j−1 . From the assumption, there exists [t˜ , w˜  ] ∈ χ˜ j−1 such that t˜ ≤ t  and w˜  ≥ − δ j+1 w  . Since [t˜ , w˜  ] is generated by Aε at iteration j, there exists a state [α, β] that will be kept by the algorithm at the end of iteration j such that α ≤ t˜ ≤ t  = t and β ≥ δ −1 w˜  ≥ δ − j w  = δ − j w are true. Therefore, the result holds in Case 1. Case 2 : [t, w] = [F(t  , p j ), w  + w j ] where [t  , w  ] ∈ χ j−1 From the assumption, there exists [t˜ , w˜  ] ∈ χ˜ j−1 such that t˜ ≤ t  and w˜  ≥ − δ j+1 w  . Since t˜ ≤ t  then F(t˜ , p j ) ≤ F(t  , p j ) ≤ d j . Hence, [F(t˜ , p j ), w˜  + w j ] is generated by Aε at iteration j and there exists a state [γ , θ ] that will be kept by the algorithm at the end of iteration j such that γ ≤ F(t˜ , p j ) ≤ F(t  , p j ) = t and θ ≥ δ −1 (w˜  + w j ) ≥ δ −1 (δ − j+1 w  + w j ) > δ − j (w  + w j ) = δ − j w. 

are true. Hence, the result holds for level j. Theorem 2.2 There is an FPTAS for problem r d . 2

Proof Recall that the complexity of Aε is bounded by O(k nε log W ). By Lemma 2.1, there exists a state [t˜, w] ˜ ∈ χ˜ n such that t˜ ≤ t ∗ and w˜ ≥ δ −n w ∗ where [t ∗ , w ∗ ] is 1 w ∗ ≥ (1 − ε)w ∗ , we can deduce that the an optimal state. From w˜ ≥ δ −n w ∗ = 1+ε schedule associated with [t˜, w] ˜ is a (1 − ε)-approximation. Hence, Aε is an FPTAS for problem r . With Algorithm TA a problem with deadlines is transformed into a  problem without deadlines. Thus, we have also an FPTAS for problem r d . 3 The non-resumable problem 1|h(k), N − r es|



w j U¯ j

 In this section we will present a PTAS for problem nr = 1|h(k), N − r es| w j U¯ j with a fixed number of non-availability intervals k and show that there is no FPTAS for the non-resumable problem even if with only one non-availability period 1|h(1),  N − r es| U¯ j . Note that it is even NP-complete to decide whether there is a solution for the  problem 1|h(1), N − r es| U j with zero late jobs which can be shown by reduction from Partition.  Partition: Given n integers e j such that nj=1 e j = 2E, does there exist a partition and N such that of the index set N = {1, 2, . . . , n} into two subsets N 1 2 j∈N1 e j =  e = E? j∈N2 j  Given an instance of Partition, define an instance of 1|h(1), N − r es| U j by

123

J Comb Optim

• p j = e j , d j = 2E, j = 1, . . . , n, • a = b = E. It can be easily seen that the constructed problem has a solutionwith no late jobs if and only if Partition has a solution. Therefore, 1|h(1), N −r es| U j is not approximable within a constant factor, although we can find in polynomial time a solution which has at most one more late job than an optimal solution Lee (1996). Thus, for constructing an approximation algorithm for the non-resumable problem we consider  the problem of maximizing the weighted number of early jobs 1|h(1), N − r es| w j U¯ j  instead of 1|h(1), N − r es| w j U j . Unfortunately, there is no FPTAS for 1|h(1), N − r es| U¯ j which is shown in the following lemma.  Lemma 3.1 There is no FPTAS for problem 1|h(1), N − r es| U¯ j unless P = N P even if all due dates are equal. Proof Given  an instance of Partition, we use the same instance of 1|h(1), has a solution if and only if in the N − r es| U j as above. Again, Partition  optimal solution  of 1|h(1), N − r es| U¯ j all jobs are early. Any solution of 1|h(1), N − r es| U¯ j that is not optimal, leaves at least one job unprocessed. Thus, the approximation ratio of any nonoptimal solution isat most (n − 1)/n = 1 − 1/n. If an FPTAS existed for problem 1|h(1), N − r es| U¯ j , we would get a polyno1 mial (1 − ε) -approximation algorithm also for 2n < ε < n1 , which would yield an optimal solution (in polynomial time in 1ε ) for the instance above whenever the original instance of Partition has a solution in polynomial time in n. This is clearly impossible unless P = N P.  Now we will present a PTAS for nr with a fixed number k of non-availability intervals [ah , bh ], h = 1, . . . , k. The PTAS is based on guessing jobs in two classes. The first class contains jobs with large weights for which the due dates are seen as deadlines. The second class contains jobs with small weights for which the FPTAS is applied before finding a feasible solution. Given an instance I of nr , denote by OPT an optimal solution and by C ∗ the corresponding value of OPT, respectively. Set  = 2k/ε , and define S ∗ = { j ∈ J | w j ≤ C ∗ /}. Moreover, set Rh∗ = { j ∈ J | w j > C ∗ / and j is processed by OPT in interval Th = [bh−1 , ah ] }, h = 1, . . . , k + 1 and R∗ =

k+1 

Rh∗ .

h=1

For a given ε the PTAS is formulated in Algorithm 4.

123

J Comb Optim

Algorithm 4 PTAS 1. Guess the sets S ∗ , Rh∗ , h = 1, . . . , k + 1. 2. Define an instance I  from I with job set R ∗ ∪ S ∗ where every job j ∈ S ∗ has due date d j and every job j ∈ Rh∗ , h = 1, . . . , k + 1, has a deadline d¯ j = min{d j , ah }. Weights, processing times and non-availability intervals remain unchanged to I. 3. Transform with algorithm TA the instance I  into an instance I  without deadlines by fixing the starting times of the jobs with deadlines. If no feasible solution exists, STOP. The guessing was incorrect. 4. Get an (1−ε/2)-approximation algorithm for the problem r with instance I  by applying the FPTAS Aε . If there is any job of Rh∗ , h = 1, . . . , k + 1, which is not processed completely in interval Th , STOP. The guessing was incorrect. 5. Remove all crossover jobs. 6. Take the preempted job j with largest completion time C j . Process it nonpreemptively with the same completion time C j by moving all its parts to the right and moving all operations which are preempted by j to the left. Repeat this until all preemptions are resolved. 7. Output the obtained solution.

Theorem 3.2 The presented algorithm is a PTAS for problem nr with a fixed number of non-availability intervals k. ∗ correctly. That means, Proof Assume we have guessed the sets S ∗ , R1∗ , . . . , Rk+1 ∗ every job of Rh is processed in interval Th in the optimal solution and no job with weight greater than C ∗ / which is not in R ∗ is processed by the heuristic. We conclude that each due date from a job in R ∗ could be changed to the given deadline and the jobs greater than C ∗ / which are not in R ∗ could be removed from the instance without decreasing the objective function of the optimal solution for the new problem. Summarizing, we get for the optimal solution for instance I  , denoted by C ∗ (I  ), that C ∗ (I  ) ≥ C ∗ . The FPTAS Aε processes jobs with deadlines as late as possible. Thus, it cannot happen that the algorithm stops, when the guessing was correct. For a correct guessing the solution value obtained in Step 4 is at least (1 − ε/2)C ∗ (I  ) ≥ (1 − ε/2)C ∗ . Note that no job of R ∗ is preempted. Only jobs from S ∗ can be crossover jobs. Note that Aε is designed in a way such that there are at most k crossover jobs. Thus, by removing the crossover jobs, we loose at most kC ∗ / ≤ εC ∗ /2. In Step 6 the obtained solution is transformed into a feasible solution for problem r with instance I. The applied procedure guarantees that no job is processed later than in instance I  . Since no preempted job is a crossover job after Step 5, it follows that no additional crossover job is created while resolving the preemptions. Therefore, we have found a feasible solution for the original problem with an objective value n 

w j U¯ j ≥ (1 − ε/2)C ∗ − εC ∗ /2 = (1 − ε)C ∗ .

j=1

It remains to estimate the running time of the algorithm. Guessing S ∗ can be done in linear time after sorting the jobs according to their weights. Every set Rh∗ contains at most  − 1 elements. Thus, for guessing a set Rh∗ correctly there are at most O(n −1 ) ∗ correctly, multiplies the runpossibilities. In total, guessing all sets S ∗ , R1∗ , . . . , Rk+1 (k+1)(−1)+1 ning time of the algorithm by a factor of order O(n ). Since the running times of Steps 2 to 6 are clearly polynomial, the running time of our algorithm is

123

J Comb Optim 2

polynomial too. In total, the algorithm can be implemented in O( knε log W n O(k time.

2 /ε)

) 

4 Conclusion In this paper, we considered the maximization of the weighted number of early jobs on a single machine with non-availability constraints in its resumable and its nonresumable versions. Since the minimization problems are not approximable, we have chosen the objective function as the weighted number of early jobs to be maximized. We presented a dynamic programming algorithm for the resumable version of the maximization problem along with an FPTAS even if the number of the nonavailability intervals is variable and a subset of jobs has deadlines instead of due dates. The FPTAS is very fast and it is obtained by converting the dynamic programming algorithm. For the non-resumable version we proved that the maximization problem cannot admit an FPTAS even if all due dates are equal and only one nonavailability interval occurs. Nevertheless, we showed in this case that the problem admits a PTAS for a constant number of non-availability intervals and arbitrary due dates. As a perspective of this research, we aim to consider the parallel-machine scheduling version. For parallel machines we have not only to decide which jobs to process but also to select the machine to which a job is assigned. Since the problem on parallel machines is already NP-hard for two machines and without nonavailability intervals, a research on this topic seems a challenging task for the future. Another interesting open question is the problem whether a PTAS exists for nr also in the case that the number of non-availability intervals is part of the input. Acknowledgments 25086PL).

This work has been supported by Programme PHC AMADEUS 2012 (Project No.

References Gens GV, Levner EV (1978) Approximation algorithms for certain universal problems in scheduling theory. Eng Cybern 16:31–36 Gens GV, Levner EV (1981) Fast approximation algorithms for job sequencing with deadlines. Discrete Appl Math 3:313–318 Kacem I, Kellerer H (2011) Fast approximation algorithms to minimize a special weighted flow-time criterion on a single machine with a non-availability interval and release dates. J Sched 14:257–265 Kellerer H, Strusevich VA (2006) A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date. Theoret Comput Sci 369:230–238 Lawler EL, Moore JM (1969) A functional equation and its application to resource scheduling and sequencing problems. Manage Sci 16:77–84 Lee C-Y (1996) Machine scheduling with an availability constraint. J Global Optim 9:363–382 Lee C-Y (2004) Machine scheduling with availability constraints. In: Leung JY-T (ed) Handbook of scheduling: algorithms, models and performance analysis. Chapman & Hall/CRC, London, pp 22-1–22-13 Ma Y, Chu C, Zuo C (2010) A survey of scheduling with deterministic machine availability constraints. Comput Ind Eng 58:199–211

123

J Comb Optim Pinedo M (2012) Scheduling: theory, algorithms and systems, 4th edn. Springer, New York Potts CN, van Wassenhove LN (1992) Approximation algorithms for scheduling a single machine to minimize total late work. Oper Res Lett 11:261–266 Sahni S (1976) Algorithms for scheduling independent tasks. J Assoc Comput Mach 23:116–127 Sahni S (1977) General techniques for combinatorial approximation. Oper Res 25:920–936 Schmidt G (2000) Scheduling with limited machine availability. Eur J Oper Res 121:1–15

123