J Sched (2013) 16:105–115 DOI 10.1007/s10951-011-0261-x

Exact algorithms for inventory constrained scheduling on a single machine Dirk Briskorn · Florian Jaehn · Erwin Pesch

Published online: 20 December 2011 © Springer Science+Business Media, LLC 2011

Abstract This paper focuses on single machine scheduling subject to inventory constraints. Jobs add or remove items to or from the inventory, respectively. Jobs that remove items cannot be processed if the required number of items is not available. We consider scheduling problems on a single machine where the objective is to minimize the total weighted completion time. We develop properties of optimal solutions and design a branch and bound algorithm and a dynamic programming algorithm with two extensions. We compare the approaches in our computational study and empirically derive parameter settings leading to instances which are hard to solve. Keywords Machine scheduling · Inventory constraints · Branch and bound · Dynamic programming

1 Introduction Let us consider a problem which has originally been introduced by Briskorn et al. (2010) and which is to schedule D. Briskorn () Lehrstuhl für Quantitative Planung, Universität Siegen, Hölderlinstr. 3, 57068 Siegen, Germany e-mail: [email protected] url: www.uni-siegen.de/fb5/qp/ F. Jaehn · E. Pesch Lehrstuhl für Wirtschaftsinformatik, Universität Siegen, Hölderlinstr. 3, 57068 Siegen, Germany F. Jaehn e-mail: [email protected] url: www.uni-siegen.de/fb5/mis/team/ E. Pesch e-mail: [email protected]

jobs on a single machine subject to inventory constraints. Jobs insert to and remove items from a centralized inventory. Consequently, a job removing items can only be processed if the inventory provides enough items at its start time. The objective is to minimize the total weighted completion time. The motivation arose while considering a truck scheduling problem at a transshipment terminal where trucks arrive in order to deliver or pickup transportation units, e.g. containers. Each truck either delivers or picks up a certain number of units of a specific type and a truck supposed to pick up a given number of units cannot be served if the current inventory level is insufficient. In the terminology of our scheduling problem we may associate machines with gates of the terminal, trucks with jobs, and each transportation unit (container) carried by a truck with an item. Different types of items may be carried, however, we consider the case of a single type and a single terminal gate (machine). Another application of our model arises in maintenance scheduling. Consider production jobs to be scheduled on a single machine whose extent of wearing occasionally needs a maintenance. We can represent the maintenance state of the machine by the inventory level of our model. Then, an inventory level of zero requires maintenance before any further production job is processed. In our model a job represents a production job which reduces the maintenance state by a certain amount. Maintenance activities can be represented by jobs refilling the inventory which corresponds to increasing the maintenance level. We do not consider release dates, thus all jobs, trucks, and production jobs, are available for processing right at the beginning of the planning horizon. Furthermore the inventory’s capacity is unlimited and our model can initially be applied to those real world settings where inventory capacity is not an issue. Moreover, an efficient procedure may serve as a building block in an approach tackling a more general

106

problem, say scheduling trucks at a transshipment terminal having several gates. Inventory constraints as described above have been considered in project scheduling; see, for example, Bartels and Zimmermann (2009), Neumann and Schwindt (2002), Neumann et al. (2005), and Schwindt and Trautmann (2000). In Neumann and Schwindt (2002) it has been shown that inventory constraints are a generalization of both renewable and non-renewable resources. Thus, finding a minimum makespan project schedule considering (standard) precedence constraints as well as inventory constraints is a generalization of the well-known Resource Constrained Project Scheduling Problem which is known to be strongly NP-hard. To the best of our knowledge only a few papers have considered the scheduling of transport vehicles that have to be served at a transshipment terminal. Scheduling of trucks at cross-dock-terminals has been considered in Boysen et al. (2010). Trucks arrive to either drop off or pick up goods. The model assumes that the terminal has two gates. While trucks are unloaded at the first gate they are loaded at the second one. Boysen et al. (2010) show that minimizing makespan is strongly NP-hard even if all processing times are equal. Yu and Egbelu (2008) consider a similar model and develop a heuristic to solve the problem. McWilliams et al. (2005) propose a genetic algorithm in order to solve a problem with more than two gates. Further truck scheduling procedures varying, e.g., with regard to the number of dock doors, the objective, whether or not transportation times inside the terminal are considered and whether or not commodities are interchangeable between outbound trucks, are presented by Boysen (2010), Boysen et al. (2010), Chen and Lee (2009), Chen and Song (2009), and Miao et al. (2009). A recent review article on truck scheduling at cross docking terminals is provided by Boysen and Fliedner (2010). In maintenance scheduling, maintenance activities are usually limited to fixed time windows, see Lee (2004), or a lower and an upper bound for the time span between two maintenance activities has to be observed, see Chen (2008) and Sun and Li (2010). Usually, durations of maintenance activities are fixed in advance whereas Mosheiov and Sarig (2009) restricted the number of maintenance activities. In a stream of papers on maintenance scheduling it is often assumed that processing times of jobs are affected by preceding maintenance activities, see Mosheiov and Sarig (2009) and Zhao and Tang (2010). Our model contributes to this area by allowing total flexibility for the scheduling of jobs as long as the maintenance state does not drop below zero. Note that jobs representing maintenance activities should not have a direct impact on the objective value. Briskorn et al. (2010) elaborate on the computational complexity and distinguish polynomially solvable special cases. The more general single machine cases with objective to minimize maximum lateness and total completion time have been proven to be strongly NP-hard.

J Sched (2013) 16:105–115

