Annals of Operations Research 83(1998)271–287

271

Decomposition in single-machine scheduling Wlodzimierz Szwarc School of Business Administration, University of Wisconsin-Milwaukee, P.O. Box 742, Milwaukee, WI 53201, USA

This paper discusses the recent research on decomposition techniques in single-machine scheduling. A variety of orderings between adjacent and nonadjacent jobs in an optimal scheduling are presented. A list of decomposition rules is given that enable one to solve large size instances of six single-machine models. A partition technique is also developed to determine the optimal completion times of a general earliness-tardiness model for a given arrangement of jobs.

1.

Introduction

This paper discusses recent research on the decomposition techniques to solve a variety of single-machine n job scheduling models. By decomposition, we mean a partition of the jobset into subsets called blocks or clusters that simplifies the search for an optimal schedule which is a vector of completion times of each job. For models in which processing starts at a given time and no idle time between jobs is allowed, the optimal schedule is represented by an n-job sequence which uniquely defines the completion times of the jobs. The theoretical framework linking most of these models is based on properties of orderings between adjacent jobs. The orderings between nonadjacent jobs for some of these models are also discussed. Several types of transitivity properties of these orderings are presented that play a crucial role in the decomposition process. A list of decomposition rules that split the problem into separate subproblems is presented. It is also useful to execute these rules for every node of the branch and bound procedure prior to calculating the lower bound. The node is terminated once the set of unscheduled job is completely decomposed. The paper also establishes three properties for two particular models. A special tardiness model is discussed, where the precedence relations remain in force for its earliness-tardiness version where idle times between jobs are permitted. Finally, a partition technique is described that is the basis of a very fast algorithm to determine the optimal schedule of the general earliness-tardiness problem for a given arrangement of jobs. © J.C. Baltzer AG, Science Publishers

W. Szwarc y Decomposition in single-machine scheduling

272

2.

Adjacent precedence matrix We adopt the following notation:

I S pk Ck f (S)

: : : : :

the set of n jobs 1, 2,…, n, sequence of n jobs, processing time of job k, k ∈I, completion time of job k, objective function (to be minimized) for sequence S.

In this paper we assume that n

f (S) =

∑ fk (Ck ).

(1)

k=1

First, consider a single-machine n-job model where the processing starts at time t0 ≥ 0 and continues uninterrupted. Then each schedule is defined by a sequence of n jobs. To study the orderings between adjacent jobs, select two schedules S1 = σ ij π and S2 = σ jiπ, where σ and π are disjoint subsequences of the remaining n – 2 jobs. Let t = ∑ k ∈σ pk . According to (1), the cost of interchanging i and j, ∆ij (t) = f (S2 ) − f (S1 ),

(2)

is a function that depends on t, i, and j exclusively. From now on we will deal with functions ∆ ij (t) that change their sign at most once. Let tij be the critical value of t where ∆ ij (t) changes its sign. Then ∆ ij (tij ) = 0. We consider models where it is possible to index the jobs such that, for each i < j, the following conditions hold: ∆ ij (t) ≤ 0, for t < tij , (3) ∆ ij (t) ≥ 0, for t ≥ tij . Suppose jobs i and j, i < j, are adjacent in an optimal schedule. Due to (2) and (3), job i precedes j for t = t1 if ∆ ij (t1) ≥ 0. Otherwise j → i for t = t1. Number tij is the critical value of t when the ordering changes direction. An ordering that does not change direction is called unconditional and symbolized by i → j or j → i without specifying t. This happens when either ∆ ij (t) ≥ 0 or ∆ij (t) ≤ 0 for min t(i, j) ≤ t ≤ max t(i, j),

(4)

where min t(i, j) and max t(i, j) are the earliest and latest start times of processing adjacent jobs i and j. Initially, min t(i, j) = t0 and max t(i, j) = t0 + ∑nk =1 pk − pi − pj . This unconditional ordering of pair i, j is called local since it depends on the domain [min t(i, j), max t(i, j)] = Dij .

W. Szwarc y Decomposition in single-machine scheduling

273

Condition (3) implies the following: Adjacent ordering rule (1)

If tij ≤ min t(i, j), then i → j,

(2)

if tij ≥ max t(i, j), then j → i,

(3)

if min t(i, j) < tij < max t(i, j), then i → j for t ≥ tij and j → i for t < tij .

Define an upper triangular precedence matrix T for 1 ≤ i < j ≤ n by placing the following symbols in cell (i, j): “–” for case 1 (of the adjacent ordering rule), “+” for case 2, and “ tij ” for case 3. We will later deal with another type of unconditional orderings, called global, when the inequalities of (4) hold for every t ≥ 0. Unconditional orderings are transitive if for every i1, i 2, i3 ∈I i1 → i2 ∀t and i2 → i3 ∀t imply i1 → i3 ∀t,

(5)

where ∀t is associated with a respective domain of t. Conditional orderings are transitive if for every i1, i 2, i 3 ∈I and t1 i1 → i2 for t = t1 and i2 → i3 for t = t1 imply i1 → i3 for t = t1 . 3.

(6)

Problem decomposition

