A Branch And Bound To Minimize The Number Of Late Jobs On A Single Machine With Release Time Constraints

European Journal of Operational Research 144 (2003) 1–11 www.elsevier.com/locate/dsw

Discrete Optimization

A branch and bound to minimize the number of late jobs on a single machine with release time constraints Philippe Baptiste a, Laurent Peridy b

b,*

, Eric Pinson

b

a CNRS, UMR 6599 H E U D I A S Y C , Universit
e de Technologie de Compi egne, F-60200 Compi egne, France Institut de Mathematiques Appliquees, Universite Catholique de l’Ouest, 44, rue Rabelais, B.P. 808, F-49008 Angers Cedex 01, France

Received 23 October 2000; accepted 23 October 2001

Abstract P This paper presents a branch and bound algorithm for the single machine scheduling problem 1jri j Ui where the objective function is to minimize the number of late jobs. Lower bounds based on a Lagrangian relaxation and no reductions to polynomially solvable cases are proposed. Efficient elimination rules together with strong dominance relations are also used to reduce the search space. A branch and bound exploiting these techniques solves to optimality instances with up to 200 jobs, improving drastically the size of problems that could be solved by exact methods up to now.
2002 Elsevier Science B.V. All rights reserved. Keywords: Single machine scheduling; Number of late jobs; Branch and bound; Dominance properties; Elimination rules

1. Introduction P In the scheduling problem 1jri j Ui , a set I of n jobs f1; . . . ; ng has to be processed without preemption a single machine. Each job i is characterized by a release date ri , a processing time pi and a due-date di (all data being integer). A job is ‘‘ontime’’ ðUi ¼ 0Þ if it is processed between ri and di . Otherwise, it is said to be ‘‘tardy’’ or ‘‘late’’ ðUi ¼ 1Þ. The objective isP to minimize the number of tardy jobs, NTJðIÞ ¼ i2I Ui . In the sequel, Di

*

Corresponding author. Tel.: +33-241-816713; fax: +33-241816700. E-mail address: [email protected] (L. Peridy).

denotes the time window of job i, that is to say the time interval in which i must execute if it is on-time (initially Di ¼ ½ri ; di ). With arbitrary release dates, the problem is NPHard in the strong sense [26]. However, many special cases and/or relaxations of the problem are polynomially solvable. P • With equal release dates, the problem 1jj Ui is polynomially solvable with Oðn log nÞ time complexity [30]. • Lawler [24] has proposed an Oðn5 Þ dynamic programming P algorithm for the preemptive case 1jri ; pmtnj Ui . Note that an enhanced Oðn4 Þ version of this algorithm is described in [2]. • Kise et al. [23] have shown that when release dates and due-dates are similarly ordered

0377-2217/03/$ - see front matter
2002 Elsevier Science B.V. All rights reserved. PII: S 0 3 7 7 - 2 2 1 7 ( 0 1 ) 0 0 3 5 3 - 8

2

P. Baptiste et al. / European Journal of Operational Research 144 (2003) 1–11

(8i; j 2 I, ri 6 rj ) di 6 dj ), the problem is also polynomially solvable, and Lawler [25] has proposed a Oðn log nÞ algorithm for this case. • Another Oðn log nÞ algorithm is presented in [25] for the preemptive nested case, that is to say the case where jobs are nested ð8i; j 2 I, ðri 6 rj ^ dj 6 di Þ _ ðrj 6 ri ^ di 6 dj ÞÞ and preemption is allowed. • Carlier [9,11] has proven that when processing P times are equal, the problem 1jpi ¼ p; ri j Ui can be solved in Oðn3 log nÞ. Extensions to the weighted case are also presented in [3].

The paper is organized as follows. Several dominance properties are stated in Section 2. New efficient lower bounds of the total number of late jobs proposed in Sections 3 and 4 describes new techniques to adjust jobs time-windows and to detect whether some jobs have to be late or ontime. The branching scheme is described in Section 5 and computational results are presented in Section 6. Finally, we draw some conclusions in Section 7.

To the best of our knowledge, few specific lower bounds have been designed for this problem. Dauzere-P
eres [16] has proposed a lower bound based on a Mixed Integer Program formulation. Computational results on instances with up to 20 jobs are reported. In the same paper, a heuristic based on a modification of Jackson’s algorithm [22] is presented. In [17], Dauzere-P
eres and Sevaux proposed an efficient lower bound that has been implemented in a branch and bound method. At the same time, Baptiste et al. [5] proposed a set of constraint propagation techniques and of dominance rules for this problem. In both cases, computational results show that instances with up to 120 jobs can be solved. In this paper, we present a branch and bound algorithm that has been successfully tested on instances with up to 200 jobs. In order to simplify the presentation, we denote by