Branch and bound (B&B) and dynamic programming (DP) belong to the most intensively used exact methods for tackling hard optimization problems, see Nemhauser and Wolsey (1999). In Briskorn and Leung (2010) B&B methods are developed for a problem differing from the one considered in this paper by the objective: while in Briskorn and Leung (2010) the maximum lateness is minimized we minimize total weighted completion time here. The obtained results are promising enough to develop exact methods for further problem variants which is the motivation for the research outlined in this paper. In contrast to the overall schemes, for both, B&B and DP, several components should be customized. In fact, besides the branching scheme and the Bellman equation we develop mechanisms to obtain lower bounds, dominance rules, and heuristics to obtain upper bounds. This paper is organized as follows. In the next section we specify the details of the problem and derive some optimality properties. In Sects. 3 and 4 we develop the B&B and DP algorithms, respectively. Both are evaluated and compared to each other by means of a computational study presented in Sect. 5. We conclude the paper in Sect. 6.

2 The problem 2.1 Modeling Consider a single machine and a set J of n jobs where each job j ∈ J is specified by its processing time pj , a weight wj , and inventory modification δj . The processing time pj of job j is the total time j uses the machine for being completed. A job’s weight describes its influence on the objective value of a schedule and, thus, intuitively its importance. The inventory modification parameter δj of job j specifies the change of the inventory level when j is started being processed until its completion. Consequently, if δj > 0 job j adds items to the inventory and j removes items from the inventory if δj < 0. Jobs may affect the inventory level in different ways. We may assume that inventory changes at the start of processing, at the completion of processing or continuously during processing. However, as long as the inventory level changes during processing of a job on a single machine there is no relevant difference between these models. We refer to jobs having positive or negative inventory modification as positive jobs or negative jobs and denote the corresponding subsets of jobs as J + with |J + | = n+ and J − with |J − | = n− , respectively. Without loss of generality we may assume that processing times, weights, and inventory modifications are integers. Let an initial inventory I0 ≥ 0 specify the inventory level at time zero, before the first job starts being processed. Consequently, we refer to the inventory level after completing

J Sched (2013) 16:105–115

107

Fig. 1 Example of a feasible schedule with I0 = 0

Fig. 2 Example of a feasible schedule with I0 = 2

the kth job as Ik . Hence, for a given sequence σ of jobs we  have Ik = I0 + kl=1 δσ (l) where σ (l) is the lth job in σ . Let S ⊂ J × N be a set of tuples where the first entry specifies a job j and the second one defines the completion time Cj of job j which is the end of the period in which job j is completed. All jobs have to be processed and the machine can only process one job at a time. We consider the non-preemptive case where a job’s processing cannot be interrupted. We say a sequence σ induces a schedule S if for any k, l, 1 ≤ k < l ≤ n implies Cσ (k) ≤ Cσ (l) . A schedule S is feasible if Ik ≥ 0, 1 ≤ k ≤ n, for the sequence inducing S. A sequence inducing a schedule is also said to be a schedule. At the bottom of Fig. 1 there is a Gantt Chart of a feasible schedule with three jobs specified by (j, pj , δj ). At the top the inventory level curve is drawn under the assumption of continuous inventory modification and empty initial inventory. Note that since I0 = 0 the only positive job 1 must be scheduled first while for the remaining jobs any order is feasible. Figure 2 shows a feasible schedule for the same set of jobs and I0 = 2. Any negative job can be scheduled first followed by the positive job. Scheduling the positive job at the last position leads to I2 = −1, which is infeasible. We consider a regular machine scheduling objective function, namely we minimize total weighted completion  time j ∈J wj Cj . As there are no release times an optimal schedule exists with no machine idle time. Such a schedule is fully specified by its inducing sequence. Extending the well-known three field notation as proposed by Graham et al. (1979), the problem may be specified  as 1|inv| wj Cj , see Briskorn et al. (2010). Briskorn et al.  (2010) have shown that 1|inv| wj Cj is strongly NP-hard even if wj = 1 for each j ∈ J and either positive or negative jobs are identical.

In order to present a condensed description of the problem we would like to conclude with an integer model. Define variables  1 if job i is scheduled before job j ; i = j, xij = 0 else.  Completion of job j is at time i pi xij + pj and minimizing  the total weighted completion time results in minimizing ( j i pi xij + pj )wj . We obtain the model Min s.t.

  i

j cˆij xij

xij + xj i = 1 ∀i = j xij + xj k + xki ≤ 2 ∀i, j, k, i = j, i = k, j = k  I0 + i δi xij + δj ≥ 0 ∀j xij ∈ {0, 1} ∀i, j where cˆij := pi wj for all i, j . The first set of constraints ensures that for any pair of jobs i, j either i is scheduled before j or vice versa. The second set of constraints ensures that the schedule is acyclic. If a schedule contains a cycle i1 , i2 , . . . , iλ , i1 of minimum length λ ≥ 4 then there must be a cycle of length 3. Therefore it is sufficient to avoid cycles of length 3. The third set of constraints requires that the inventory constraints are satisfied. 2.2 Optimality properties In this subsection we provide optimality properties, i.e. properties of at least one  optimal schedule. Note that the underlying problem 1|| wj Cj can be solved by the weighted shortest processing time (WSPT) rule, i.e. by sorting jobs in non-decreasing order of pj /wj , see Blazewicz et al. (2007) or Pinedo (2008).

108

J Sched (2013) 16:105–115

Lemma 1 There is an optimal sequence σ being a concatenation of subsequences, i.e.

Consequently, we may restrict our attention to optimal schedules satisfying the following property:

σ = σ0 σ1 σ2 . . . σk−1 σk σk+1 ,

Property 1 For any schedule where job j immediately precedes job i but i is preferred to j (i ≺ j ) there exists a schedule with non-increasing objective value where i and j are interchanged.

k≥0

such that (i) σ + := σ0 is a (possibly empty) subsequence consisting of positive jobs ordered in WSPT, (ii) σ − := σk+1 is a (possibly empty) subsequence consisting of negative jobs ordered in WSPT, (iii) each σl , 1 ≤ l ≤ k, consists of a non-empty subsequence of negative jobs followed by a non-empty subsequence of positive jobs and is ordered in WSPT, and (iv) pj /wj ≤ pj  /wj  or Ip < −δj  where j and j  are the last job in σl and the first job in σl+1 , 0 ≤ l < k, respectively, and σ (p + 1) = j . If σk+1 is not empty, then the above holds also for l = k. In plain English, the last job in σl and the first job in σl+1 are in WSPT or switching both jobs is infeasible due to a negative inventory level after finishing the (p + 1)th job. Proof Clearly, we can divide each schedule σ into σ + , σ − , and σ1 , . . . , σk . As the WSPT order is optimal for  1|| wj Cj it is easy to see that each subsequence of positive jobs and each subsequence of negative jobs can be assumed to be in WSPT order. This proves (i) and (ii). Assume that pj  pj > wj wj  j

where j is the last negative job and is the first positive job in a subsequence σl , 1 ≤ l ≤ k. Swapping j and j  leads to a feasible schedule σ  with non-negative inventory level because the previous schedule σ (before the swap) was feasible. Furthermore, according to the WSPT rule the objective value of the modified schedule cannot increase. This proves (iii). Now assume pj /wj > pj  /wj  and Ip ≥ −δj  where j and j  is the last job in σl and the first job in σl+1 , 1 ≤ l < k, respectively, and σ (p + 1) = j . Then, j and j  can be swapped without violating an inventory constraint since only Ip+1 drops to Ip + δj  ≥ 0. Again, due to the WSPT rule the objective value of the modified schedule cannot increase.  We say job i is preferred to job j (i ≺ j ) if one of the following conditions holds: • • • • •

pi /wi pi /wi pi /wi pi /wi pi /wi

≤ pj /wj , i ∈ J + and j ∈ J − , < pj /wj and i, j ∈ J + , = pj /wj , i, j ∈ J + , δi ≥ δj or i < j , < pj /wj and i, j ∈ J − , = pj /wj , i, j ∈ J − , δi ≥ δj or i < j .

Let σ 1 and σ 2 be two partial sequences containing the same subset of jobs and that can be extended to a feasible sequence. If the contribution to the objective value induced by σ 1 is at most that one of σ 2 then the following holds: Property 2 If there is an optimal sequence starting with σ 2 , then there is an optimal sequence starting with σ 1 . Proof Obviously, total processing time and total inventory modification of σ 1 and σ 2 are equal. Thus, replacing σ 2 by σ 1 in the optimal sequence yields a feasible sequence which must be optimal, as well.  Define    pj  f + pj J := j | j ∈ J , ≤ min wj j  ∈J − wj  and

   pj  − pj . ≥ max J := j | j ∈ J , wj j  ∈J + wj  b

Property 3 There is an optimal schedule where all jobs in J f are scheduled at positions 1, . . . , |J f | in WSPT order and all jobs in J b are scheduled in WSPT order at positions n − |J b | + 1, . . . , n. Property 3 immediately allows picking and scheduling all jobs in J f ∪ J b in a preprocessing step and, dropping them from further consideration. Let ub be an upper bound for the optimal objective function value of the instance consisting of jobs J and let lbj denote a lower bound for the instance containing all jobs of J except j . Then, we can determine an upper bound for the completion time, that is, a latest possible completion time lct(j ), of j in an optimum schedule. Property 4 In any optimal schedule the completion time Cj of job j is bounded by Cj ≤ lct(j ) :=

ub − lbj wj

for each j ∈ J . Analogously, we can determine a lower bound msw(j ) for the total weight of jobs being scheduled before j .

J Sched (2013) 16:105–115

109

Property 5 In every optimal schedule 

wi ≥ msw(j ) := tw −

i∈J :xij =1

ub − lbj pj

holds for each j ∈ J . Proof Consider an arbitrary schedule for J \ {j } and the lower bound lbj . Inserting j will increase the objective  pj where J  is the subset of value by exactly i∈J  wi  jobs not preceding j . Thus, i∈J  wi = tw − i∈J \J  wi ≤ ub−lbj pj

or the resulting schedule cannot be optimum.



3 Branch and bound algorithm We have to customize several components of the B&B algorithm as there is deciding how to split the set of all feasible solutions into smaller subsets which we consider in each step. Moreover, dominance rules may help to reduce the number of subproblems created without losing all optimal solutions. In Sect. 3.1 we outline the branching decisions and dominance rules. Obtaining lower bound and upper bounds is considered in detail in Sect. 3.2. The B&B approach uses Lemma 1 and Property 1 while there seems to be no efficient way to use Property 2 in this framework. Clearly, we can make use of Property 3 in a preprocessing step. The values lct(j ) and msw(j ) as described in Properties 4 and 5 are also determined in a preprocessing step using the bounds to be described below. 3.1 Branching A node having depth d in the branching tree represents a partial schedule where jobs on positions (slots) 1, . . . , d in the schedule are fixed while no jobs have been selected for positions d + 1, . . . , n. Let F ⊆ J be the set of jobs assigned to positions 1, . . . , d. Then, the current node represents all solutions starting with the same sequence of d jobs on the first d positions. Alternatively, this problem can be seen as  an instance of 1|inv| wj Cj with a set of jobs J  := J \ F  and an inventory level of I0 := I0 + j ∈F δj . Consequently, we branch on the job being assigned to position d + 1 and there may be up to n − 1 child nodes. In order to reduce the number of child nodes created in each step we employ Lemma 1. Let j d be the last job (on position d) in the partial schedule. We create a child node for job  j ∈ J \ F if Id + δj ≥ 0, and i∈F pi + pj ≤ lct(j ), and  i∈F wi ≥ msw(j ), and (1) j d ≺ j , (2) j d ∈ J − , j ∈ J + , pj /wj > pj d /wj d , or (3) j d ∈ J + , j ∈ J − , pj /wj < pj d /wj d , and Id−1 < −δj .