Consider the precedence matrix T. We will explore whether the problem is decomposable if some or all the entries of T are “+” or “–”. Consider two sets α and β, where β = I – α. The following obvious property based on the interchange argument holds: Property 1. α, β is an optimal block schedule if u → υ unconditionally for every u ∈α and υ ∈β. Property 1 is the basis for the following specific rules: Rule 1. α, β is an optimal block schedule if for some α = {1, 2,…, m} and β = {m + 1,…, n} the entries (i, j) of matrix T are “–” for each i ∈α and j ∉α. m should be chosen as small as possible. Rule 2 . α, β is an optimal block schedule if the entries (i, j) are “–” for each i ∈α, j ∉α and “+” for each i ∉α and j ∈α. Rule 2 is a generalization of rule 1. For α = {k} or β = {k}, rule 2 reduces to: Rule 3 . (a) Job k is first in an optimal schedule if all entries of T are “+” in column k and “–” in row k. (b) Job k is last in an optimal schedule if all entries of T are “–” in column k and “+” in row k.

274

W. Szwarc y Decomposition in single-machine scheduling

Suppose each entry in row and column k of T is “+” or “–”. Let α and β = I – α – {k} be sets of jobs that unconditionally precede and follow, respectively, job k. Introduce a rule, called split rule, as follows: Split rule (rule 4). α, k, β is an optimal block sequence. It is obvious that rule 4 is applicable if for each r ∈α and s ∈β, r → s unconditionally. The partition of jobset I into α, β or α, k, β affects the values of max t(i, j), for i, j ∈α and min t(i, j), for i, j ∈β. Their updated values for, say, the two block partition α, β are max t(i, j) = t0 + ∑k ∈α pk – pi – pj and min t(i, j) = t0 + ∑k ∈α pk , respectively. Then some conditional orderings become unconditional (local within a block) once cases 1 and 2 of the adjacent ordering rule hold for the updated min t(i, j) and max t(i, j). We outline the following: Partition procedure. Decompose the original jobset I into blocks α, β or α, k, β by using one of the decomposition rules. Update min t(i, j) and max t(i, j) within each block. Create new “–” and “+” entries within each block for cases 1 and 2 of the adjacent ordering rule. Repeat the procedure for each block until no further decomposition is possible. Since the range of the domain Dij narrows within each of the partitioned blocks α and β, the “tij ” entries of TB are more likely to be converted into “+” or “–” than for the original domain. Remark 1. Let TB be the precedence matrix of an arbitrary block B (B , I) that starts at t = tB . If tB ≥ max (i, j) ∈B tij , then all “tij ” entries of TB are “+” or “–”. Notice that rules 1, 2 and 3 do not depend on the transitivity of local orderings. Still, transitivity plays a crucial role for the following case. Suppose each entry of T (or TB ) is “+” or “–”. It is easy to show that transitivity of unconditional orderings guarantees that conditions (a) and (b) of rule 3 are always satisfied. Hence, repetitive application of this rule produces an optimal sequence for jobset I (or B). All models discussed in section 4 share the following property (semitransitivity). Property 2. Unconditional orderings are transitive if each entry of T is “+” or “–”. Decomposition rules play an important role even if the problem is initially not decomposable. Suppose that the model is solved by a branch and bound method by using a branching rule that adds a job to the first unfilled position of the sequence at each branching. Consider node σ, where ∑k ∈σ pk = t, and let B = I – σ. Note σ is terminated once block B is completely decomposable by one of the rules 1–4. According to remark 1 and property 2, t ≥ max (i, j) ∈B tij is a sufficient condition for σ to be terminated.

W. Szwarc y Decomposition in single-machine scheduling

275

Consider three jobs of I. If i1, i2, i3 are replaced in (5) and (6) by all possible combinations of i, j and k, i < j < k, then (5) as well as (6) consists of six conditions. Select two cases of (6) for i1 = i, i2 = j and i3 = k, and i1 = i, i2 = k and i3 = j, and replace them by the following conditions (6 ′) and (6″) that can be written (due to (4)) in the following form: ∆ij (t1 ) ≥ 0 and ∆jk (t1) ≥ 0 imply ∆ ik (t1 + p j ) ≥ 0, ( 6′ ) ∆ik (t1) ≥ 0 and ∆ jk (t1 ) < 0 imply ∆ij (t1 + pk ) ≥ 0.

(6 ′′ )

The above conditions are less restrictive since ∆uυ (t) ≥ 0, according to (3), implies ∆uυ (t + δ ) ≥ 0 for each u < υ, and δ > 0. Consider block B , I that starts at time t. For convenience, assume B = {1, 2,…,m}. Let TB be the precedence matrix of B. Define K = {i | i ∈B, tik ≤ t + ∑ ui −1 = 1 pu}. Using the arguments of [2] (that deals with a specific model), one can show that conditions (6′ ) and (6″ ) allow one to use, instead of rule 3, a less restrictive rule 3 ′ (to identify the first and last job of block B) by replacing (a)

tkj ≤ t (then cell (k, j) is marked by a “–”) by tkj ≤ t + ∑u ∈K pu in rule 3(a).

(b)

tik ≤ t (then cell (i, k) is marked by a “–”) by tik ≤ t + ∑ ui −1 = 1 pu in rule 3(b).

4.

Models with adjacent precedence matrices

The findings of sections 2 and 3 are applicable for the following seven models if the processing is uninterrupted (Models VI and VII are discussed in sections 5 and 6). Model I [2,8,9,18]