The properties presented in this section allow us (1) to decompose the problem into independent sub-problems, (2) to add some precedence constraints between jobs and (3) to determine that some jobs are on-time.

• L, the set of jobs that are known to be late, • T, the set of that are known to be on-time, • F, the set of ‘‘Free’’ jobs, i.e., F ¼ I  ðT [ LÞ. Moreover, for any set of jobs B; rðBÞ; dðBÞ and pðBÞ stand for the release date, the due-date and the processing time of B: rðBÞ ¼ min ri ; i2B

dðBÞ ¼ max di ; i2B

pðBÞ ¼

X i2B

pi :

2. Dominance properties

2.1. Problem decomposition There are some situation where the problem can be split into independent sub-problems. Proposition 1. Let t be a time instant such that 8i 2 I  L either di 6 t or ri P t: NTJðIÞ ¼ jLj þ NTJðfi 2 I  Ljdi 6 tgÞ þ NTJðfi 2 I  Ljri P tgÞ: Proof. Obvious because the two subsets of jobs do not interact.  All possible decompositions according to Proposition 1 are computed by Algorithm 1. It runs in linear time once an initial sort on ri and di values is performed. Hence it runs in Oðn log nÞ. 2.2. Precedence constraints Given two jobs i and j, we note i ! j if and only if i is processed before j in any solution where both jobs are on-time. Such constraints can have a large impact on time-windows of jobs (see Section 4.2). Hence they contribute to the reduction of the search space.

P. Baptiste et al. / European Journal of Operational Research 144 (2003) 1–11

Algorithm 1 (Problem decomposition). Let K ¼ fri j i 2 I  Lg [ fdi j i 2 I  Lg sorted in increasing order d 0; p 1; Ip ; for i 1 to 2n do if K½i corresponds to a release date then d d þ1 Let k be the job whose release date is K½i Ip Ip [ fkg else {K½i is a due-date} d d 1 if d ¼ 0 then {Ip is an independent sub-problem} p pþ1 Ip ; end if end if end for Proposition 2. For any jobs i; j 2 T [ F such that ri < rj and di < dj , if 8k 2 T [ F  fi; jg, rk P di or dk 6 rj , then i ! j. Proof. Notice that if i starts between ri and rj , or if j is completed between di and dj , then we have i ! j. Now assume that i and j start after rj and are completed before di . Since no job starts or is completed in ½rj ; di , we can impose that i ! j.  By scanning the jobs in increasing order of their due-dates, we can compute all the disjunctions complying with Proposition 2 in Oðn2 Þ.

3

Proof. Let S be an optimal schedule such that the first index i, for which there is a job j that violates the condition of Proposition 3 is maximum. Assume that i is late and that j is on-time. Let t be the starting time of j. We build a new schedule obtained by ‘‘exchanging’’ i and j as follows: j is removed and i starts at maxðri ; tÞ. The completion time of i is maxðri þ pi ; t þ pi Þ and it is smaller than the previous completion time of j (so there is no overlapping in time with other jobs). Moreover t þ pj 6 dj ) t þ pi 6 dj  pj þ pi 6 di so the completion time of i is lower than or equal to di , i.e., it is on-time. Now, suppose that, on the new schedule, there is a late job k such that k < i and that together with i it violates Proposition 3. Since k was also late on the initial schedule, it was also violating the proposition with j. This contradicts the choice of i. Consequently, k > i which in turn contradicts our hypothesis on the choice of the initial schedule.  Due to elimination rules and/or dominance rules, release dates and due-dates will be tightened throughout the search for an optimal schedule. A careful examination of Proposition 3 shows that the most efficient dominance rule is obtained when ri and di are kept as the initial values of the release date and of the due-date of i. On the contrary, it is worth to consider the tightened values of rj and dj . The following proposition is a straight application of Proposition 3. When two jobs cannot be scheduled both on-time, the ‘‘less interesting’’ job is late.

2.3. Small jobs vs. large jobs To minimize the number of tardy jobs, it seems reasonable to ‘‘schedule on-time as many small jobs as possible’’. Proposition 3 provides a rationale for this claim. In the following we assume that jobs are scored in non-decreasing order of their processing times, i.e., p1 6 p2 6    6 pn . Proposition 3 (Dominance property). There is an optimal schedule where, for any pair of jobs i; j such that (1) i < j, (2) rj þ pj P ri þ pi and (3) dj  pj 6 di  pi , job i is on-time if j is on-time.

Proposition 4. Let i and j be two jobs in F verifying Proposition 3. If ðri þ pi þ pj > dj Þ and ðrj þ pj þ pi > di Þ then Uj ¼ 1. Proof. The conditions ðri þ pi þ pj > dj Þ and ðrj þ pj þ pi > di Þ imply that at least one job is scheduled late. Because of the dominance property (cf. Proposition 3), j is late.  Another way to fix the status of a set of jobs is to prove that we can schedule all of them on-time without any interaction with the other jobs.

4

P. Baptiste et al. / European Journal of Operational Research 144 (2003) 1–11

Proposition 5. Let ½t1 ; t2 be a time interval and Iðt1 ; t2 Þ ¼ fi 2 T [ F j ri 6 t2 _ di P t1 g. If all jobs of Iðt1 ; t2 Þ can be scheduled on-time in ½t1 ; t2 then there exists an optimal solution where all jobs of Iðt1 ; t2 Þ are processed on-time in the time interval ½t1 ; t2 . Proof. Given the definition of Iðt1 ; t2 Þ, the set I can be decomposed in three subsets Ib , Iðt1 ; t2 Þ and Ia where Ib ¼ fi 2 I j di < t1 g, Ia ¼ fi 2 I j ri > t2 g. Obviously, the jobs in Ib are completed before t1 and the jobs in Ia are scheduled after t2 . So, a schedule of the jobs of Iðt1 ; t2 Þ that starts at h1 P t1 and is completed at h2 6 t2 has no interaction with the jobs in I  Iðt1 ; t2 Þ. Of course, it follows that all the jobs in Iðt1 ; t2 Þ are scheduled on-time. 

constraint. Unfortunately, the best algorithm that solvesPthe preemptive scheduling problem 1jri ; pmtnj Ui is running in Oðn4 Þ [2] which is too time consuming to be incorporated in a branch and bound. In this section, we propose new lower bounds with lower time complexities. The first one (Section 3.1) is based on a Lagrangian relaxation. For the other ones (Section 3.2), release and duedates are adjusted in order to match polynomially solvable case of the problem at hand. To simplify the presentation, we remove jobs that are known to be late (i.e., those in L) from the instance. Of course, the value jLj is added to the lower bound computed on the modified instance. 3.1. Flow based lower bound

Proposition 3 also allows us to create holes in the time-windows of jobs. Consider a job i 2 L and a job j 2 T [ F with i < j and ri þ pi < di  pi . Let S be an optimal dominant schedule where j is ontime. We can tighten the release date and the duedate of j, respectively, to its start time tj and its completion time Cj on S. According to the dominance property (cf. Proposition 3), we cannot have tj þ pj ¼ Cj P ri þ pi and Cj  pj ¼ tj 6 di  pi . So the interval ½ri þ pi ; di  pi can be removed from the time-window Dj . To conclude, we propose an elimination rule that exploits the holes performed on the timewindows of jobs. Proposition 6. Let i 2 F and let us assume that there exists a time interval ½t1 ; t2 with t2  t1 P pi and ½t1 ; t2  ½ri ; di such that, due to the dominance property (cf. Proposition 3) applied with job i late, we have 8j 2 I  fig; Dj \ ½t1 ; t2 ¼ ;; hence i is on-time. Proof. The claimed conditions imply that if i is late, there is a time interval greater than pi unused by other jobs due to the dominance property (cf. Proposition 3). Therefore, it would have been possible to schedule i on-time. 

This lower bound is based on the classical flow formulation proposed for the Pmjri jLmax scheduling problem. Let S denote a partitioning of the interval ½mini ri ; maxi di into s non-overlapping time slots S1 ; S2 ; . . . ; Ss with ranges l1 ; l2 ; . . . ; ls . Bounds of each time slot Su are either a release date or a due-date of some job ðs 6 2n  1Þ. In addition, a complementary time slot Ssþ1 is created in order to receive all pieces of jobs that are not processed ontime. For each job i, let Cþ i be the set of time slots where i can execute. If i 2 F ; Cþ i ¼ fSk j Sk  ½ri ; di g [ fSsþ1 g, otherwise Cþ ¼ fS k j Sk  ½ri ; di g. i Conversely, let C be the set of jobs that k can execute in Sk : 8k 6 s; C ¼ fijS k  ½ri ; di g and k C ¼ F . sþ1 We introduce the decision variables xik (1 6 i 6 n 1 6 k 6 s þ 1) that represent the amount of job i assigned to the time interval Sk . The following P Mixed Integer Problem solves the 1jri ; pmtnj Ui problem. X ðPÞ min Ui i2F

8i 2 F ;

X

xik P ð1  Ui Þpi ;

ð1Þ

k2Cþ fSsþ1 g i

3. Lower bounds A usual way to obtain lower bounds of scheduling problems is to relax the non-preemption

8k 2 f1; . . . ; sg; 8i 2 T ;

X k2Cþ i

X

xik 6 lk ;

ð2Þ

i2C k

xik ¼ pi ;

ð3Þ

P. Baptiste et al. / European Journal of Operational Research 144 (2003) 1–11

8i 2 T [ F ; 8k 2 f1; . . . ; s þ 1g;

xik P 0; ð4Þ

8i 2 F ;

Ui 2 f0; 1g:

ð5Þ

We use a Lagrangian relaxation for designing a lower bound of (P). By dualizing the set of constraints (1), we obtain the Lagrangian function Lðx; U ; pÞ defined as follows: 0 1 X X X Lðx;U ;pÞ¼ Ui þ pi @ð1Ui Þpi  xik A i2F

¼

X

X

X

pi xik þ

i2F k2Cþ fSsþ1 g i

X

pi pi ;

i2F

where p is the non-negative vector of Lagrangian multipliers. The associated dual function is then LðpÞ ¼ minðx;U Þ2Z Lðx; U ; pÞ, where Z is the domain defined by constraints (2)–(5) of ðPÞ. To get an efficient algorithm, we need a fast procedure to compute LðpÞ. LðpÞ min

X

ð1  pi pi ÞUi 

i2F

8k 2 f1; .. . ;sg; 8i 2 T ;

X

X

X

X

pi xik þ

i2F k2Cþ fSsþ1 g i

X

Ui ¼ 1 if and only if 1  pi pi 6 0, Ui ¼ 0 otherwise. • The second sub-problem ðL1 ðpÞÞ is based on variables xik . X X pi xik L1 ðpÞ min i2F k2Cþ fSsþ1 g i

8k 2 f1; . . . ; sg; 8i 2 T ;

X

X

pi xik 6 lk ;

i2C k

xik ¼ pi ;

k2Cþ i

8i 2 T [ F ; 8k 2 f1; . . . ; s þ 1g; xik P 0:

ð1pi pi ÞUi

i2F



k2Cþ fSsþ1 g i

i2F

5

pi pi

i2F

One can recognize a min-cost max-flow problem where pi is the cost of scheduling one unit of i 2 F in S1 ; . . . ; Ss . So L1 ðpÞ can be efficiently computed with, for instance, the Capacity Scaling Algorithm [1]. So LðpÞ can be computed in a short time for any distribution of Lagrangian multipliers p. In our implementation, adjustments of Lagrangian multipliers are performed by using a sub-gradient method as described for instance in [29].

xik 6 lk ;

i2C k

3.2. Relaxing release dates and/or due-dates to obtain polynomially solvable cases

xik ¼ pi ;

k2Cþ i

8i 2 T [ F ; 8k 2 f1; . .. ; s þ 1g; xik P 0; 8i 2 F ; Ui 2 f0; 1g:

Clearly, the computation of LðpÞ for any distribution of Lagrangian multipliers can be decomposed into two independent sub-problems: X LðpÞ ¼ L0 ðpÞ þ L1 ðpÞ þ pi pi ; i2F

where • The first sub-problem ðL0 ðpÞÞ is based on variables U1 ; . . . ; Un . X L0 ðpÞ ¼ min ð1  pi piÞUi i2F

8i 2 F ; Ui 2 f0; 1g which can be trivially solved in time OðnÞ by applying the following rule:

Another lower bound can be reached by relaxing release dates and/or due-dates in such a way that the resulting problem is polynomially solvable. Our goal is to reach either a ‘‘nested’’ problem or an instance satisfying the Kise, Ibaraki and Mine conditions. Clearly, the main issue is how to relax the initial data in a pertinent way that match this goal. 3.2.1. Lower bound based on the nested case In this section, we show how to decrease release dates in such a way that jobs become nested, i.e., their time-windows are either included or do not overlap in time. This basic idea relies on the computation of a particular preemptive schedule obtained by applying the earliest due-date (EDD) priority dispatching rule. Given this EDD schedule, we can introduce the notion of blocks.

6

P. Baptiste et al. / European Journal of Operational Research 144 (2003) 1–11

Definition 1. The block Bc associated with any job c in a preemptive EDD scheduled is the minimal set of jobs (for the inclusion) satisfying [13]: • c 2 Bc , • 8i 2 Bc ; di 6 dc , • rðBc Þ þ pðBc Þ ¼ Cc , where Cc denotes the completion time of job c in the EDD schedule. Blocks are of prime interest for our purpose because of the following property. Proposition 7. In the preemptive EDD schedule, blocks are either included or do not overlap in time. Proof. Let us suppose that there are two jobs i and j such that Bi \ Bj 6¼ ; and let us assume that di < dj . From these two assumptions we have i 2 Bi \ Bj . Since Bi is the minimal set satisfying Definition 1, there is no block that contains job i and that starts after time rðBj Þ. So, there exists a job from Bi \ Bj starting before time instant rðBj Þ, and Bj is not a block, which contradicts the assumptions.  Notice that, by construction of EDD schedule, 8i 2 I, ri P rðBi Þ. Hence, by adjusting the release date of each job i to the release date of its block rðBi Þ, we obtain a nested problem. As pointed out before, this problem is solved thanks to Lawler’s algorithm [25]. Because release date have been decreased, the resulting solution is a lower bound for the P 1jri j Ui scheduling problem. Since the EDD preemptive schedule can be computed in Oðn log nÞ, the proposed lower bound can be processed in Oðn log nÞ time. Notice that symmetrically, we can define a lower bound based on the adjustments of job due-dates. 3.2.2. Lower bound based on Mine, Ibaraki and Kise algorithm Now, following [18], we adjust data on the problem in order to match the Kise, Mine and Ibaraki conditions (8i; j 2 I, ri 6 rj ) di 6 dj ). Algorithm 2 formalizes this idea.

Algorithm 2 (Increasing due-dates to match conditions of [23]). Sort jobs in non-decreasing order of release dates dmax 0 for i 1 to n do if di < dmax then di dmax else dmax di end if end for Apply Kise, Ibaraki and Mine algorithm [23] Proposition P 8. Algorithm 2 computes a lower bound for 1jri j Ui in Oðn log nÞ time. Proof. Following the fact that Algorithm 2 increases due-dates, we clearly obtain a lower P bound of 1jri j Ui . Adjustments of the due-dates can be performed in Oðn log nÞ, and the complexity of Kise, Mine and Ibaraki algorithm is Oðn log nÞ.  Once more, we can symmetrically define a lower bound based on the adjustment of the release dates. Quite surprisingly, extensive computational experiments performed on these three lower bounds show that the two latter ones are very close in terms of quality even if the first one performs better. The adjustments based lower bounds are computed must faster than the first lower bound. Hence, it is not computed at each node of the search tree. We only use it at the root of the search tree and when the other lower bounds (computed at each node) are very close to (less than 2 units) the current upper bound (best known upper bound).

4. Elimination rules Elimination rules are of prime interest in branch and bound methods because they may drastically prune the search tree. Elimination rules are necessary conditions that any optimal schedule must

P. Baptiste et al. / European Journal of Operational Research 144 (2003) 1–11

fulfill, while dominance properties are conditions that do not discard all optimal schedules. We first focus on some well-known elimination rules, initially designed for 1jri jLmax . They can be adapted to our problem. Second, we propose a collection of specific time-windows adjustments.

7

Proposition 11. For any job i 2 T and for any job j 2 T [ F,  rj ¼ maxðrj ; ri þ pi Þ; ði ! jÞ ) di ¼ minðdi ; dj  pj Þ: Proof. Obvious.



4.1. Immediate selections If we focus on the set of on-time jobs T, we have a 1jri jLmax sub-problem for which many elimination rules have been proposed [4,6,7,12–15,20, 21,27,28,31,32]. In this section, we show that immediate selection on disjunction and immediate selection on ascendant/descendant sets (also known as edge-finding), can be transposed to our problem. Proposition 9. For any pair of on-time jobs i; j such that rj þ pj þ pi > di we have i ! j. Proof. Direct application of immediate selections on disjunctions [8,14].  Proposition 10. 8c 2 T [ F and 8K  T  fcg, • if minðrc ; rðKÞÞ þ pðKÞ þ pc > dðKÞ then ð8j 2 K, j ! cÞ, • if rðKÞ þ pc þ pðKÞ > maxðdc ; dðKÞÞ then (8j 2 K, c ! j).

Proof. Direct application of immediate selections on ascendant/descendant sets [13,14].  According to the algorithm proposed in [14], immediate selections related to Propositions 9 and 10 can be performed in Oðn log nÞ time. 4.2. Adjustments on jobs time-windows As shown in [14], immediate selections on disjunctions or ascendant/descendant sets lead to adjustments of jobs release and due dates. Of course, for such adjustments we only consider ontime jobs. In this section, we first recall adjustments induced by Propositions 9 and 10. Next, we propose new adjustments relying on the dominance property stated in Proposition 3.

In the sequel, we note K ! i iff ð8u 2 K; u ! iÞ. Proposition 12. For any job c 2 T [ F and for any subset K  T  fcg, ðK ! cÞ ) rc ¼ maxðrc ; rðKÞ þ pðKÞÞ; ðc ! KÞ ) dc ¼ minðdc ; dðKÞ  pðKÞÞ: Proof. Obvious.



Proposition 13. If Di is composed of a set of nonoverlapping intervals, the intervals whose sizes are not greater than pi can be removed. Proof. Indeed, job i cannot be processed without preemption in a time slot with a duration strictly smaller than its processing time.  So, we have a very simple propagation rule that removes the small intervals from the time-windows of jobs. Note that this rule may also have an impact on the release date of the considered job if the first interval of Di is removed.

5. Branching scheme In our branch and bound, we perform a tree search where at each node, lower bounds are computed and where dominance properties and elimination rules are applied. We refer to the last paragraph of Section 3 for the exact strategy used for the computation of lower bounds. Two types of branching decisions can be taken at each node: either a sequencing decision between on-time jobs (a job is scheduled before or after a set of jobs) or an on-time/late decision (chose a free job and put in on-time or late).

8

P. Baptiste et al. / European Journal of Operational Research 144 (2003) 1–11

To determine if a sequencing or an on-time/late decision is to be taken, we first schedule all on-time jobs according to the EDD sequence (free jobs and late jobs are not scheduled). • If the resulting schedule is feasible, we chose a ‘‘free’’ job u and we schedule it on-time (if there is no more free job then we have a solution). Upon backtracking, it will be scheduled late. The heuristic used to chose u is the following one. We first compute pmin ¼ mini2F pi , the smallest processing time among processing times of free jobs. We then select a free job u with the largest time-window among those of the jobs that have a processing time lower than 1:1pmin . This heuristic bets that it is a good decision to schedule on-time a job with a small processing time and a large time-window. • If the resulting schedule is not feasible we focus on the sequencing problem. We use the very efficient branching scheme of Carlier for the one-machine problem [10] that allows us to determine a critical job c and a critical set of jobs J such that either c is before all jobs of J or c is after all jobs of J. Note that after such a branching, time-windows of jobs are tightened and so, the EDD schedule computed at the next node is likely to differ from the initial one. The rationale behind this branching scheme is not obvious and we refer the reader to the early work of Carlier [10].

[5]. We pay attention to the following characteristics: • the distribution of the processing times; • the overall ‘‘load’’ of the machine, where the load is the ratio between the sum of the processing times of the jobs and (max di  min ri ); • the slack mi ¼ di  ri  pi of each job. So, the generation scheme is based on four parameters: the number of jobs n and the three statistical distributions followed by the release dates, the processing times and the slacks (given ri ; pi ; mi , the due-date can be immediately computed by di ¼ mi þ ri þ pi ). • Processing times are generated from an uniform distribution in [pmin ; pmax ]. • Release dates are generated from a normal distribution (0; r). • Slacks are generated from an uniform distribution in [0; mmax ]. Given these parameters and relying on the fact that most of the release dates are in [2r; 2r], the load is approximately equal to: nðpmin þ pmax Þ : 2ð4r þ pmax þ mmax Þ One instance has been generated for each combination of the parameters ðn; ðpmin ; pmax Þ; mmax ; loadÞ

The efficiency of our branching scheme comes from the interaction between on-time/late decisions and sequencing decisions. In practice, the EDD schedule is almost always optimal, i.e., if the EDD schedule is not feasible then most often there is no feasible schedule at all. In this case, we backtrack on the previous on-time/late node. Sometimes, some sequencing nodes have to be explored but in practice, most of the nodes of the search tree are on-time/late nodes.

6. Computational experiments Two set of instances have been tested. The first set of instances follows the generation scheme of

in the Cartesian product f80; . . . ; 200g  fð0; 100Þ; ð25; 75Þg  f50; 100; . . . ; 500g  f0:5; 0:8; 1:1; 1:4; 1:7; 2:0g: Table 1 reports the results obtained for different values of n, each line corresponding to 120 instances. The column ‘‘% solved problems’’ provides the percentage of instances that have been solved within one hour of CPU time on a PC Pentium III 450 MHz running windows NT. The column ‘‘Avg’’ reports the average of the CPU time in seconds (or of the total number of nodes) required to solve the instances of each set within the time limit. The second instance set has been generated by Dauzere-P
eres and Sevaux. They use two para-

P. Baptiste et al. / European Journal of Operational Research 144 (2003) 1–11

9

Table 1 Results obtained on the first set of instances n

pi range

% solved problems

# nodes avg

CPU avg

# open problems

80 80 100 100 120 120 140 140 160 160 180 180 200 200

½0; 100 ½25; 75 ½0; 100 ½25; 75 ½0; 100 ½25; 75 ½0; 100 ½25; 75 ½0; 100 ½25; 75 ½0; 100 ½25; 75 ½0; 100 ½25; 75

100 100 100 98.33 98.33 86.67 93.33 80 90 70 88.33 70 73.33 56.67

144 1327 629 492 677 201 646 600 490 588 797 808 1197 214

18 58 28 76 170 85 191 172 215 155 394 335 519 149

0 0 0 1 1 8 4 12 6 18 7 18 16 26

Table 2 Results obtained on the second set of instances n

% solved problems

# nodes avg

CPU avg

# open problems

80 100 120 140

100 98.12 98.75 94.37

38 75 70 79

21 82 145 212

0 3 2 9

meters K1 and K2 to characterize an instance. K1 is related to the release dates dispersion and K2 to the due-dates dispersion. Ten instances have been generated for each combinations of the parameters (K1 ; K2 ) in the Cartesian product f1; 5; 10; 20g  f1; 5; 10; 20g. Table 2 reports the results obtained for different values of n, each line corresponding to 160 instances. Table 1 shows that 86% of the generated instances of [5] are solved up to optimality. Moreover, it indicates that for each size of problems, the set of instances for which the processing times are generated in the interval ½25; 75 are harder to solve than the other set. This fact is probably due to the dominance property (cf. Proposition 3). It is less likely to be applied. Table 2 shows that 98% of the instances generated according to the Dauzere-P
eres and Sevaux scheme are solved up to optimality. These instances are somewhat ‘‘easier’’ to solve than those of the first set since for given size, there are more open instances in our set than in the one of Dauzere-P
eres and Sevaux (e.g., for n ¼ 140,

13.3% of the instances of the first set are open while 5.6% of the instances of the second set are open). We think that this is due to the fact that the time-windows in the second set are larger in average. In this case, dominance properties are very efficient and building an optimal solution is easier. Detailed experimental results can be found on the web site http://www.ima.uco.fr/personnes/zeb/ recherche/instances/latejobs. Tables 3 and 4 provide a comparison of the efficiency of our branch and bound with the Constraint Programming approach of Baptiste et al. [5] and with the latest version of the branch and bound method of Dauzere-P
eres and Sevaux [19]. In all cases, the search has been interrupted after one hour of CPU time. Different computers have been used (a PC 200 MHz in [5], a SUN SPARC 5 workstation in [19] and a PC 450 MHz in this experimental study). Hence, these results have to be taken with care. However it seems that our branch and bound performs very well as to the number of instances solved. It is never outperformed by the other techniques except for n ¼ 140

10

P. Baptiste et al. / European Journal of Operational Research 144 (2003) 1–11

Table 3 Comparison with other exact approaches on the first set of instances [5]

[19]

Our B&B

n

% solved

Avg CPU

% solved

Avg CPU

% solved

Avg CPU

80 100 120 140

96.7 90.0 84.2 72.5

117 274 538 1037

98.3 95.0 90.3 73.3

49 78 90 234

100.0 99.2 92.5 86.7

38 42 128 182

Table 4 Comparison with other exact approaches on the second set of instances [5]

[19]

Our B&B

n

% solved

Avg CPU

% solved

Avg CPU

% solved

Avg CPU

80 100 120 140

100.0 97.5 98.6 93.1

21 55 98 121

98.1 98.1 95.0 95.0

8 28 66 126

100.0 98.1 98.8 94.4

21 82 145 212

on the second set of instances where the branch and bound of Dauzere-P
eres and Sevaux is able to solve one more instance than our method. Most of the time, we have significantly improved the number of instances solved.

paper. The authors are also grateful to Marc Sevaux who kindly provided Tables 3 and 4 of the experimental study.

References 7. Conclusion In this paper, we have presented a branch and bound algorithm for the single machine scheduling problem where the objective function is to minimize the number of late jobs. Lower bounds based on Lagrangian relaxation and on polynomially solvable cases after appropriate adjustments of release and due-dates have been proposed. New elimination rules using a dominance property and immediate selections have been presented. A branch and bound exploiting these different tools has been used to solve to optimality problems with up to 200 jobs, improving drastically the size of problems that could be solved by exact methods up to now.

Acknowledgements The authors would like to thank the referees for their helpful comments on an earlier version of this

[1] R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows, Prentice-Hall, Englewood Cliffs, NJ, 1993. [2] Ph. Baptiste, An Oðn4 Þ algorithm for preemptive scheduling of a single machine to minimize the number of late jobs, Operations Research Letters 24 (1999). [3] Ph. Baptiste, Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine when processing times are equal, Journal of Scheduling 2 (1999) 245–252. [4] Ph. Baptiste, C. Le Pape, W. Nuijten, Constraint-based scheduling: Applying constraint programming to scheduling problems, in: International Series in Operations Research and Management Science, vol. 39, Kluwer Academic Publishers, Dordrecht, 2001. [5] Ph. Baptiste, C. Le Pape, L. Peridy, Global constraints for partials csps: a case study of resource and due date constraints, in: Proceedings of the Fourth International Conference on Principles and Practice of Constraint Programming, Lecture Notes in Computer Science, Springer, Berlin, 1998. [6] P. Brucker, B. Jurisch, A. Kr€amer, The job-shop problem and immediate selection, Annals of Operations Research 50 (1994). [7] P. Brucker, B. Jurisch, B. Sievers, A branch and bound algorithm for the job-shop scheduling problem, Discrete Applied Mathematics 49 (1994) 107–127.

P. Baptiste et al. / European Journal of Operational Research 144 (2003) 1–11 [8] J. Carlier, Ordonnancements a machines disjunctives, RAIRO 12 (4) (1975). [9] J. Carlier, Probleme a une machine et algorithmes polyn^ omiaux, Questio 5 (4) (1981). [10] J. Carlier, The one machine problem, European Journal of Operational Research 11 (1982) 42–47. [11] J. Carlier, Problemes d’ordonnancements a contraintesde
tat, Ph.D. ressources: Algorithmes et complexit
e, These d’E Thesis, University of Paris VI, 1984. [12] J. Carlier, E. Pinson, An algorithm for solving the job-shop problem, Management Science 35 (2) (1989) 165–176. [13] J. Carlier, E. Pinson, A practical use of jackson’s preemptive schedule for solving the job-shop problem, Annals of Operations Research 26 (1991) 269–287. [14] J. Carlier, E. Pinson, Adjustments of heads and tails for the job-shop problem, European Journal of Operational Research 78 (1994) 146–161. [15] Y. Caseau, F. Laburthe, Disjunctive scheduling with task intervals, Technical Report, LIENS Technical Report 95
coleNormale Sup
erieure Paris, France, 1995. 25, E [16] S. Dauzere-P
eres, Minimizing late jobs in the general one machine scheduling problem, European Journal of Operational Research 81 (1995) 134–142. [17] S. Dauzere-P
eres, M. Sevaux, An branch and bound method to minimize the number of late jobs in single machine, Technical Report 98/5/AUTO, Ecole des Mines de Nantes, 1998. [18] S. Dauzere-P
eres, M. Sevaux, A efficient formulation for minimizing the number of late jobs on a single machine, Technical Report 98/9/AUTO, Ecole des Mines de Nantes, 1998. [19] S. Dauzere-P
eres, M. Sevaux, An exact method to minimize the number of tardy jobs on a single machine, Technical Report 99/6/AUTO, Ecole des Mines de Nantes, SDP, MS, 1999. [20] G. Dewess, Ein existenzsatz f€ ur packungs probleme mit konsequenzen f€ ur die berechnung optimaler maschinenbelegungspl€ ane, Technical report, Universit€at Leipzig, 1991.

11

[21] J. Erschler, F. Roubellat, J.P. Vernhes, Characterizing the set of feasible sequences for n jobs to be carried out on a single machine, European Journal of Operational Research 4 (1980) 189–194. [22] J.R. Jackson, Scheduling a production line to minimize maximum tardiness, Technical Report 43, University of California, Los Angeles, 1955. [23] H. Kise, T. Ibaraki, H. Mine, A solvable case of the one machine scheduling problem with ready and due times, Operations Research 26 (1) (1978) 121–126. [24] E.L. Lawler, A dynamic programming algorithm for the preemptive scheduling of a single machine to minimize the number of late jobs, Annals of Operations Research (26) (1990) 125–133. [25] E.L. Lawler, Knapsack-like scheduling problems, the moore-hodgson algorithm and the ‘‘tower of sets’’ property, Mathematical Computer Modelling 20 (2) (1994) 91–106. [26] J.K. Lenstra, A.H.G. Rinnooy Kan, P. Brucker, Complexity of machine scheduling problems, Annals of Discrete Mathematics 1 (1977) 343–362. [27] P. Lopez, Approche
energ
etique pour l’ordonnancement de t^aches sous contraintes de temps et de ressources, Ph.D. Thesis, Universit
e Paul Sabatier, 1991. [28] P. Martin, D.B. Shmoys, A new approach to computing optimal schedules for the job-shop scheduling problem, in: Proceedings of the fifth Conference on Integer Programming and Combinatorial Optimization, 1996. [29] M. Minoux, Mathematical Programming, Wiley, New York, 1986. [30] J.M. Moore, An n job, one machine sequencing algorithm for minimizing the number of late jobs, Management Science 15 (1) (1968) 102–109. [31] L. Peridy, Le probleme de Job-Shop: arbitrages et ajustements, Ph.D. Thesis, University of Technology of Compiegne, 1996. [32] D. Rivreau, Problemes d’ordonnancement disjonctifs: regles d’
elimination et bornes inf
erieures, Ph.D. Thesis, University of Technology of Compiegne, 1999.