First of all, clearly, j must be feasible to position d + 1 with respect to inventory constraints and Properties 4 and 5 must hold. Then, rule 1 covers all those cases where j d is preferred to j independently of the actual inventory level Id−1 , see Sect. 2.2. Consequently, rules 2 and 3 cover the case where exactly one job belongs to J + and has higher pi /wi . If the negative job has already been feasibly scheduled at position d, then the positive job can be scheduled at position d + 1 defining a new node of the search tree. Note that scheduling a positive job inventory constraints remain satisfied. If the positive job is already feasibly scheduled at position d, then the negative job may be feasibly scheduled at position d + 1 provided the inventory level is sufficiently high. We considered two different ways of selecting a node for further branching. Using Best Bound Search implies that the node with the lowest lower bound (see below) is fathomed next. Although this order guarantees the lowest number of nodes to be fathomed, it requires to record a large number of unexplored nodes. Thus, due to scarce memory, this method might be slow for large instances. To overcome this problem, Depth First Search fathoms the node with highest number of fixed positions (“Last in, first out”). Ties are broken using the best bound rule. 3.2 Bounds 3.2.1 Lower bounds A node at search depth d specifies a partial schedule consisting of those jobs j ∈ F ⊆ J assigned to positions 1, . . . , d. Let WC be the contribution of the partial schedule to the objective value and let P be the total processing time of the partial schedule, i.e.   wj Cj and P = pj . WC = j ∈F

j ∈F



 As 1|| wj Cj is a relaxation of 1|inv| wj Cj , at any search tree node a lower bound can easily be obtained by ordering all jobs in J \ F according to the WSPT rule. Let ORD be the objective value of the relaxation on the reduced set of jobs from J \ F . The lower bound lb for the current node is  wj + ORD. lb = WC + P j ∈J \F

3.2.2 Upper bounds We propose three methods to derive upper bounds based on a given partial schedule at positions 1, . . . , d. The first one schedules all jobs in J \ F in WSPT order at positions d + 1, . . . , n. If the schedule is feasible it is optimal with

110

respect to the partial schedule at the first d positions. Let d < k < n be the first position where the inventory constraint is violated, i.e. Ik < 0 and δσ (k) < 0. Let the next positive job be scheduled at position k  , k  > k. Then, we move the positive job to position k and shift each job at position h = k, . . . , k  − 1 to position h + 1. Note that the obtained solution is best among all solutions in which the subset of positive jobs and the subset of negative jobs are ordered according to WSPT. This follows directly from the proof of Lemma 1(iv). We will refer to the objective function value of this solution by ub1. The second method repairs the lower bound solution in a similar way. Again, whenever we find a position k, Ik < 0, a positive job is moved to k. However, we select the positive p job j scheduled after position k that minimizes wj jδj . The difference to the first method is that the positive job is not only chosen with respect to its WSPT rank (i.e. its influence on the objective), but also with respect to δj . This solution’s objective score is called ub2. The second method keeps the WSPT order of all negative jobs while the positive jobs might have a different order. Both methods might lead to solutions that can easily be improved by exchanging the positions of two jobs. Firstly, the solutions of the first and second method are compared and the better one is used for further improvement using a 2-opt local search. For a given solution σ , a solution σ  is called a neighbor, if |{k | σ (k) = σ  (k)}| = 2. For the current solution, all neighbors and their objective function values are determined. If the best neighbor’s objective function value is worse than the one of the current solution, the method stops. Otherwise, the best neighbor replaces the current solution and the procedure re-starts. The objective value of the solution when the 2-opt local search terminates is upper bound ub3.

4 Dynamic programming algorithm 4.1 DP algorithm without explicit consideration of consecutive jobs In order to specify the basic dynamic programming approach, namely DP1, we follow the basic idea of Held and Karp (1962). We propose to consider state s where s = (s1 , . . . , sn ) ∈ {0, 1}n determines that the set J (s) = {j ∈ J | sj = 1, j ∈ J } of jobs has been scheduled in positions 1, . . . , |J (s)|. We, furthermore, consider the transition from state s to state t, t = (t1 , . . . , tn ), if

J Sched (2013) 16:105–115

1. there is exactly one j ∈ J such that sj + 1 = tj , tj  for each j  = j , and 2. sj  = 3. I0 + j ∈J (t) δj ≥ 0. This transition represents assigning job j , sj + 1 = tj , to position |J (t)| and, therefore, setting Cj = i∈J,ti =1 pi . Consequently, the cost c(s, t) of this transition is ⎧  if i∈J,ti =1 pi > lct(j ) ⎪ ⎨∞  c(s, t) = or i∈J,ti =1 wi < msw(j ) ⎪ ⎩  wj i∈J,ti =1 pi else. Let c(t) be the cost of state t. Now, we can formulate the Bellmann function as  c(t) = min c(s) + c(s, t) | there is a transition from s to t s