fk (Ck ) = wk Ck2 ,

Model II [9,13]

fk (Ck) = wk (Ck – pk) 2,

Model III′ [7,15,18]

fk (Ck ) = wk Ck2 + w k′ Ck ,

Model IV [11]

fk (Ck) = w ′ Ek + wTk ,

Model V [3,4,5,6,12,17]

fk (Ck ) = Tk ,

Model VI [1,10]

fk (Ck) = wp k Tk ,

Model VII [16]

fk (Ck) = w ′pk Ek + wp k Tk ,

where wk , wk′, w, and w ′ are job related penalties, Ek = max(dk – Ck , 0), Tk = max( Ck – dk , 0), and dk is the due date of job k. Consider the first three models. Instead of Model III ′, [15] deals with an equivalent Model III, where fk (Ck ) = wk (Ck + bk )2 and where wk′ = 2bk wk . Let uk = wk pk . To satisfy (3), index the jobs such that u1 ≥ u2 ≥ L ≥ un . (7) If ui = u j , then i < j if (a) wi ≥ wj (Model I), (b) wi ≤ w j (Model II), (c) wi + 2ui bi ≥ wj + 2uj bj (Model III).

W. Szwarc y Decomposition in single-machine scheduling

276

Consider ∆ ij (t) defined by (2). Then ∆ ij (t) = pi pj Rij (t), where (ui − u j ) (2t + pi + p j ) + wi − w j , for Model I,  Rij (t) = (ui − u j ) (2t + pi + p j ) − wi + w j , for Model II, (8) (u − u ) (2t + p + p ) + (w + 2u b ) − (w + 2u b ), for Model III. j i j i i i j j j  i Due to (7) and (8), ∆ ij (t) (and Rij (t)) are linear increasing functions of t if ui ≠ u j . We construct the adjacent precedence matrix T, where tij is the solution of equation Rij (t) = 0. If ui = uj , then Rij (t) ≥ 0 for every t and cell (i, j) is marked by a “–”. Table 1 provides the information about the transitivity results established in references [2,8,9,13,15] for Models I, II, III, IV, and V. Table 1 Known transitivity results of adjacent orderings. Condition (5)

Condition (5) if each entry of T is “+” or “–” or if p i2 ≤ min( pi1, pi3)

Condition (6)