and, hence, the optimal solution value is c(1, . . . , 1). In contrast to the approach presented in Sect. 3 the DP approach presented in this section makes use of Property 2 while Lemma 1 and Property 1 are not used. Just as in Sect. 3 we can make use of Property 3 in a preprocessing step. Note that for each state t we can easily derive a lower bound analogously to Sect. 3.2.1: 

  pj · wj + ORD, lb(t) = c(t) + j ∈J (t)

j ∈J \J (t)

where ORD describes the solution value if only jobs j ∈ J \J (t) are sequenced according to the WSPT rule. Whenever lb(t) ≥ ub(t), we can drop state t from consideration. 4.2 DP algorithms with consecutive jobs We propose two extensions of the approach presented in Sect. 4.1. The first extended DP approach, DP2, operates on states similar to the ones used in Sect. 4.1 but specifying whether the job on the last already scheduled position is a positive job or not. Consequently, we propose to consider state s  where s  = (s1 , . . . , sn , p) ∈ {0, 1}n+1 determines that the set J (s  ) = {j | sj = 1} of jobs has been scheduled at positions 1, . . . , |J (s  )| and that the job at position |J (s  )| is a positive job if p = 1 and a negative job otherwise. Let p(s  ) denote the last entry in s  . We consider the transition from state s  to state t  , t  = (t1 , . . . , tn , p(t  )), if 1. there is exactly one j ∈ J such that sj + 1 = tj , 2. sj  = tj  for each j  = j ,

J Sched (2013) 16:105–115

3. p(t  ) = 1 if and only if j ∈ J + , 4. there is a job i, i ∈ J (s  ), such that i ≺ j , and 5. I0 + j ∈J (t  ) δj ≥ 0. Condition 4 is due to Property 1. Note, however, that it is not known which job is scheduled in slot |J (s  )|. Therefore we require that at least one job i ∈ J (s  ) exists which may be scheduled immediately before j . Interpretation of the transition, cost of transition c(s  , t  ), and the Bellmann function are completely in analogy to those presented in Sect. 4.1. Then the optimal solution value is given by min{c(1, . . . , 1, 1), c(1, . . . , 1, 0)}. In the next extended DP approach, DP3, we consider states similar to the ones used in Sect. 4.1 but specify the job in the last already scheduled position. Consequently, we consider state s¯ where s¯ = (¯s1 , . . . , s¯n , l) ∈ {0, 1}n × J determines that the set J (¯s ) = {j | s¯j = 1} of jobs has been scheduled in positions 1, . . . , |J (¯s )| and that job l is scheduled at position |J (¯s )|. Let l(¯s ) denote the last entry in s¯ . There is a transition from state s¯ to state t¯, t¯ = (t¯1 , . . . , t¯n , l(t¯)), if

111

other states than states in DP1 have. Thus, we have two opposite trends and we do not know in advance which one proves to be more powerful in the average case. Comparing DP2 and DP3 we observe a similar relation. DP3 has higher worst case bound for the number of states and transitions. However, there is no clear indicator regarding the average case. Note that the B&B and DP3 use Property 1. While the B&B approach additionally uses the lower bounds of Sect. 3.2.1, DP3 uses Property 2.

5 Computational results The proposed algorithms have been implemented in Java 2 and run on an Intel® Core™2 Duo, 2.53 GHz PC, with 2.96 GB of memory. To the best of our knowledge, no test  bed is available for 1|inv| wj Cj . Thus, we randomly generated a huge number of instances as will be described next. 5.1 Instance generation In order to obtain a big variety of instances, various settings for choosing the parameters were considered in order to gen erate the test set. An instance of 1|inv| wj Cj can be characterized by the following parameters.

s¯l(t¯) + 1 = t¯l(t¯) , s¯j  = t¯j  for each j  = l(t¯), l(¯s ) ≺ l(t¯), l(¯s ) ∈ J − , l(t¯) ∈ J + , pl(t¯) /wl(t¯) > pl(¯s ) /wl(¯s ) , l(¯s ) ∈ J + , l(t¯) ∈ J − , pl(t¯) /wl(t¯) < pl(¯s ) /wl(¯s ) , and − δl(¯s ) < −δl(t¯) , and I|J (¯s )| 6. I0 + j ∈J (t¯) δj ≥ 0.

1. 2. 3. 4. 5. 6.

Conditions 3 to 5 are in line with (1) to (3) of Sect. 3.1. Again, interpretation of the transition, cost of transition c(¯s , t¯), and the Bellmann function are completely in analogy to Sect. 4.1. Then the optimal solution value is minj ∈J {c(1, . . . , 1, j )}.

Each of the parameters has been determined as follows.

1. 2. 3. 4. 5.

4.3 Analysis In this section we shortly analyze the worst case run time complexity of DP1, DP2, and DP3. It is not hard to see that the size of the corresponding state spaces are increasing from DP1 to DP2 and from DP2 to DP3. The number of states for DP1, DP2, and DP3 is O(2n ), O(2n+1 ), and O(n2n ). For each state there are O(n) transitions to other states and we cannot expect DP3 to perform better than DP1. DP2 is a compromise in a sense that we have more information associated to each state than in DP1 and less than in DP3. According to the worst case bound in DP2 we have twice as many transitions than in DP1. Depending on the problem instance each state in DP2 has less connections to

The number of jobs The percentage of positive jobs The processing time pj for every job j The weight wj for each positive job j ∈ J + The weight wj for each negative job j ∈ J − The inventory modification δj for each positive job j ∈ J+ 7. The inventory modification δj for each negative job j ∈ J− 8. The initial inventory I0

1. The number of jobs was set to 5, 10, 15, 20, 25. 2. We differ between a very large percentage of positive jobs (80%), a large percentage (60%), a medium percentage (50%), a small percentage (40%), and a very small percentage of positive jobs (20%). Thus, there are five variations. 3. The integer processing times of the jobs j ∈ J are uniformly distributed in either of the intervals [1, 1], [1, 3], [1, 5] or [1, 10] (four variations). 4. The integral weights wj of the jobs are uniformly distributed in either of the intervals [1, 1], [1, 3], [1, 5] or [1, 10] (four variations). 5. Integral weights wj for negative jobs j ∈ J − are multiplied by either 1, 4 or 8 (three variations).

112

J Sched (2013) 16:105–115

6./7. The integral inventory modifications δj are uniformly distributed in either of the intervals [1, 1], [1, 3], [1, 5] or [1, 10] and in case of j ∈ J − , the result is multiplied by either 1, 4 or 8 (four variations /three variations). 8. In order to ensure a feasible solution for an instance,  (min) := max{− j ∈J δj , 0} must hold. We tested I0 ≥ I0 (min)

instances with minimum inventory level I0 = I0 , (min) +0.5, and high medium inventory level I0 = 1.2·I0 (min) + 0.5 (three variations). inventory level I0 = 1.4 · I0 We generated the test set using a full factorial design of all variations. Thus, for a given number of jobs, 5 · 4 · 4 · 3 · 4 · 3 · 3 = 8640 instances were obtained and the maximum runtime for a single instance had to be kept low. We allowed 5 minutes. 5.2 Results In our first test, we compare the three different upper bounds. Table 1 contains the results of ub1, ub2, and ub3 Table 1 Comparison of the upper bounds Jobs

ub1

ub2

ub3 2619204

5

2624715

2621958

10

7528036

7518225

7501387

15

14904439

14877579

14852457

20

24823747

24772688

24739484

25

36456349

36392150

36341746

Table 2 Results of the branch and bound and dynamic programming algorithms

Jobs 5

10

15

20 a Best solutions found before termination of the algorithm. The entry for BandB corresponds to the optimum

lb

for all instances with 5, 10, 15, 20, and 25 jobs. Each entry is the sum of 8640 results. Obviously, ub3 cannot be worse in any instance than ub1 and ub2. In fact, ub3 is significantly better than the other upper bounds, especially if the number of jobs is large. Although ub2 turns out to be better than ub1 in general, there are some instances in which ub1 is smaller. As all results were obtained in less than a second, we have used ub3 in our Branch and Bound and Dynamic Programming approaches. The Branch and Bound Algorithm using Best Bound Search turned out to be the least effective algorithm. Out of the 2880 instances with 15 jobs and high inventory level, 49 instances could not be solved within the time limit. Thus, we do not consider this algorithm furthermore. The results of Branch and Bound, DP1, DP2, and DP3 for 5, 10, 15, and 20 jobs are shown in Table 2. We present lower bounds (lb), upper bounds (ub3), the optimal solution values ub∗ , the number of search tree nodes for Branch and Bound and accordingly the maximum number of states at a certain depth for the Dynamic Programming approaches (Nodes), the CPU in seconds, and the number of instances terminated by the time limit (Abort). Again, each entry describes the sum of 8640 results. However, in case of 20 jobs and a medium or high inventory level a major number of instances exceeded the runtime limit. Thus, each entry corresponds to the sum of the results of 2880 instances. There are instances with 20 jobs and a high inventory level, which cannot be solved by any of the proposed algorithms within the time limit. This, and the fact that the upper bound generally is close to the optimal solution make us be-

ub3

uba

Nodes

CPU

Abort

BandB

2425824

2619204

2604850

23514

0.61

DP1

2425824

2619204

2604850

13614

0.56

DP2

2425824

2619204

2604850

15767

0.60

DP3

2425824

2619204

2604850

15255

0.64

BandB

6994614

7501387

7432273

1010376

7.73

DP1

6994614

7501387

7432273

200213

5.30

DP2

6994614

7501387

7432273

244387

5.50

DP3

6994614

7501387

7432273

296900

5.57

BandB

13861536

14852457

14682167

139772381

DP1

13861536

14852457

14682167

2929527

859

DP2

13861536

14852457

14682167

3677864

1504

DP3

13861536

14852457

14682167

5878980

2425

7791165

8121601

8061884a

914012232

14795

21 78

BandB

1216

DP1

7791165

8121601

8077017a

6750435

32964

DP2

7791165

8121601

8081852a

7636373

38609

93

DP3

7791165

8121601

8084511a

11506531

45193

119

J Sched (2013) 16:105–115

113

Table 3 The influence of the number of positive jobs on the number of search tree nodes 5 Jobs

10 Jobs

15 Jobs

20 Jobs

Table 4 The influence of the spread of pj /wj on the number of search tree nodes a

5 Jobs

10 Jobs

15 Jobs

20 Jobs

80%

8,189

457,331

84,309,385

422,764,598

0

1,709

32,024

597,398

2,114,254

60%

6,380

304,124

25,901,872

192,319,983

5

1,707

33,128

703,124

2,826,032

50%

6,157

168,618

24,432,521

271,822,762

10

1,715

34,635

799,157

3,226,756

40%

2,788

70,032

5,011,315

27,104,889

50