Conditions (6'), (6")

Model I

?

Model II

Yes, except cases kji and jki [13]

Yes [8,9]

No [8]

Yes, Yes [2]

Yes [9]

Yes [13]

Yes, Yes [13]

Model III

?

Model IV

?

Yes [11] Yes, if pi2 ≤ max(pi1, pi3)

Yes [9]

No [15]

Yes, No [15]

No [11]

?

Model V

?

?

Yes [12]

Yes [12]

Notation kji, where i < j < k, stands for a special case of condition (5) or (6) where i1 = k, i2 = j, and i3 = i. Consider Model I. Let t0 and t0 + p, where p = ∑nk =1 pk , be the start and completion time of jobset I. Also, let q = p – pi – pj – pk ≥ 0. Then i → j, ∀t ∈Dij , means that Rij (t0) ≥ 0, while j → i, ∀t ∈Dij , means that Rij (t0 + q + pk ) < 0. According to (8), where wk = uk pk , Rij (t0 ) ≥ 0 ⇔ Rij (t 0 + q + pk ) ≥ 0 ⇔

2t0 + pi + 2 p j ui ≥ , uj 2t0 + 2p i + p j 2(t0 + q + pk ) + pi + 2 pj ui ≥ . uj 2(t0 + q + pk ) + 2 pi + pj

We establish the following new result (for proof, see appendix 1).

W. Szwarc y Decomposition in single-machine scheduling

277

Theorem 1. Unconditional adjacent orderings of Model I are transitive except for case ikj. To show that transitivity does not hold for case ikj, consider the following threejob example where t0 = 0, pi = 1, pj = 3, pk = 12, ui = 25 14, uj = 29 20, uk = 1 (wi , wj , wk are 25 14, 87 20, and 12, respectively). Then tij = 1.82, tik = 0, tjk = 1. The domains Dij , Dik , and Djk are [0, 12], [0, 3], and [0, 1], respectively. Hence, i → k and k → j unconditionally, while i → j for t ≥ 1.82 and j → i for t < 1.82. u Theorem 1 provides the following split rule (rule 4) for Model I. Split rule. Suppose every entry of T in row and column k is “+” or “–”. Then α, k, β is an optimal block sequence if every cell (i, j), i ∈α, j ∈β, of set Ω = {(i, j)|(i, k ) is “–” and ( j, k ) is “+”} is marked by “+” or “–”. According to [13], the split rule also holds for Model II if set Ω is Ω = {(i, j)|(i, k ) is “+” and ( j, k) is “–” or (k, j) is “+”}, where j ∈α and i ∈β. The split rules of Models I and II are much less restrictive than rule 3 of [9]. Models I, II, III are highly decomposable once parameters pk , wk , and wk′ are independently generated from a uniform distribution. Then only a small portion of cells are marked by “ tij ”. Szwarc [9] observed that the frequency of “ tij ” entries increases as a ≤ uk ≤ b, ∀k, where b a gets closer to 1. Notice that if a = b for each k, then the problem is trivial since 1, 2,…, n is the optimal sequence (all entries of T are “–”). Harder problems are solved by a branch and bound algorithm or [9] with the refinements of [2, 13, 15] and could easily handle large problems where n ≥ 100. This algorithm utilizes the decomposition mechanism of section 3, which is executed at every node of the branching tree before calculating the appropriate lower bound. Consider Models IV and V. To satisfy (3), the jobs are indexed by SPT. If pi = pj , then i < j if di ≤ dj . The respective ∆ ij (t) of these models are piecewise linear functions. According to [11], the tij for Model IV are defined as w ′pi + wp j w′  , if di − d j > ( pi − p j ) < 0,  di − w′ + w w′ + w  w ′pi + wp j w′ tij =   di − pi − w ′ + w , if di − d j ≤ w ′ + w ( pi − p j ) < 0,   0, if pi = p j .

(9)

Model IV belongs to the harder class of problems. Still, the decomposition mechanism proves to be useful in the branch and bound procedure currently under investigation.

278

W. Szwarc y Decomposition in single-machine scheduling

Next consider Model V. According to [12], the tij are defined as if di ≤ d j ,  0, tij =   max(di − p j , 0), if di > d j .

(10)

In [12], the transitivity of conditional orderings was established. We show the following result (for proof see appendix 2). Theorem 2. Unconditional orderings are transitive. The decomposition techniques of Model V based on adjacent orderings have not been tested yet. 5.

Global adjacent orderings

This section deals with a new ordering for models with no interruption in job processing. We say that an unconditional adjacent ordering is global if ∆ ij (t) ≥ 0 for every t ≥ 0 or ∆ ij (t) ≤ 0 for every t ≥ 0. If global orderings are transitive and the number of “ tij ” entries is small, then the following procedure builds the optimal solution as a sequence of blocks: Decomposition Procedure (DP). Step 1 . Define the initial precedence matrix T by placing the following symbols in cell (i, j), 1 ≤ i < j ≤ n: (a) “–” if i → j globally, (b) “+” if j → i globally, (c) “tij ” otherwise. Step 2 . Let Ω be a set of cells (i, j) of T marked by “ tij ”. Divide Ω into mutually exclusive subsets Ω1, Ω2,…, Ωm , m ≤ n, using the following rule: once (i, j) ∈Ωk , then cells (i, u) ∈Ω and (υ, j) ∈Ω are also assigned to Ωk . Define a multi-job block Bk as Bk = {i, j | (i, j) ∈Ωk}. The remaining jobs of set I – {B1 < B2 < … < Bm} form single-job blocks (job u is a single-job block if all entries in row and column u are “+” or “–”). Step 3 . For each block Bk , select an arbitrary job. For convenience, select a job with the smallest index, say ik . Step 4 . Consider a submatrix of T for jobs i1, i 2,…, im (each entry of this submatrix is “+” or “–”). Find the optimal sequence using, say, rule 3 (or 4). If, say, 1, 2,…, m is the resulting sequence, then B1, B2,…, Bm is the optimal block sequence. This procedure utilizes the following property (based on the transitivity of global orderings) (see [10]):

W. Szwarc y Decomposition in single-machine scheduling

279

If some job of Bu globally precedes some job of Bυ , then every job of Bu globally precedes every job of Bυ . Let B be an arbitrary block of the optimal block sequence that starts at time tB and completes at tB + ∑k ∈B pk . If (i, j), i, j ∈B is a “ tij ” cell where tij is outside the interval [tB, tB + ∑k ∈B pk – pi – pj ], then the ordering of pair i, j becomes local unconditional and cell (i, j) is marked by “–” if tij ≤ tB or “+” if tij ≥ tB + ∑k ∈B pk – pi – pj . Block B is further decomposed by the applicable decomposition rules of section 3. Consider Models VI and VII. Let ∆ ij (t) and ∆′ij (t) be their respective functions defined by (2). To satisfy (3), the jobs are indexed by LPT, where i < j if pi = pj and di ≤ d j. According to [16], ∆ ij (t) = (w (w ′ + w)) ∆′ij (t). Hence, both models share the following property (see [10]): Property 3. (a)

If di – dj ≤ 0,

then i → j, ∀t, t ≥ 0,

(b)

if di – dj ≥ pi – pj ,

then j → i, ∀t, t ≥ 0,

(c)

0 < di – dj < pi – pj , then j → i for t ≥ tij and i → j for t ≥ tij ,

where

tij = di − pi − pj +

di − d j pi − pj

p j , pi > pj .

(11)

If pi = pj and di = dj , then i → j globally because case (a) is checked prior to case (b). According to [10] and [16], global orderings of Models VI and VII are transitive. To illustrate DP for Model VI, consider example 1 of [10], where p1,…, p10 = 85, 78, 76, 70, 43, 33, 24, 18, 17, 7, and d1,…, d10 = 254, 218, 161, 197, 250, 265, 160, 241, 252, 307. For this example, set Ω = {(1, 5), (1, 8), (1, 9), (3, 7), (4, 7), (5, 8), (6, 9)} splits into Ω1 = Ω – Ω2 , where Ω2 = {(3, 7), (4, 7)}. Then B1 = (1, 5, 6, 8, 9), B2 = (3, 4, 7). The remaining two jobs form single-job blocks B3 = (2), B4 = (10). For this particular model, it is sufficient to arrange the first jobs of the four blocks by EDD. The resulting sequence is 3, 2, 1, 10. Hence, 2, (3, 4, 7), (1, 5, 6, 8, 9), 10 is an optimal block sequence. Models VI and VII also share the following properties: (a) local properties are transitive, and (b) the mix of local and global properties is semitransitive (see property 2). Based on those two properties, the split rule (rule 4) for those models can be formulated as follows: Split rule. α, k, β is an optimal block sequence if for every r ∈α and s ∈β cells (r, s), r < s or (s, r), r > s are marked by ± . Examine only those pairs r, s where one of two orderings r → k, k → s is global and the other one is local. Arkin and Roundy [1] also offer a decomposition method of Model VI by splitting the jobset into clusters without using the adjacent precedence matrix T. Their partition

280

W. Szwarc y Decomposition in single-machine scheduling

is, in fact, based on condition dr ≤ ds – ps (to ensure, using our terminology, that r → s globally). Notice that conditions (a) and (b) of property 3 can be combined into r → s globally if d r ≤ ds and d r − pr ≤ ds − ps .

(12)

Condition (12) is considerably less restrictive than dr ≤ ds – ps . This is why a cluster is a union of usually many blocks. In our example 1, Arkin–Roundy’s cluster partition splits the jobset into two clusters arranged as (1, 2, 3, 4, 5, 6, 7, 8, 9), 10. The decomposition mechanism presented in this section was highly successful (on a PC 386) in solving Model VI with up to 150 jobs (for a variety of tardiness factors and due date ranges) by complete decomposition or reducing the unsolved problems to mostly very small subproblems with sizes not exceeding 25 jobs. Only in 2 of 320 problems the job sizes of unsolved subproblems were 30 or 45. 6.

Models with inserted idle times

This section discusses decomposition techniques applicable to earliness-tardiness (E T) models where the start time is not fixed and idle times between jobs are permitted. Consider the E T Model VII. It was shown in [16] that Models VI and VII share the same precedence relations defined by property 3. The proof that property 3 can be extended to Model VII is based on the following two observations. (1)

Consider a schedule where there is idle time between adjacent jobs r and s. If r is the earlier job and dr > ds , then one can find a better schedule without idle time between r and s by starting r later or (and) starting s earlier.

(2)

If there is idle time in an optimal schedule between adjacent jobs r and s, where r is the earlier job, then ds – dr > ps .

Model VII is decomposable into blocks as Model VI. What is remarkable is that the optimal ordering of those blocks does not change when their start times are shifted. What does change is the ordering of jobs within each block. Notice that the start and completion times of each block are no longer fixed due to possible idle times between jobs. Therefore, one cannot create local orderings marked by “+”. As a result, the next decomposition stage is limited to converting certain “ tij ” entries into “–” only. Hence, the “+” entries correspond to global orderings exclusively, while the “–” entries correspond to global or local orderings. All decomposition rules of Model VI remain in force. The decomposition mechanism was able to handle (on a PC 386) without branching problems of size n = 40 and 50 by finding an optimal schedule among a small number of candidate sequences using the method described below. Consider a general E T model where fk (Ck ) = w k′ Ek + wk Tk , where wk′ and wk are earliness and tardiness penalties of job k ∈I. Suppose the jobs are processed in the order 1, 2,…, n. Since idle times are permitted in this model, the schedule is defined by a vector

W. Szwarc y Decomposition in single-machine scheduling

281

C = (C1, C2,…, Cn ) of completion times of the jobs. We have to select a schedule that minimizes ∑nk =1 fk (Ck ). In [14], a decomposition technique that considerably simplifies the solution method was developed. Consider two consecutive jobs i and i + 1, where i precedes i + 1 in an optimal schedule. According to [14], the following property holds. Property 4. There is no idle time between jobs i and i + 1 in an optimal schedule if di +1 − di ≤ pi + 1.

(13)

Let σ = u, u + 1,…, υ, u < υ, be a subsequence of S = 1, 2,…, n. Sequence σ is called a cluster if (13) holds for each i, u ≤ i ≤ υ – 1, and does not hold for i = u – 1 and i = υ. If (13) does not hold, then i and i + 1 belong to different clusters. Consider example 1 of [14] where p1…, p7 = 3, 2, 7, 3, 6, 2, 8 and d1,…, d7 = 12, 4, 26, 18, 16, 25, 30. Sequence S = 1, 2, 3, 4, 5, 6, 7 is split into a cluster sequence (1, 2), (3, 4, 5), (6, 7), where the jobs within each cluster are processed without interruption. Notice that the cluster decomposition does not depend on the earliness or tardiness penalties. The following basic property was also established in [14]. Property 5. In each cluster of an optimal schedule, the early jobs precede the nonearly jobs. Moreover, if i and i + 1 belong to the same cluster, then Ei ≥ Ei +1 if both jobs are early, while Ti ≤ T i +1 if those jobs are not early. Based on the cluster concept and properties 4 and 5, a simple and very fast algorithm was designed in [14] to find the optimal schedule. The processing starts with a schedule C, where Ci = ∑ik =1 pk for each i = 1,…, n. Next, the first block of clusters is identified that cannot be shifted. This block stays “behind”. The procedure is repeated for the reduced set of clusters to identify the next block that cannot be shifted. Otherwise, all remaining clusters are shifted by a specified amount, such that the last early job of a cluster changes its status by turning into an on-time job. After all Ck are updated, the procedure is repeated again and all non-early jobs are removed from the list of each cluster. The algorithm stops once a block involving the last cluster cannot be shifted. This algorithm does not explicitly deal with idle times which emerge automatically once a block of clusters stays behind while all remaining clusters are pushed forward. The solution is instantaneous if sequence S splits into one or n clusters. The proposed algorithm is extremely fast. It handles 500 job problems in less than 2 seconds on a PC 386. 7.

Models with adjacent and nonadjacent orderings

Consider a model with uninterrupted job processing where f (S) and ∆ ij (t) satisfy (1) and (3), respectively. Then adjacent orderings hold for every pair of jobs.

W. Szwarc y Decomposition in single-machine scheduling

282

Next, we introduce orderings between jobs that may not be adjacent. Ordering i ⇒ j means that i precedes j in an optimal sequence. Property 6 summarizes the known results. Property 6 (Sen et al. [7]). i ⇒ j if (a)

p i ≤ p j , wi ≥ wj

(b)

pi ≤ p j , wi ≥ w j , and wi′≥ wj′ for Model III′.

for Models I and II,

According to property 6, the nonadjacent orderings are limited to a restricted number of pairs i, j. The reader might wonder when an adjacent (unconditional) ordering becomes nonadjacent. To address this issue, consider block B , I that starts at tB ≥ 0 and completes at tB = ∑k ∈B pk . Let i be the job of B with the smallest index. If (6 ′ ) and (6″) are satisfied, then the following general property holds (the proof is similar to that of theorem 1 of [2] that deals with Model I). Property 7. Let i be the job of B with the smallest index. If i → u, for some u ∈B, then i ⇒ u. Properties 6 and 7 allow for further relaxation of rule 3 (for details, see [2]). We now discuss the nonadjacent orderings of Model V, where the jobs are indexed by SPT. Assume i < j. Let α i (β i ) be a set of jobs that have been shown to precede (follow) job i in an optimal sequence. Then si = ∑k ∈α i pk and ci = ∑nk ∈1 pk – ∑k ∈βi pk are the earliest start time and latest completion time of job i in an optimal sequence. Emmons [3] established the following properties when i ⇒ j or j ⇒ i in an optimal sequence. Property 8. (a)

i⇒j

if di ≤ d j or sj ≥ di – pj ,

(b)

j⇒i

if di > dj and cj ≤ di + pi ,

(c)

i⇒j

if di > dj and ci ≤ dj .

We prove the following result (the proof is given in appendix 3). Theorem 3 . Assume that u ⇒ υ implies su + pu ≤ sυ and cu + pu ≤ cυ . Then the orderings based on properties 8(a) and 8(b) are transitive. Assume for convenience that Huυ symbolizes the inequalities of property 8(a) for i = u, j = υ if u < υ and 8(b) for j = u, i = υ if u > υ. The idea of the proof of theorem 3 is to show that Hi1 i2 and Hi2i 3 imply Hi1i 3 . Remark 2. It is well known that the orderings based on properties 8(a), 8(b), and 8(c) are antitransitive, which means that precedence cycles may occur.

W. Szwarc y Decomposition in single-machine scheduling

283

We systematically collect the precedence information in our precedence matrix T and mark cell (i, j) by “–” or “+” whenever property 8(a) or 8(b), respectively, holds. The process is continued for the updated si and c i until no new “ ± ” cells can be created. Theorem 3 provides an alternative justification of the following result, established in [17]. Split rule. If each of the entries in row and column k is “+” or “–”, then αk , k, βk is an optimal block sequence. The conditions of the split rule imply that ck – sk = pk . The split rule of [17] proved to be very powerful. It completely decomposed 25% of all generated problems for each n, where 100 ≤ n ≤ 150. Another partition rule (called Lawler’s partition) is based on a result established by Lawler [4]. Property 9. If job n occupies position s, 1 ≤ s ≤ n, in an optimal block sequence α, n, β, then max k ∈α dk < min k ∈β dk . Thus, sets α and β are uniquely determined once position s of job n is known. The list of potential positions of job n in sequence α, n, β can be drastically reduced. Suppose job n is r th in an EDD sequence d[1] , d[2],…, d[n] , where jobs with identical due dates are arranged by SPT. According to property 8(a), condition di ≤ dn implies i ⇒ n. Hence, dn = d[r] < d [r +1] and the first r – 1 jobs of the EDD sequence precede job n, thus reducing the list to positions r, r + 1,…, n. This list can be further reduced by the following: Property 10. (a)

(Lawler [4]). Job n is not in position s, s ≥ r if

∑ pk + pn ≥ d[s + 1].

k ∈α

(b)

(Potts and Wassenhove [5]). Job n is not in position s + 1, s ≥ r if

∑ pk + pn < d[s + 1].

k ∈α

(c)

(Szwarc [12]). Job n is not in position s, s ≥ r if there exists a job i, i ∈{[r + 1], [r + 2],…,[s – 1]} such that

∑ pk + pn ≤ di + pi .

k ∈α

A very fast branch and bound algorithm based on pure decomposition is presented in [17]. It combines the split rule with Lawler’s partition (using property 10) to solve 2,400 problems with various degrees of difficulty whose sizes vary from 100 to 150 jobs.

W. Szwarc y Decomposition in single-machine scheduling

284

Remark 3. The algorithm of [17] was tested on four hundred 100-job problems with or without using property 10(c). Deleting this property caused a 9.7% increase of the average time and an 11.4% increase of the average number of nodes. 8.

Final remarks

The paper discusses a variety of decomposition techniques that simplify the solution of single-machine scheduling models. Most of these models share the following fundamental property: Function ∆ ij (t) of t, the cost of interchanging adjacent jobs i, j in a schedule where pair i, j starts at time t, changes its sign at most once. This property does not hold for the earliness-tardiness (or even tardiness) model with arbitrary job-dependent earliness and tardiness penalties wk′ and wk , since ∆ ij (t) may change its sign more than once for certain pairs i, j (see [11]). Then the adjacent ordering techniques are not applicable for this model. Still, a partitioning technique is available for an arbitrary earliness-tardiness model with inserted idle times that makes it easy to determine the optimal completion times of jobs for a given sequence. Acknowledgement I would like to thank one of the referees for his insightful comments which improved the earlier versions of the paper. Appendix 1 Proof of theorem 1. Define a=

2t0 + p i + 2 pj 2t0 + 2 pi + pj

, b=

2t0 + p j + 2 p k 2t0 + 2 pj + p k

, c=

2t 0 + pi + 2 pk 2t 0 + 2 pi + pk

.

Case ijk : We have to show that ui uj ≥ a and uj uk ≥ b imply ui uk ≥ c. Suppose ui uk < c. Then c > 1. Moreover, c > max(a, b). Simple calculations show that inequalities c > a and c > b imply that pj < pk and pi < pj , respectively. Hence, pi < pj < pk . According to the assumptions, we have ab ≤

ui uj

⋅

uj uk

=

ui uk

< c.

Consider inequality ab < c. After simplifications, it reduces to pi2 pk + p j p2k + pi p j2 < pi p 2k + p 2j pk + pi2 p j or

W. Szwarc y Decomposition in single-machine scheduling

pi pj

+

pj

pk

+

pk

pi

<

pi pk

+

pk pj

pj

+

pi

285

(∗)

.

Since pi < pj < pk , let pi = x, pj = x + y, pk = x + y + z, where y > 0 and z > 0. Substituting these values in (∗) leads to an equivalent expression yz ( y + z) < 0, which is impossible since y and z are positive. Hence ui uk ≥ c. To prove the remaining four cases, define a′ = b′ = c′ =

2(t0 + q + pk ) + pi + 2 pj 2(t0 + q + pk ) + 2 pi + pj 2(t0 + q + pi ) + p j + 2 pk 2(t0 + q + pi ) + 2 p j + pk 2(t0 + q + pj ) + pi + 2 pk 2(t0 + q + pj ) + 2 pi + pk

,

, .

Consider case jik. We have to prove that ui uj < a ′ and ui uk ≥ c imply uj uk ≥ b. Suppose uj uk < b. Then ui uj ui c≤ ⋅ = < a ′b. uj uk uk Simple calculations show that inequality a ′b > c is false. Cases jki and kij are handled like case jik by disproving inequalities ab < c ′ and ab′ < c ′, respectively. Finally, consider case kji. Let d = t0 + p, where p = ∑nk =1 pk . Then a′ =

2d − pi 2d − p j

2d − p j

, b′ =

2d − pk

, c′ =

2d − pi 2d − pk

.

By assumption, ui uj ≤ a ′, uj uk ≤ b′. Hence, ui uk

=

ui uj

⋅

uj uk

≤ a ′ b ′ = c′ .

u

Appendix 2 Proof of theorem 2. Let i < j < k (then di ≤ pj ≤ pk) be three arbitrary jobs of jobset I. To prove (5), we have to consider six cases: ijk, ikj, jik, kij, jki, and kji, where jik symbolizes the following case: j → i and i → k imply that j → k. First notice that i → j means that tij ≤ min t(i, j) = 0, while j → i means that di > dj and tij ≥ max t(i, j) = p – pi – pj = q + pk , where p = ∑nk =1 pk and q = p – pi – pj – pk . Case ijk: We have to prove that i → j and j → k imply that i → k. If di ≤ d k , then tik = 0 and i → k. Suppose di > dk .

W. Szwarc y Decomposition in single-machine scheduling

286

(a) If di ≤ d j , then dj > dk . By assumption, tjk = max(0, dj – pk) ≤ 0. Hence, tik = max(0, d i – pk) ≤ 0 and i → k. (b) If di > d j , then i → j means that tij = max(0, di – pj) ≤ 0. Thus, tik = max(0, di – pk) ≤ 0 and i → k. Case kij: By assumption, di > d k and tik = max(0,di – pk) ≥ q + pj . (a) If di ≤ d j , then dj > d k and tjk = max (0, dj – pk) ≥ max(0,di – pk) = tik ≥ q + pj ≥ q + pi . Then k → j since tjk ≥ q + pi . (b) Let di > dj . By assumption, tij = max(0, di – pj) ≤ 0. Then tik = max(0, di – pk) ≤ tij ≤ 0, which violates inequality tik ≥ q + pj . Hence, this case is ruled out. One can similarly prove the remaining four cases. Appendix 3 Proof of theorem 3. Consider three jobs where i < j < k (then pi ≤ pj ≤ pk). There are six possible cases: ijk, jik, ikj, jki, kij, and kji, where jik symbolizes case j ⇒ i and i ⇒ k implies that j ⇒ k. Case ijk: We have to prove only for di > d k since di ≤ dk implies that i ⇒ k. To show that sk ≥ di – pk , consider the following two cases. Case a: di > d j . Then sk > s j ≥ di – pj ≥ di – pk . Case b: di ≤ dj . Then dj > d k . Again, sk ≥ d j – pk implies sk > di – pk . Case jik : Again, we have to prove only for dj > dk . Since di > dj > dk , we have sk ≥ di – pk > dj – pk. Thus, sk > dj – pk . Case ikj : It remains to prove for di > d j . By assumption, di > dj > d k , so we have sk ≥ di – pk and sj ≥ sk + pk . Hence, sj ≥ di – pk + pk > di – pj . Case jki : By assumption, ck ≤ di + pi . Then c j < c k ≤ di + pi . Case kij : By assumption, di > dk and c k ≤ di + pi . First we show that dj > dk . Suppose dj ≤ d k . Then j ⇒ k. This together with assumption i ⇒ j implies (see case ijk) that i ⇒ k, contrary to the assumption k ⇒ i. To show that ck ≤ dj + pj , we only have to consider case di + p i > d j + p j. Then di > d j . By assumption, sj ≥ d i – pj . Consider sj and ck . If ck ≤ sj , then obviously k ⇒ j. Suppose ck > sj . Then di – pj ≤ sj < c k ≤ di + pi . Hence, c k – sj ≤ pi + p j < pj + pk , a contradiction. Remark. Case pi + pj = pj + p k is impossible since it would imply that pi = p k . Then i > k (since k ⇒ i), contrary to the assumption that i < j < k. Case kji: Then di > dj > dk and ck < c j < c i . Assumption cj ≤ di + pi implies ck < di + pi . u

W. Szwarc y Decomposition in single-machine scheduling

287

References [1] [2] [3] [4] [5] [6]

[7]

[8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18]

E.M. Arkin and R.O. Roundy, Weighted-tardiness scheduling on parallel machines with proportional weights, Operations Research 39(1991)64–81. F. Della Croce, W. Szwarc, R. Tadei, P. Baracco and R. Di Tullio, Minimizing the weighted sum of quadratic completion times on a single machine, Naval Research Logistics 42(1995)1263–1270. H. Emmons, One-machine sequencing to minimize certain functions of job tardiness, Operations Research 17(1969)701–715. E.L. Lawler, A pseudopolynomial algorithm for sequencing jobs to minimize total tardiness, Annals of Discrete Mathematics 1(1977)331–342. C.N. Potts and L.N. Van Wassenhove, A decomposition algorithm for the single machine total tardiness problem, Operations Research Letters 1(1982)177–182. C.N. Potts and L.N. Van Wassenhove, Dynamic programming and decomposition approaches for the single machine total tardiness problem, European Journal of Operational Research 32(1987) 405–414. T. Sen, P. Dileepan and B. Ruparel, Minimizing a generalized quadratic penalty function of job completion times: An improved branch-and-bound approach, Engineering Costs and Production Economics 18(1990)197–202. W. Szwarc, M.E. Posner and J.J. Liu, The single machine problem with a quadratic cost function of completion times, Management Science 34(1988)1480–1488. W. Szwarc, Parametric precedence relations in single machine scheduling, Operations Research Letters 9(1990)133–140. W. Szwarc and J.J. Liu, Weighted tardiness single machine scheduling with proportional weights, Management Science 38(1993)626–632. W. Szwarc, Adjacent orderings in single-machine scheduling with earliness and tardiness penalties, Naval Research Logistics 40(1993)229–243 (1993). W. Szwarc, Single machine total tardiness problem revisited, in: Creative and Innovative Approaches to the Science of Management, ed. Y. Ijiri, Quorum Books, 1993, pp. 407–419. W. Szwarc and S.K. Mukhopadhyay, Minimizing a quadratic cost function of waiting times in single-machine scheduling, Journal of Operational Research Society 46(1995)753–761. W. Szwarc and S.K. Mukhopadhyay, Optimal timing schedules in earliness-tardiness single machine sequencing, Naval Research Logistics 42(1995)1109–1114. W. Szwarc and S.K. Mukhopadhyay, Solution of the generalized Townsend single machine scheduling model, European Journal of Operational Research 91(1996)1263–1270. W. Szwarc and S.K. Mukhopadhyay, Earliness and tardiness single machine scheduling with proportional weights, The Journal of Global Optimization 9(1996)227–236, special issue on scheduling. W. Szwarc and S.K. Mukhopadhyay, Decomposition of the single machine total tardiness problem, Operations Research Letters 19(1996)243–250. W. Townsend, The single machine problem with quadratic penalty function of completion times: A branch-and-bound solution, Management Science 24(1978)530–534.