1,717

35,559

938,567

4,004,279

20%

0

10,271

117,288

0

r

0.78

0.84

0.91

0.90

r

0.96

0.97

0.91

0.91

lieve that our NP-hard problem is hard to tackle even for small instances. A comparison of the algorithms shows that Branch and Bound is best for the given test bed. It is the only algorithm, which delivers all optimal solutions for 20 jobs and a high inventory level (although optimality was only proven after exceeding the time limit). As the worst case number of states of DP1 is smaller than the one of DP2, which again is smaller than the one of DP3 we would expect that the average results show the same effect. Indeed, the runtimes reflect the same tendency, although there are several instances in which DP3 has less states than DP2 and even less than DP1. 5.3 Analysis of instances Although the presented algorithms fail to solve some instances with only 20 jobs, they solve most instances within seconds, even if many more jobs are considered. Thus, we would like to (empirically) figure out what makes an instance to be “hard”. In what follows, we reduced our focus on the Branch and Bound algorithm with Depth First Search, as this algorithm turned out to be best for the test bed at hand. We quantify the “hardness” of an instance by the number of search tree nodes required for solving it. That means, if an instance can be solved with less search tree nodes than another one, we may call the first instance “easier” than the second one. Firstly, let us consider how the percentage of positive jobs might influence the results. In Table 3, the number of search tree nodes are depicted for different percentages of positive jobs. Each entry denotes the sum of 1728 instances (last column: 576 instances). The effect of the percentage of positive jobs on the number of search tree nodes is summarized using the Pearson Correlation Coefficient, denoted by r. As r is always close to one, we may state that for our test bed and for the used parameters, a higher percentage of positive jobs leads to harder instances. Of course, this statement is not true in general (an instance consisting only of positive jobs can easily be solved using WSPT). However, it seems to be obvious that

for this test bed, the instances get harder, if only few negative jobs are present. This is caused by the fact that negative and positive jobs were not generated symmetrically. Otherwise the result should be symmetric as well, as each instance of  1|inv| wj Cj can be transformed to an equivalent instance by setting pj = wj , wj = pj , δj = −δj for each job j (see Briskorn et al. 2010). Thus, the results obtained from Table 3 cannot be generalized, but show that instances get harder, if there are more positive (negative) jobs, and these jobs have less extreme attributes than the negative (positive) jobs. There is little sense in solely analyzing the influence of the processing times pj or solely analyzing the influence of the weights wj . An optimal solution of an instance is also optimal if all pj (and/or all wj ) are multiplied by a constant. Considering the ratio pj /wj , an instance in which pj /wj is constant for all j ∈ J is easy. However, generally speaking a low spread of pj /wj makes an instance harder, as the following experiment shows. We generated a second set of instances in which pj and wj were obtained by a randomly generated integer number between 1 and 5 plus a constant a: pj = rand(1, 2, 3, 4, 5) + a, wj = rand(1, 2, 3, 4, 5) + a

∀j ∈ J.

The remaining parameters (δj and I0 ) have been obtained as in Sect. 5.1. a has been set to 0, 5, 10 and 50. The expected value of pj /wj is always 1, but its spread is smaller with increasing a. For each parameter setting, we obtained nine instances, leading to 9 · 5 · 4 · 3 · 3 = 1620 instances for a given number of jobs. The results are shown in Table 4. Each entry corresponds to the sum of 1620 instances (540 instances in the last column). Although the influence seems to be not as strong as the one shown in Table 3, it is quite obvious that instances with a = 0 were the easiest to solve. In a further test, we analyzed how far higher weights for negative jobs have an impact on the number of search tree nodes, and consequently on the runtime. Again, we use the test set as described in Sect. 5.1. The number of required search tree nodes is shown in Table 5 for the cases that the weights of negative jobs are multiplied by 1, 4 or 8. A high factor leads to a considerable increase in search tree

114

J Sched (2013) 16:105–115

Table 5 The influence of increased weights for negative jobs on the number of search tree nodes Factor

5 Jobs

10 Jobs

15 Jobs

20 Jobs

1

2,733

54,749

2,605,670

8,797,984

4

9,627

399,829

43,500,454

389,916,258

8

11,154

555,798

93,666,257

515,297,990

r

0.91

0.96

1.00

0.93

Table 6 The influence of different intervals used for obtaining the inventory modification on the number of search tree nodes

levels. As expected, instances are the hardest if the minimum level is used. The analytical results are perfectly reflected for the hardest instance on 20 jobs and still solved by our Branch and Bound. 80% of the jobs are positive, the processing times are uniformly distributed in the interval [1,10], whereas all positive weights are 1 and all negative weights equal to −8. The inventory modifications are uniformly distributed in the interval [1,10]. The initial inventory level has been multiplied by 1.4 because instances with a lower initial inventory level were too hard to solve. 81,379,572 search tree nodes and almost 21 minutes were required to solve this instance.

Interval

5 Jobs

10 Jobs

15 Jobs

20 Jobs

[1, 1]

5,052

163,606

16,066,537

118,758,800

6 Conclusion and outlook

[1, 3]

5,634

219,127

31,628,033

222,172,167

[1, 5]

6,480

306,350

34,337,109

304,064,288

[1, 10]

6,348

321,293

57,740,702

269,016,977

r

0.80

0.89

0.98

0.70

 We have considered the 1|inv| wj Cj Scheduling Problem, in which jobs have to be scheduled on a single machine in accordance to inventory constraints. A solution with minimum total weighted completion time is searched. In this context we have presented various optimality properties, leading to a Branch and Bound algorithm and a Dynamic Programming approach with some variants. Although most instances can easily be solved in a short time, even with a high number of jobs, there are instances with 20 jobs that we were not able to solve within a few minutes. Thus, the generation of efficient heuristics or approximation algorithms would be a reasonable topic for further research.  Considering the practical basis for 1|inv| wj Cj , future research might need to extend the problem formulation. Especially cases in which several machines (or gates) are considered, in which the goods might be of different kinds, and in which the inventory is limited, are of high practical relevance.

Table 7 The influence of the initial inventory on the number of search tree nodes Factor 1.4 1.2

5 Jobs

10 Jobs

3,593

110,375

15 Jobs 11,020,915

5,039

184,284

18,128,810

1

14,882

715,717

110,622,656

r

–0.92

–0.92

–0.90

nodes. Thus, if the importance of negative jobs on the objective function is increased compared to the positive jobs, instances are harder to solve. A similar result appears if we consider the different possible intervals from which the inventory modification has been chosen. As shown in Table 6, a larger interval leads to harder instances. One might expect that this effect cannot be continued for arbitrary large intervals. In fact, it is worth mentioning that many instances for which the inventory modification is from the interval [1, 10] were easier to solve than those for which the interval is [1, 5]. We also analyzed the modification of the number of search tree nodes if different factors for the inventory modification of negative jobs are used. However, we were not able to detect any kind of correlation. Finally, let us take a look at the initial inventory level. It seems to be most obvious that an inventory level above the (min) minimal inventory level I0 should make an instance easier. The higher the initial inventory level, it is more likely that a solution is optimal in which all jobs are in WSPT order. Table 7 presents the results for different initial inventory

References Bartels, J.-H., & Zimmermann, J. (2009). Scheduling tests in automotive R&D projects. European Journal of Operational Research, 193(3), 805–819. Blazewicz, J., Ecker, K., Pesch, E., Schmidt, G., & Weglarz, J. (2007). Handbook on scheduling. Berlin: Springer. Boysen, N. (2010). Truck scheduling at zero-inventory crossdocking terminals. Computers & Operations Research, 37, 32–41. Boysen, N., & Fliedner, M. (2010). Cross dock scheduling: classification, literature review and research agenda. Omega, 38, 413–422. Boysen, N., Briskorn, D., & Tschöke, M. (2010). Truck scheduling in cross docking terminals with fixed outbound departures. Working Paper. Boysen, N., Fliedner, M., & Scholl, A. (2010). Scheduling inbound and outbound trucks at cross docking terminals. OR Spektrum, 32, 135–161. Briskorn, D., & Leung, J. (2010). Branch and bound algorithms for minimizing maximum lateness of trucks at a transshipment terminal. Working Paper.

J Sched (2013) 16:105–115 Briskorn, D., Choi, B.-C., Lee, K., Leung, J., & Pinedo, M. (2010). Complexity of single machine scheduling subject to nonnegative inventory constraints. European Journal of Operational Research, 207(2), 605–619. Chen, F., & Lee, C.-Y. (2009). Minimizing the makespan in a twomachine cross-docking flow shop problem. European Journal of Operational Research, 193, 59–72. Chen, F., & Song, K. (2009). Minimizing makespan in two-stage hybrid cross docking scheduling problem. Computers & Operations Research, 36, 2066–2073. Chen, J.-S. (2008). Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan. European Journal of Operational Research, 190, 90– 102. Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimisation and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5, 236–287. Held, M., & Karp, R. (1962). A dynamic programming approach to sequencing problems. SIAM Journal, 10, 196–210. Lee, C.-Y. (2004). Machine scheduling with availability constraints. In J. Y.-T. Leung (Ed.), Handbook of scheduling: algorithms, models and performance analysis (pp. 22-1–22-13). McWilliams, D. L., Stanfield, P. M., & Geiger, C. D. (2005). The parcel hub scheduling problem: A simulation-based solution approach. Computers & Industrial Engineering, 49, 393–412. Miao, Z., Lim, A., & Ma, H. (2009). Truck dock assignment with operational time constraint within crossdocks. European Journal of Operational Research, 192(1), 105–115.

115 Mosheiov, G., & Sarig, A. (2009). Scheduling a maintenance activity and due-window assignment on a single machine. Computers & Operations Research, 36, 2541–2545. Nemhauser, G., & Wolsey, L. A. (1999). Integer and combinatorial optimization. New York: Wiley-Interscience. Neumann, K., & Schwindt, C. (2002). Project scheduling with inventory constraints. Mathematical Methods of Operations Research, 56, 513–533. Neumann, K., Schwindt, C., & Trautmann, N. (2005). Scheduling of continuous and discontinuous material flows with intermediate storage restrictions. European Journal of Operational Research, 165, 495–509. Pinedo, M. (2008). Scheduling: theory, algorithms, and systems. Berlin: Springer. Schwindt, C., & Trautmann, N. (2000). Batch scheduling in process industries: An application of resource-constrained project scheduling. OR-Spektrum, 22(4), 501–524. Sun, K., & Li, H. (2010). Scheduling problems with multiple maintenance activities and non-preemptive jobs on two identical parallel machines. International Journal of Production Economics, 124, 151–158. Yu, W., & Egbelu, P. J. (2008). Scheduling of inbound and outbound trucks in cross docking systems with temporary storage. European Journal of Operational Research, 184, 377–396. Zhao, C.-L., & Tang, H.-Y. (2010). Single machine scheduling with general job-dependent aging effect and maintenance activities to minimize makespan. Applied Mathematical Modelling, 34, 837– 841.