Journal of the Operational Research Society (2013) 64, 1851–1864

© 2013 Operational Research Society Ltd. All rights reserved. 0160-5682/13 www.palgrave-journals.com/jors/

Minimizing maximum lateness of jobs in inventory constrained scheduling 1

D Briskorn 1

2

and JY-T Leung

2

Universita¨t Siegen, Siegen, Germany; and University Heights, Newark, NJ, USA

This paper focuses on a machine scheduling problem having applications in truck scheduling at transshipment terminals. Jobs increase and decrease, respectively, the level of a central inventory. Naturally, jobs decreasing the inventory level can be processed only if the level of the inventory is high enough not to drop below zero. We consider the problem to find a schedule for jobs such that the maximum lateness among all jobs is minimized. We develop properties of optimal solutions, lower bounds, and heuristic methods in order to find upper bounds. These are incorporated in four branch and bound algorithms that are based on fixing sequences of jobs in forward or backward direction in two different types of representations. By means of a computational study, we compare these approaches with each other in order to show their efficiency. Journal of the Operational Research Society (2013) 64, 1851–1864. doi:10.1057/jors.2012.155 Published online 6 February 2013 Keywords: machine scheduling; inventory constraints; branch and bound; minimization of maximum lateness

1. Introduction In this paper, we consider a problem that has originally been introduced by Briskorn et al (2010) and which is to schedule jobs non-pre-emptively on a single machine subject to inventory constraints. Jobs increase and decrease, respectively, a centralized inventory’s level. We do not allow negative inventory levels. Consequently, a job decreasing the level can only be started if the inventory level is high enough for the inventory level not to drop below zero. While in Briskorn et al (2010) various objectives have been considered, we focus on the minimization of maximum lateness with regard to job-dependent due dates here. The motivation arises in transshipment terminals’ environments when trucks arrive in order to deliver or pick up transportation units, for example containers. Each truck either delivers or picks up a certain number of units. Naturally, a truck can pick up a given number of units only if the inventory level is sufficiently high. In the terminology of our scheduling problem, we may associate trucks with jobs. 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 

Correspondence: D Briskorn, Lehrstuhl fu¨r Quantitative Planung, Universita¨t of Siegen, Ho¨lderlinstr. 3. Siegen NRW 57068, Germany. E-mail: [email protected]

minimum makespan project schedule considering (standard) precedence constraints and inventory constraints is a generalization of the well-known Resource Constrained Project Scheduling Problem, which is known to be strongly NP-hard. 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 goods or pick up goods. The model assumes that the terminal has two gates. At the first gate, trucks are unloaded and at the second gate trucks are loaded. Boysen et al (2010) show that minimizing makespan is strongly NP-hard even if all processing times are equal. Chen and Lee (2009) consider a similar problem where the pickup truck for each single item is predetermined, that is, goods are not interchangeable. This variant is proven to be strongly NP-hard. Then, an approximation algorithm and an exact B&B algorithm are presented. Moreover, heuristics for this problem are presented in Chen and Song (2009). Boysen (2010) presents a scheduling problem for trucks at a transshipment terminal where items must not be stored at the terminal but have to be picked up immediately. The problem is tackled by an exact dynamic programming procedure and a simulated annealing algorithm. 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. Clearly, there is a huge variety of problem settings for the scheduling of trucks at transshipment terminals.

1852

Journal of the Operational Research Society Vol. 64, No. 12

Boysen and Fliedner (2010) provide a comprehensive overview of existing literature and introduce a unifying notation enabling us to fully specify a problem setting. In Briskorn et al (2010), the problem at hand has been introduced and its computational complexity has been determined. Problem versions with objective to minimize maximum lateness and total completion time have been proven to be strongly NP-hard. In Briskorn et al (2011), exact approaches for the problem version with objective to minimize total weighted completion time have been developed. It has been shown that there is quite some potential in solving the problem optimally if the approaches are customized in order to make use of the problem’s structure. In this paper, we complement this stream of research by tackling the problem version with objective to minimize maximum lateness. Note that in scheduling theory minimization of maximum lateness and minimization of total completion time are the easiest objectives besides minimization of makespan, which is trivial in this setting. This paper is organized as follows. In Section 2, we formalize the problem in terms of machine scheduling problems and derive optimality properties. In Section 3, we develop the B&B algorithm and its components. We finally come up with four different B&B algorithms, each having its own individual merits and shortcomings. The computational study comparing these algorithms is provided in Section 4. We conclude the paper in Section 5.

2. The problem 2.1. Problem definition The problem at hand can be defined as follows. We are given a set J, |J| ¼ n, of jobs where each job jAJ is specified by processing time pj, due date dj, and inventory modification dj. The processing time pj of job j is the total time j occupies the machine while being processed. Jobs are available for processing at time zero, and once started a job must be completed without interruption. A job’s due date gives a point of time when it should be completed. However, each job can be completed before or after its due date. The inventory modification dj of job j specifies the alteration of the inventory level during processing of j. We refer to jobs having positive and negative inventory modification as positive jobs and negative jobs, respectively, in the following, and denote the corresponding subsets of jobs as J þ with |J þ | ¼ n þ and J with |J| ¼ n. Without loss of generality, we assume that processing times, due dates, and inventory modifications are integers. An initial inventory level I0X0 is given that specifies the inventory level at time zero. Consequently, we refer to the inventory level after the kth job as Ik. Hence, for a given

I

σ

(1,4,+4)

(2,3,-2)

d1

d3

(3,5,-1)

d2

Figure 1 Example for feasible schedule with I0 ¼ 0.

P sequence s of jobs we have Ik ¼ I0 þ kl ¼ 1ds(l), where s(l) is the lth job in s. We say a schedule is a sequence of all jobs in J. A schedule is called feasible if the inventory level is nonnegative after completion of each job. Completion time Cj of job j can be determined by adding total processing time of preceding jobs to the processing time of this very job. Lateness of each job j, then, is given by Cjdj. The problem is to find a feasible schedule that has minimum maximum lateness of jobs among all feasible schedules. Figure 1 provides a Gantt Chart for a feasible schedule with three jobs specified by (j, pj, dj) in the lower part. In the upper part, the inventory level curve is displayed. We assume a continuous and constant inventory modification during each job’s processing and empty initial inventory. Note that since I0 ¼ 0 the only positive job 1 must be scheduled first. Then, as far as feasibility is concerned we can schedule the negative jobs in an arbitrary order. However, considering due dates d2 and d3 of jobs 2 and 3, switching 2 and 3 would yield a better schedule. We denote this problem by extending the well-known three-field notation, see Graham et al (1979), as proposed in Briskorn et al (2010) as 1|inv|Lmax. In Briskorn et al (2010), 1|inv|Lmax has been proven to be strongly NP-hard even if pj ¼ 1 and dj ¼ 1 for each jAJ. If, in addition, dj ¼ d for each jAJ, then the problem still is ordinary NP-hard. Note that since maximum lateness is a regular objective and we do not consider release dates we can restrict ourselves to non-pre-emptive schedules with no idle time. Conveniently, we can fully specify such a schedule by the sequence of jobs. With regard to the applications, it is not hard to motivate due dates. The first of the reasonings focuses on the shipper’s point of view, while the second one focuses on the perspective of the terminal manager. First, for each truck a route (eg, covering a whole day) may have been determined by the dispatcher responsible for this very truck. Therefore, reaching the terminal under consideration, being loaded or unloaded and leaving for the next destination is only part of this route. In order to meet appointments at further destinations, the truck should be able to leave the terminal under consideration on time. Then, the latest point of time that enables the truck to reach the next destination on time may be considered as

D Briskorn and J Leung—Minimizing maximum lateness of jobs in inventory constrained scheduling

a due date. In particular, pickup trucks should leave not later than the assigned due dates since the goods picked up at the terminal under consideration are to be delivered somewhere else. Second, trucks having arrived at the terminal and waiting to be served means money tied up while the investment (the truck itself and—possibly—its load) is not being used effectively. Thus, the shippers may charge the terminal’s manager for long waiting times, which leads to the manager’s objective to serve each truck within a given time window (depending on its arrival time). Then, the due date considered in this paper simply specifies the end of this time window. Obviously, the problem setting is rather stylized and lacks some characteristics that can be found in real-world environments. For example, we assume trucks to be available right at the beginning of the planning horizon. This of course does reflect real-world conditions only in very few cases. Usually, trucks arrive throughout the planning horizon. However, note that despite the increasing usage of telematics services many—in particular smaller—shipping companies do not use them. And even if up-to-date technology is used estimated arrival times of trucks are still unreliable to a certain extent. A common approach to tackle this issue is the rolling horizon strategy. Here, at a certain point in time the problem at hand is solved for those trucks that have arrived at the terminal. Trucks being on their way are not taken into account. This procedure is repeated either after a certain time interval or triggered by a certain event. Clearly, each time the procedure is executed the set of trucks having arrived at the terminal may have changed. Note that it may happen that the procedure is executed while a truck is loaded or unloaded, and even if possible it seems undesirable to reschedule this truck to proceed later. However, it is not hard to incorporate a truck being currently loaded or unloaded and, thus, occupying the gate for a while into our problem setting. A further restriction in this paper is the assumption that the inventory’s capacity is infinite or at least large enough so it will not be reached. We are aware of the fact that this is a major drawback as far as modelling of real-world applications is concerned. However, even this special case of the problem is computationally hard, see Briskorn et al (2010), and, therefore, problem instances of considerable size usually can be solved only using sophisticated methods. In this paper, we aim at developing such methods. Once we have an efficient solution procedure, we may employ it as a building block in an approach for a more general problem.

2.2. Optimality properties In this subsection, we provide optimality properties, that is, properties of at least one optimal schedule. Note that the underlying problem 1||Lmax obtained by relaxing inventory constraints can be solved by sorting jobs in non-decreasing

1853

order of dj, see Lawler (1973). This rule is known as earliest due date (EDD) order. Lemma 1 There is an optimal sequence s such that

(i) each subsequence consisting of a sequence of negative jobs followed by a sequence of positive jobs is ordered in EDD; (ii) if a positive job precedes a negative job with lower due date immediately, then switching both would result in a negative inventory level j; (iii) if a positive job j precedes another positive job j0 , then djpdj0 , pjppj0 , or djXdj0 ; and (iv) negative jobs are ordered in EDD.

Proof In order to prove (i), we consider a feasible subsequence consisting of a sequence of negative jobs followed by a sequence of positive jobs. It is easy to see that in both subsets the negative jobs and the positive jobs can be assumed to be in EDD order. Now, assume that the last negative job’s due date is larger than that of the first positive job. Then, switching these jobs yields a feasible schedule, which cannot have a larger maximum lateness. We can prove (ii) and (iii) by contradiction using a simple interchange argument. Note that in both cases Ik does not drop below zero for any 0pkpn. For the proof of (iv), consider two jobs j ¼ s(k), jAJ and s(k0 )AJ, ko k0 , such that ds(k)4 ds(k0 ). Then, we can insert j immediately after j0 without modifying the sequence of all jobs. Postponing a negative job cannot increase the inventory level after any position of the schedule. Moreover, using the basic argument in Lawler (1973) it is easy to see that the new schedule cannot have larger maximum lateness than the old one. & Note that (i) and (iv) in Lemma 1 imply that there is an optimal schedule such that each negative job j is followed only by jobs having no smaller due date. We can derive two types of predetermined orders for pairs of jobs from Lemma 1. First, we consider global orders for pairs of jobs. Here i!!j means that there is an optimal schedule where i precedes j. Second, we consider local order for pairs of jobs. Here, i!j means that there is an optimal schedule where i precedes j if i and j are scheduled consecutively. Concluding from Lemma 1, we have i!!j if K K

j is a negative job and dipdj or both are positive jobs and dipdj, pippj, and diXdj (one of them strictly unequal).

Furthermore, we have i!j if i!!j holds or both are positive jobs and dio dj.

1854

Journal of the Operational Research Society Vol. 64, No. 12

3. Branch and bound algorithms We have to customize several components of the B&B algorithms regarding the problem to be tackled. First, we have to decide how to derive subproblems from the problem we consider in each step. We develop four different strategies. When deriving subproblems, dominance rules may help to reduce the number of subproblems created without preventing us from finding an optimal solution. We outline the branching decisions and dominance rules we apply in Section 3.1. Second, we have to design mechanisms in order to obtain lower bounds and upper bounds. These components are considered in detail in Section 3.2. Third, we have to decide in which order nodes of the B&B tree are explored. We restrict ourselves to the best bound strategy, that is, we examine the node having the lowest associated lower bound first.

3.1. Branching We distinguish between branching strategies based on two different representation schemes for solutions.

3.1.1. Explicit branching. As mentioned in Section 2.1, we can specify a solution by a sequence of jobs. Consequently, we can derive a subproblem of our instance by fixing a job to a certain position of the sequence. More precisely, we consider two variants of this strategy where we fix an unscheduled job to the first open position or to the last open position, respectively. We refer to these strategies as EX-FOR and EX-BACK since we fix jobs in a forward and backward, respectively, direction in an explicit representation of solutions. A specific node of the B&B tree, then, represents a sequence sf fixed to the first k, kX0, positions of the sequence, a sequence sb fixed to the last l, 0plpnk, positions of the sequence, and sets J^þ , J^þ  J þ , and J^ , J^  J  , of unscheduled positive jobs and unscheduled negative job, respectively. In order to keep the notation as simple as possible, we will use sf and sb as both the sequence of jobs and the underlying set of jobs in this sequence in the following. Note that taking into account branching only for EX-FOR and EX-BACK we have sb ¼ | and sf ¼ | in each node. In Section 3.2.1, we provide methods to fix jobs to positions of the sequence by means different from branching. Hence, we may have sba| and sfa| in nodes. Each job in J^þ [ J^ is a candidate for branching. Nevertheless, for both strategies, EX-FOR and EX-BACK, we can reduce the set of branching candidates. Using EX-FOR, we fix a job to position k þ 1 of the sequence. In order to qualify as a branching job, a job must imply feasibility of the resulting sequence, that is, Ik þ djX0 must hold. Moreover, we take into account global orders and local orders of pairs of jobs according to Lemma 1.

That is a job j can be assigned to position k þ 1 if there is no job i in J^þ [ J^ [ sb such that i!!j and for the last job i in sf we do not have j!i. Using EX-BACK, we fix a job to position n1 of the sequence. We can reduce the set of branching candidates strictly analogue to what has been described for EX-FOR. Note that we determine the jobs completion time and, therefore, its lateness by fixing it to position n1. Therefore, a job will not be considered a candidate for branching if the implied lateness exceeds a given upper bound for the optimum objective value. Branching as described above clearly yields subproblems being instances of 1|inv|Lmax themselves. For a node and corresponding sf, sb, J^þ , and J^ the instance is specified by the sets J^þ , and J^ ofP positive and negative jobs and initial inventory level I0 þ j2sf dj .

3.1.2. Implicit branching. As an alternative to the explicit branching, we make use of an implicit representation specifying the sequence of positive jobs only. As outlined in Section 2.2, we can assume negative jobs to be ordered according to EDD order. Moreover, in Briskorn et al (2009), it is shown that if a sequence of positive and a sequence of negative jobs is given, then we can find the optimal corresponding schedule in linear time. Here, since the negative jobs can be assumed to be in EDD order we say that a schedule corresponds to a sequence s þ of positive jobs if each job i preceding job j in s þ precedes j in the schedule. We can describe the method for finding the optimal schedule corresponding to a given sequence s þ as follows. In each step, we consider the last unscheduled positive job and the last unscheduled negative job. If the negative job’s due date is not smaller than that of the positive one or the positive job cannot be feasibly scheduled in the last free slot of the schedule, then we schedule the last negative job in the last free slot. Otherwise, we schedule the last positive job in the last free slot. Hence, using the linear time method to merge both sequences we can represent each solution by the implied sequence of positive jobs. Note that a sequence of positive jobs seems to be superior to a sequence of all jobs as representation. Evaluation, that is, checking feasibility and determining the objective value, can be done in linear time for both types of representation. However, using sequences of positive jobs we clearly have a smaller search space. Note that the search space may be smaller by a factor that is exponential in the input size. Using sequences of positive jobs as representation, we can derive a subproblem of our instance by fixing a positive job to a certain position of s þ . More precisely, we consider two variants of this strategy where we fix a positive job to the first open position or to the last open position of s þ , respectively. We refer to these strategies as IM-FOR and IM-BACK since we fix positive jobs in a forward and

D Briskorn and J Leung—Minimizing maximum lateness of jobs in inventory constrained scheduling

backward, respectively, direction in an implicit representation of solutions. A specific node of the B&B tree represents a sequence s þ , f fixed to the first k, kX0, positions of the sequence of positive jobs, a sequence s þ ,b fixed to the last l, 0plpn þ k, positions of the sequence of positive jobs, and the set J^þ , J^þ  J þ , of unscheduled positive jobs. Each positive job in J^þ is a candidate for branching. Again, we can reduce the set of branching candidates by accounting for orders of pairs of jobs according to Lemma 1. As opposed to explicit branching, we cannot consider local orders since the sequence of positive jobs does not directly specify immediate predecessors and successors of jobs. Nevertheless, we are able to consider global orders, and therefore job j qualifies as a branching job if fixing j to the first (last) open position does not violate any global order. Note that each sequence s þ of positive jobs has at least one corresponding feasible schedule and, thus, we do not have to take feasibility issues into account when determining the set of branching candidates. Up to now, the question remains whether it is possible to derive subproblems being instances of 1|inv|Lmax with a smaller number of jobs involved from s þ ,f and s þ ,b as we did in Section 3.1.1 for sf and sb. This issue is addressed in the following. For a given node of the B&B tree and implied sequences s þ ,f and s þ ,b and the set J^þ , J^þ  J þ , of unscheduled positive jobs we create a positive dummy job j with pj  ¼

X j2J^þ

pj ; dj  ¼

X

  dj ; and dj ¼ min dj jj 2 J^þ

j2J^þ

and consider a sequence s þ of positive jobs involving j defined as ^þ ¼ sþ;f  j   sþ;b s where 1 is the concatenation operator for two sequences. Intuitively speaking, we replace J^þ by a single job j , which has a priority value in terms of EDD equalling the highest priority among jobs in J^þ . We apply the merge algorithm ^þ and interpret j as a sequence of jobs in J^þ in EDD to s afterwards. It is not hard to see that this gives us a feasible solution s to the underlying problem and thus provides an upper bound. Now, let i ¼ s (k) be the first job from J^þ in s and let 0 i ¼ s(k0 ) be the first job in s þ , b. In the following, we say that a sequence s corresponds to a pair (s þ , f, s þ , b) if there is a sequence s þ of positive jobs starting with s þ , f and ending with s þ , b such that s corresponds to s þ . The following lemma states that we can fix all jobs in positions 1, . . . , k1 and k0 , . . . , n and consequently restrict ourselves to scheduling the remaining jobs in positions k, . . . , k0 1.

1855

Lemma 2 There is an optimal sequence s0 corresponding to (s þ ,f, s þ , b) such that s0 (l) ¼ s (l) for each lA{1, . . . , k1, k0 , . . . , n}.

Proof We first show that there is an optimal schedule such that the set of positive jobs in positions 1 to k1 and the set of positive jobs in positions k0 to n equal s þ , f and s þ , b, respectively. Consider an optimal schedule s0 not fulfilling the property above. Then, at least one of 1, 2, 3, and 4 is applicable.

1. The set I þ of positive jobs in positions k0 , . . . , n is a proper superset of s þ , b. Then, there is a set I  of negative jobs which precedes s þ , b(1) in s0 and follows s þ , b(1) in s . Owing to our algorithm all jobs in I  not  þ ,b can feasibly precede s (1) or min dj jj 2 I Xdsþ;b ð1Þ . In the first case, s0 cannot be feasible and in the second case we can delay each job in I such that it is scheduled after s þ , b(1) without increasing the objective value. 2. The set I þ of positive jobs in positions k0 , . . . , n is a proper subset of s þ , b. Then, there is a set of negative jobs I which follows s þ , b(1) in s0 and precedes s þ , b(1) in s . Owing to our algorithm     max dj j j 2 I  o min dj jj 2 sþ;b ; see also Lemma 1, and therefore we can move all jobs of I before s þ , b(1) by a sequence of pair-wise interchanges. 3. The set I þ of positive jobs in positions 1, . . . , k1 is a proper superset of s þ , f. Then, there is a set of negative jobs I which follows the first job from J^þ in s0 and precedes the first job from J^þ in s . Owing to our algorithm and the construction of j     max dj jj 2 I  o min dj jj 2 sþ;b [ J^þ ; see also Lemma 1, and therefore we can move all jobs of I before the first job from J^þ by a sequence of pairwise interchanges. 4. The set I þ of positive jobs in positions 1, . . . , k1 is a proper subset of s þ , f. Then, there is a set of negative jobs I, which precedes the first job from J^þ in s0 and follows the first job from J^þ in s . Owing to our algorithm and the construction of j , there must be at least one positive job j0 scheduled after all jobs in I such that   dj 0 p min dj jj 2 I  : Then, we can move all jobs of I in EDD right after j 0 without increasing the objective value and it is easy to see that the resulting schedule must be feasible.

1856

Journal of the Operational Research Society Vol. 64, No. 12

From the above, it follows that there is an optimal schedule such that the set of jobs in positions 1 to k1 and the set of jobs in positions k0 to n, respectively, equal the corresponding sets in s . Then, due to the correctness of the merge algorithm it is easy to see that there is an optimal schedule coinciding with s in slots 1 to k1 and k0 to n. & The problem to schedule the remaining jobs in positions k, . . . , k0 1 is obviously an instance of 1|inv|Lmax, and thus the implicit branching scheme is suitable to obtain smaller problem instances recursively.

3.2. Bounds As seen in the previous subsection, we can think of a subproblem obtained by one of the branching strategies presented in Section 3.1 as an instance of 1|inv|Lmax. Therefore, we restrict everything in the subsection at hand to such instances. In Section 3.2.1, we propose several techniques to derive lower bounds. Section 3.2.2 outlines two ways to fix jobs to positions based on information provided by lower bounds. Finally, in Section 3.2.3 we propose methods to yield feasible solutions and, thus, upper bounds.

3.2.1. Lower bounds. Clearly, 1||Lmax is the relaxation of 1|inv|Lmax derived by dropping inventory constraints. Solving the corresponding instance of 1||Lmax by ordering jobs according to EDD yields a possibly non-feasible schedule sEDD. The objective value provided by sEDD clearly is a lower bound, namely, lb1. If sEDD is feasible, then it is optimal as well. However, if it is not feasible, then we can further strengthen lb1 as follows. Consider a job j ¼ sEDD(k) such that Iko 0. Note that there is at least one such job if sEDD is infeasible. Let Jj , Jj  J , and Jj, JjDJ þ , be the set of jobs scheduled in slots 1, . . . , k in sEDD and the set of positive jobs scheduled in positions k þ 1, . . . , n of sEDD, respectively. Let Z be the optimal objective value, Cj be the completion time of j in sEDD, and P j be the minimum total processing time among subsets of J j such that the total inventory increment of the subsets is at least Ik. Lemma 3 For each job j, j ¼ sEDD(k), such that Iko 0 we have ZXCj þ Pjdj. Proof Let i be the last job of Jj in an arbitrary feasible schedule s. Clearly, Ci0 XCj where Ci0 denotes i0 s completion time in s. Also, i ¼ s(k0 ) with k0 4 k since I 0k 0 o0 otherwise, where I 0k 0 denotes the inventory level after slot k0 according to s. Clearly, there is a set J^ , J^  J j , of k0 k jobs scheduled before i having total inventory modification of at least Ik. Note that J^ \ Jj ¼ . Clearly, the total

processing time of jobs in J^ must be at least Pj. Therefore, Ci0 XCj þ Pj. Since dipdj we have lateness Ci0  di XCj þ Pj  di XCj þ Pj  dj of job i and, therefore, maximum lateness of at least Cj þ Pjdj. & Determining P j for given k and sEDD is equivalent to the well-known binary knapsack problem. We, first, roughly sketch the analogies. Jobs in Jj correspond to items. A job’s processing time and inventory modification corresponds to the item’s profit and weight. Now, our problem is to select a subset of items having at least a given minimum total weight such that total profit is minimized. This corresponds to choosing the items not to be put into the knapsack, which obviously is equivalent to choosing the items to be put into it. In order to limit the effort spent on finding lower bounds, we propose the following lower bound lb2. Consider job j ¼ sEDD(k). Let qj ¼ min{pi|iAJj} if Iko 0 and let qj ¼ 0 otherwise. Then, lb2 ¼ max{Cj þ qjdj|jAJ} is a lower bound for Z. This easily follows from qjpPj, which is obviously true. On the other hand, lb2 is stronger than lb1, meaning that there are instances where lb24 lb1 and can be easily derived in linear time. Let Pj be optimum objective value to the continuous version of the knapsack problem described above. We  propose lower bound lb3 ¼ max Cj þ maxfPj ; qj g dj jj 2 Jg for Z. Since Pj pPj it is clear that lb3pZ. The computational complexity to derive lb3 is determined by O(n log n) to solve the LP relaxation of the knapsack problem. Finally, we propose lower bound lb4 ¼ max{Cj þ Pjdj|jAJ} according to Lemma 3. We use the combo algorithm developed by Martello et al (1999) in order to solve the Knapsack instances. Although published in 1999, it still seems to be the state of the art; see Martello et al (2000) and Pisinger (2005). Comparing the proposed lower bounds we can state that lb1plb2plb3plb4. In order to limit the computational burden to compute lower bounds, we propose to abort the procedure to find minimum qj, Pj , and Pj, respectively, whenever the smallest Cj þ qjdj, Cj þ Pj  dj , and Cj þ Pjdj found so far is strictly smaller than the bestknown solution value. Then, clearly we cannot use the contribution of job j to the lower bound to prune the current node of the B&B tree. Finally, we provide an example to illustrate the lower bounds applied. Consider the problem instance specified by I0 ¼ 0 and Table 1. Obviously, sEDD ¼ (1, 2, 3, 4, 5) and lb1 ¼ 0. Note that I1 ¼ 5, I2 ¼ 3, and IkX0 for k ¼ 3, . . . , 5. For both, job 5 is the job having smallest processing time among all following positive jobs. Hence, lb2 ¼ max{0 þ 2, 1 þ 2, 0 þ 0, 2 þ 0, 1 þ 0} ¼ 2. The knapsack instances corresponding to job 1 and 2 encompass jobs set {2, 3, 4, 5} and {3, 4, 5}, respectively.

D Briskorn and J Leung—Minimizing maximum lateness of jobs in inventory constrained scheduling

Table 1 Example for lower bounds j

1

2

3

4

5

pj dj dj

1 1 -5

3 5 2

4 8 3

9 19 9

2 20 1

The most efficient, that is, the job having maximum dj/pj, is job 4. Hence, lb3 ¼ max{0 þ 5, 1 þ 3, 0 þ 0, 2 þ 0, 1 þ 0} ¼ 5. Finally, solving the binary Knapsack problem we obtain lb4 ¼ max{0 þ 7, 1 þ 4, 0 þ 0, 2 þ 0, 1 þ 0} ¼ 7.

3.2.2. Fixing jobs based on the EDD schedule and LBs. As outlined in Section 3.2.1, we derive lower bounds based on the EDD schedule sEDD, which obviously may not be feasible. Nevertheless, it may provide properties of optimal solutions. Lemma 4 If there is no negative inventory level after each of the first k positions of sEDD, then there is an optimal schedule, which coincides with sEDD in the first k positions.

Proof We first show that there is an optimal schedule such that the set of jobs in the first k positions equals the corresponding set J in sEDD. Consider an arbitrary optimal schedule s. Let job  then we are j ¼ s(k) be the last job out of J in s. If k  jJj,   jobs from finished. If k4jJj, then there is a set of k  jJj  JnJ scheduled before j in s. Let the set of these jobs be ^ Consider the last negative job i in J. ^ We denoted by J. modify s by removing i from its position and inserting it into position k. This move yields a feasible schedule since delaying negative jobs is feasible. Moreover, since diXdj the maximum lateness cannot be increased. By repeating this procedure, we can find an optimal schedule s0 without a ^ negative job in J. Henceforth, we consider an arbitrary optimal schedule s0 such that J^ contains only positive jobs. We apply the same move as above to jobs in J^ until J^ ¼ |. Note that for each job i we have diXdj, and therefore the maximum lateness cannot be increased. Note that the resulting schedule s00 may be infeasible. However, no negative inventory level occurs after the kth job since s00 coincides with s in positions k þ 1, . . . , n. Also, according in s00 , we  jobs equals the have IjJj X0 as the set of the first jJj EDD corresponding set in s and we assume that IjJj X0  þ 1; . . . ; k  1 we have according to sEDD. In positions jJj a sequence of positive jobs followed by a sequence of negative jobs and, thus, due to IjJj X0 and IkX0 no negative inventory level can occur here. In summary, inventory levels are non-negative after position l.

1857

Now, we can rearrange jobs in positions 1, . . . , l in EDD order. This obviously cannot increase the maximum lateness and, moreover, we assume that this order yields non-negative inventory levels up to position l. & Lemma 4 allows us to fix all jobs that can be feasibly scheduled in EDD order at the beginning of sEDD. Clearly, this reduces the maximum depth of the search tree. We refer to the technique to fix jobs as FIX-JOB-AT-START. It is easy to see using basic arguments as applied before that we can fix positions l, . . . , n of sEDD where l is the minimum position such that all jobs in positions l, . . . , n are negative. In addition, we may be able to fix further negative jobs to positions. Given a LB lb we fix the negative job j having the largest due date among those not yet being fixed to the last open position if the implied lateness Lj of j does not exceed lb. Clearly, the lower bound of the resulting subproblem with fixed j does not have an increased lower bound. Moreover, in each schedule delaying j yields a feasible schedule. We refer to this technique as FIX-NEG-AT-END.

3.2.3. Upper bounds. In the following, we propose methods to derive upper bounds. Each of them uses a backward scheduling technique, that is, we assign jobs to positions n, n1, . . . , 2, 1. The first upper bound ub1 is based on the assumption that positive jobs are ordered in EDD. Since negative jobs can be assumed to be in EDD order, we have two ordered subsets, then, and can apply the linear time method to merge both sequences introduced in Section 3.1.2. The obtained upper bound is referred to as ub1. Clearly, if a lower bound lb is given, then we have more freedom choosing the last job among those not fixed yet. Consider the step where we assign a job to position k. First, if a negative job that is not scheduled yet can be fixed to k without its implied lateness exceeding lb, then we can fix it to k. Second, if the next negative job’s lateness exceeds lb when scheduled in k, then we consider positive jobs to be scheduled in k. A positive job j can be feasibly scheduled in k if spIk. If there is more than one such job, then we choose the one having the largest processing time, lowest inventory modification, or largest relation pj/dj of processing time and inventory modification. Choosing the one having largest processing time and minimum inventory modification is motivated by minimizing the completion time of the job scheduled in position k1 and maximizing Ik1, respectively. Considering the relation of processing time and inventory modification accounts for the trade-off between both. In preliminary tests, choosing the job having the largest processing time proved to be the most efficient in terms of the overall run time. Third, if no job can be scheduled in k without its lateness exceeding lb, then we

1858

Journal of the Operational Research Society Vol. 64, No. 12

decide as in a step of the merge algorithm. If the next positive job (in backward EDD perspective) can be feasibly scheduled in k and its due date is larger than the next negative one’s (in backward EDD perspective), then schedule the next positive job in k. Otherwise, schedule the next negative job in k. The corresponding upper bound is referred to as ub2.

3.3. Analysis of approaches and preliminary results We proposed four basic schemes in Section 3.1 and several bounding and fixing techniques in Section 3.2. In the following, we shortly analyse the advantages and drawbacks of the four schemes. In addition, we summarize results of preliminary tests comparing different bounding techniques. As mentioned in Section 3.1, subproblems resulting from all four approaches can be specified as instances of 1|inv|Lmax themselves. Therefore, lower bounds lb1 to lb4 can be derived for all four schemes. Clearly, the number of derived subproblems for each node of the search tree is a figure of interest when evaluating the performance. We expect the number of derived subproblems to be smaller for EX-BACK than for EX-FOR since the completion time of fixed jobs is larger when EX-BACK is applied, and therefore the lower bounds derived tend to be higher. However, while we can make use of FIX-NEG-AT-END for EX-FOR, we cannot do so easily for EX-BACK. Note that FIX-NEGAT-END conflicts local orders of jobs as proposed in Section 2.2, and therefore we can make use of either FIX-NEG-AT-END or local orders but not both. In preliminary tests, the version of EX-BACK using local orders proved to be superior in terms of run time. However, this leaves EX-BACK with the drawback that we cannot fix negative jobs at the end, which obviously reduces problem complexity. Comparing implicit branching strategies with explicit ones we found the following. Clearly, the search space is smaller using implicit branching strategies. This should lead to a smaller number of nodes that have to be explored during the optimization process. However, the computational burden per node should be higher using the implicit branching strategies due to the additional effort for decoding the implicit representation. As mentioned in Section 3.2.1, there is an obvious tradeoff between quality of lower bounds lb1 to lb4 and the corresponding computational burden. In addition, we expect a trade-off between quality of the derived upper bound and computational burden for upper bounds ub1 and ub2. In preliminary tests, lb4 and ub2 clearly proved to be most efficient. In conclusion, in all that follows we restrict ourselves to the following variants of the proposed B&B algorithms.

K

K

K

K

EX-FOR with local orders, global orders, lb4, ub2, FIX-NEG-AT-END, and FIX-JOB-AT-START EX-BACK with local orders, global orders, lb4, ub2, and FIX-JOB-AT-START IM-FOR with global orders, lb4, ub2, FIX-NEG-ATEND, and FIX-JOB-AT-START IM-BACK with global orders, lb4, ub2, FIX-NEG-ATEND, and FIX-JOB-AT-START

Having a closer look at the forward-oriented approaches, we can see that employing the techniques specified above both approaches strongly resemble each other. Note that using FIX-JOB-AT-START fixes a sequence of jobs such that the first non-fixed job in sEDD is a negative one. Let this job be j. In EX-FOR, we decide about which job to assign to the first open position k. Since j is the only negative job to be considered assignable to k due to EDD order of negative jobs and j cannot be feasibly assigned to k, we will create subproblems by assigning positive jobs to k only. This strongly coincides with IM-FOR.

4. Computational results We carried out our computational study using a 2.83 GHz Intel Core2 Quad CPU Q9950 machine with 3.5 GBs of RAM running Microsoft Windows Server 2003. Test instances can be distinguished by the fraction of jobs being negative jobs. First, two-thirds of the jobs are negative (‘2-1’); second, one-half of the jobs are negative (‘1-1’); third, one-third of the jobs are negative (‘1-2’). We created instances with 30, 60, 90, 120, 150, 180, 210, and 240 jobs. Each instance is created by randomly choosing pj for each jAJ from integer values in [1, 10]. Inventory modifications of negative jobs and positive jobs, respectively, were drawn from [20, 1] and [1, 20] for ‘11’, from [10, 1] and [1, 20] for ‘21’, and from [20, 1] and [1, 10] for ‘12’. Note that we draw values from ranges depending on the fraction of negative jobs in order to level total amount of delivery and total amount picked up. Initial inventory has been drawn from [1, 20], [1, 10], and [1, 20] for ‘11’, ‘21’, and ‘12’, respectively. Due dates of positive jobs have been drawn from integer values in [0, Cmax]. We expect the due dates of negative jobs to have an impact on the run times of our algorithms. Note that if due dates of negative jobs tend to be large we likely can fix jobs according to FIX-NEG-AT-END and FIX-JOB-ATSTART more often than if they tend to be small. This is why we create two sets of instances. For the first set, referred to as ‘Cmax’, due dates of negative jobs are drawn from integer values in [0, Cmax]. For the second one, referred to as ‘Cmax/2’, due dates of negative jobs are drawn from integer values in [0, Cmax/2]. If—after creating all jobs—total inventory modification induces a negative final inventory level, then we add the

D Briskorn and J Leung—Minimizing maximum lateness of jobs in inventory constrained scheduling

1859

Table 2 Results for ‘1-1’ and ‘Cmax’ n

rep

FOR

BACK

1

5

60

1800

1

5

60

1800

30

EX IM

0.04/49 0.04/49

0.05/50 0.04/50

— —

— —

0.05/48 0.01/50

0.13/49 —

0.19/50 —

— —

60

EX IM

0.16/43 0.17/43

0.64/45 0.63/45

6.16/45 6.16/45

147.78/46 147.73/46

0.14/44 0.11/46

0.57/45 0.22/50

5.34/46 —

112.38/47 —

90

EX IM

0.24/39 0.26/39

0.92/42 0.93/42

9.77/42 9.81/42

256.15/43 256.30/43

0.28/37 0.25/40

1.11/40 0.78/45

9.70/43 1.91/50

178.57/46 —

120

EX IM

0.22/40 0.22/40

1.02/40 1.02/40

12.05/40 12.04/40

326.67/41 oom

0.20/41 0.19/42

0.88/42 0.83/42

9.68/42 6.59/46

263.49/43 12.46/50

150

EX IM

0.45/28 0.46/28

2.07/30 2.07/30

20.95/35 21.60/34

oom oom

0.43/30 0.42/31

1.77/36 1.60/38

14.40/39 11.60/41

364.21/40 121.25/49

180

EX IM

0.19/41 0.19/41

0.92/41 0.91/41

9.83/42 9.93/42

oom oom

0.23/39 0.23/39

1.04/40 1.10/40

10.90/42 10.71/42

289.77/42 82.93/48

210

EX IM

0.40/30 0.41/30

1.81/33 1.80/33

18.86/35 19.33/35

oom oom

0.35/33 0.34/34

1.62/35 1.62/35

16.90/37 14.38/39

411.54/39 237.83/44

240

EX IM

0.28/38 0.30/38

1.20/39 1.21/39

12.81/40 13.25/40

oom oom

0.35/33 0.35/33

1.71/33 1.71/33

20.41/33 18.01/37

541.56/36 291.89/45

minimum number of positive jobs having maximum inventory modification such that the final inventory level is non-negative. In summary, each class of instances can be identified by the fraction of jobs being negative (‘1-1’, ’2-1’, or ‘1-2’), the number of jobs (‘30’, . . . , ’240’), and tightness of negative jobs’ due dates (‘Cmax’ or ‘Cmax/2’). For each of these classes, we created 50 instances. Note that in real-world instances the loading time or unloading time of jobs may correspond to the amount transported. Therefore, we consider an additional set of instances where parameters are set according to ‘11’ and ‘Cmax’. For this set also, we created 50 instances for each number ‘30’, . . . , ’240’ of jobs. In this set of instances, we set pj ¼ |dj| in order to reflect the dependency of (un)loading time and the amount transported For each class of instances, we outline results of our four algorithms with run time limited to 1 s, 5 s, 60 s, and 1800 s, respectively, in Tables 2-8. In general, we can conclude that as expected the performances of EX-FOR and IM-FOR are almost identical. This is why we will not distinguish between them in the following and refer to them as FOR. Table 2 outlines results for ‘1-1’ and ‘Cmax’. The first column gives the instance size, while the second column gives the type of representation (explict versus implicit). Columns 3-6 and 7-10 outline results achieved with

branching in forward and backward, respectively, direction. Column heads in line 2 give the run time limit. In each cell, that is for each problem size, branching direction, type of representation, and run time limit we find, first, the average run time and, second, the number of instances (out of 50) being solved optimally within the given time limit. Here, solving optimally means finding the optimal solution and proving its optimality. If all instances have been solved optimally for a given time limit, then we do not line out results for larger time limits but simply put ‘—’ in the corresponding cells. Also, we outline that our approach runs out of memory for at least one instance by ‘oom’. Although, naturally, run times tend to be higher for larger instances, this is not true in general. For example, comparing results for 150 jobs with those for 180 jobs we see that run times are lower on average for 180 jobs. Since, first, this is true independent of the actual run time limit and, second, the number of instances being solved optimally for each run time limit is larger for 180 jobs, we can conclude that there are more randomly generated ‘hard instances’ for 150 jobs pushing run times to the limit. We can see that the backward-oriented branching schemes are mostly performing better than FOR. This does not hold for problem classes having a lot of easy instances, namely, ‘180’ and ‘240’. In terms of memory usage, however, the backward-oriented branching schemes are performing better. For no class of instances EX-BACK

1860

Journal of the Operational Research Society Vol. 64, No. 12

Table 3 Results for ‘2-1’ and ‘Cmax’ n

rep

FOR

BACK

1

5

60

1800

1

5

60

1800 — —

30

EX IM

0.00/50 0.00/50

— —

— —

— —

0.00/50 0.00/50

— —

— —

60

EX IM

0.11/45 0.11/45

0.36/47 0.35/47

1.95/49 2.02/49

3.67/50 4.26/50

0.09/46 0.05/50

0.28/49 —

1.38/49 —

9.64/50 —

90

EX IM

0.13/44 0.11/45

0.53/45 0.52/45

3.97/47 3.99/47

oom oom

0.15/43 0.10/47

0.40/47 0.19/49

3.71/47 0.48/50

81.83/48 —

120

EX IM

0.24/39 0.23/40

1.04/40 1.04/40

11.00/41 11.04/41

oom oom

0.28/39 0.25/40

1.09/41 0.69/47

8.06/45 2.49/50

181.87/45 —

150

EX IM

0.21/40 0.20/41

0.89/42 0.91/42

9.70/42 9.71/42

oom oom

0.21/41 0.19/43

0.87/42 0.67/45

7.97/46 4.40/47

146.78/46 7.33/50

180

EX IM

0.23/39 0.23/39

0.97/41 0.98/41

8.83/43 8.94/43

oom oom

0.22/39 0.22/40

1.10/39 0.96/41

12.12/40 8.82/44

238.65/44 25.83/50

210

EX IM

0.30/37 0.28/38

1.20/39 1.22/39

13.31/39 13.32/39

oom oom

0.31/35 0.28/38

1.44/36 1.21/39

15.82/37 11.25/43

434.07/38 72.69/49

240

EX IM

0.29/37 0.28/37

1.32/37 1.33/37

14.83/38 14.93/38

oom oom

0.31/35 0.28/37

1.46/37 1.29/38

13.58/40 13.16/41

340.92/41 146.31/48

Table 4 Results for ‘1-2’ and ‘Cmax’ n

rep

FOR

BACK

1

5

60

1800

1

5

60

1800

30

EX IM

0.15/43 0.15/43

0.56/45 0.56/45

4.99/46 5.00/46

44.54/49 42.90/49

0.01/50 0.00/50

— —

— —

— —

60

EX IM

0.32/35 0.32/35

1.53/35 1.53/35

14.19/39 14.25/39

333.71/41 333.21/41

0.29/38 0.20/43

1.05/42 0.53/48

6.85/45 0.97/50

133.49/47 —

90

EX IM

0.45/29 0.44/30

1.93/32 1.96/32

21.02/33 21.15/33

oom oom

0.35/35 0.32/38

1.41/39 1.08/43

10.06/43 4.80/48

197.05/45 7.54/50

120

EX IM

0.27/39 0.26/39

1.15/39 1.14/39

11.29/41 11.35/41

oom oom

0.28/37 0.29/36

1.32/37 1.33/37

11.97/41 9.58/44

202.98/45 97.83/48

150

EX IM

0.45/29 0.45/29

2.06/30 2.04/31

22.99/31 22.99/31

oom oom

0.47/27 0.41/31

2.13/32 1.88/33

21.04/33 15.12/40

516.39/36 196.47/46

180

EX IM

0.57/24 0.57/24

2.56/26 2.53/26

27.94/28 27.21/28

oom oom

0.54/24 0.54/25

2.62/24 2.54/25

31.23/24 27.25/28

893.89/26 454.27/40

210

EX IM

0.45/28 0.45/28

2.21/28 2.21/28

25.36/30 25.47/30

oom oom

0.40/31 0.41/31

1.85/32 1.77/34

18.09/36 16.83/37

481.08/37 270.08/45

240

EX IM

0.44/29 0.45/28

2.12/29 2.14/29

23.26/31 23.30/31

oom oom

0.45/28 0.43/29

2.18/30 1.94/32

22.89/32 19.62/34

539.85/36 388.82/41

or IM-BACK run out of memory, while FOR do for larger instances and a run time limit of 1800. Comparing EX-BACK and IM-BACK, we can conclude that

IM-BACK never performs worse but significantly better for several problem classes. The superiority is increasing in the run time limit.

D Briskorn and J Leung—Minimizing maximum lateness of jobs in inventory constrained scheduling

1861

Table 5 Results for ‘1-1’ and ‘Cmax/2’ n

rep

FOR

BACK

1

5

60

1800

1

5

60

1800

30

EX IM

0.06/48 0.06/48

0.15/49 0.15/49

0.82/50 0.83/50

— —

0.00/50 0.00/50

— —

— —

— —

60

EX IM

0.51/26 0.51/26

2.44/26 2.43/26

27.57/29 27.55/28

493.17/39 509.01/38

0.03/50 0.04/50

— —

— —

— —

90

EX IM

0.49/26 0.49/26

2.41/26 2.41/26

28.87/26 28.87/26

833.73/27 835.03/27

0.07/47 0.07/48

0.19/49 0.17/49

0.46/50 0.61/50

— —

120

EX IM

0.67/17 0.67/17

3.32/17 3.31/17

39.68/17 39.68/17

oom oom

0.16/45 0.18/45

0.42/47 0.41/47

0.69/50 1.01/50

— —

150

EX IM

0.75/13 0.76/13

3.71/13 3.72/13

43.69/14 43.69/14

oom oom

0.20/45 0.24/44

0.36/49 0.45/49

0.41/50 0.49/50

— —

180

EX IM

0.86/8 0.86/8

4.22/8 4.22/8

50.46/8 50.45/8

oom oom

0.34/40 0.38/39

0.88/45 0.97/45

3.83/48 3.97/48

39.95/49 40.01/49

210

EX IM

0.78/12 0.78/12

3.82/12 3.82/12

45.65/12 45.64/12

oom oom

0.35/40 0.40/40

0.85/45 0.88/45

4.04/48 4.66/47

11.23/50 15.57/50

240

EX IM

0.85/9 0.84/9

4.12/9 4.12/9

49.25/9 49.24/9

oom oom

0.36/39 0.42/36

0.84/46 1.01/46

2.27/49 2.75/49

2.65/50 3.51/50

Table 6 Results for ‘2-1’ and ‘Cmax/2’ n

rep

FOR

BACK

1

5

60

1800

1

5

60

1800

30

EX IM

0.07/48 0.07/48

0.18/49 0.15/49

0.54/50 0.26/50

— —

0.00/50 0.00/50

— —

— —

— —

60

EX IM

0.15/43 0.15/43

0.69/44 0.69/44

5.03/47 5.08/47

74.60/48 74.75/48

0.00/50 0.00/50

— —

— —

— —

90

EX IM

0.36/33 0.36/33

1.73/33 1.73/33

20.52/33 20.52/33

471.57/39 oom

0.00/50 0.00/50

— —

— —

— —

120

EX IM

0.31/35 0.31/35

1.51/35 1.51/35

17.38/36 17.40/36

oom oom

0.01/50 0.01/50

— —

— —

— —

150

EX IM

0.57/22 0.57/22

2.82/22 2.82/22

33.71/22 33.72/22

oom oom

0.03/50 0.02/50

— —

— —

— —

180

EX IM

0.61/20 0.61/20

3.01/20 3.02/20

36.12/20 36.13/20

oom oom

0.05/50 0.04/50

— —

— —

— —

210

EX IM

0.63/19 0.63/19

3.11/19 3.11/19

37.31/19 37.33/19

oom oom

0.02/50 0.03/50

— —

— —

— —

240

EX IM

0.63/19 0.63/19

3.11/19 3.12/19

37.31/19 37.32/19

oom oom

0.02/50 0.02/50

— —

— —

— —

Table 3 presents results for ‘2-1’ and ‘Cmax’. In general, run times are lower than for ‘1-1’ and ‘Cmax’ and the number of instances solved to optimality in a specific

setting tends to be higher. Mostly, IM-BACK performs slightly better than FOR while EX-BACK is slightly inferior.

1862

Journal of the Operational Research Society Vol. 64, No. 12

Table 7 Results for ‘1-2’ and ‘Cmax/2’ n

rep

FOR

BACK

1

5

60

1800

1

5

60

1800

30

EX IM

0.20/43 0.18/43

0.65/45 0.65/45

3.59/48 2.82/49

39.02/49 37.71/49

0.00/50 0.00/50

— —

— —

— —

60

EX IM

0.77/12 0.77/12

3.82/12 3.82/12

43.08/16 43.48/16

1139.40/19 1137.29/20

0.16/46 0.17/46

0.25/50 0.24/50

— —

— —

90

EX IM

0.67/17 0.67/17

3.31/17 3.31/17

39.73/17 39.73/17

1128.74/19 1139.65/19

0.12/46 0.14/46

0.39/47 0.55/47

1.55/50 1.88/50

— —

120

EX IM

0.77/12 0.77/12

3.81/12 3.81/12

45.71/12 45.70/12

oom oom

0.20/43 0.23/43

0.70/44 0.73/44

1.65/50 1.76/50

— —

150

EX IM

0.72/15 0.71/15

3.52/15 3.52/15

42.07/15 42.07/15

oom oom

0.30/39 0.33/37

1.17/40 1.22/40

9.18/44 9.78/44

92.63/49 126.76/48

180

EX IM

0.66/18 0.66/18

3.22/18 3.22/18

38.46/18 38.46/18

oom oom

0.21/47 0.25/45

0.39/48 0.45/48

1.70/49 1.82/49

4.37/50 4.79/50

210

EX IM

0.68/17 0.68/17

3.32/17 3.32/17

39.65/17 39.65/17

oom oom

0.23/44 0.29/42

0.66/45 0.75/45

4.01/47 4.11/47

34.55/50 35.90/50

240

EX IM

0.78/12 0.78/12

3.82/12 3.82/12

45.65/12 45.65/12

oom oom

0.32/38 0.34/37

0.95/44 1.03/43

6.48/45 6.51/45

143.65/47 141.70/47

Table 8 Results for ‘1-1’ and ‘Cmax’ with pj=|dj| n

rep

FOR

BACK

1

5

60

1800

1

5

60

1800 — —

30

EX IM

0.00/50 0.00/50

— —

— —

— —

0.00/50 0.00/50

— —

— —

60

EX IM

0.03/49 0.03/49

0.09/50 0.10/50

— —

— —

0.05/48 0.05/49

0.21/48 0.07/50

1.65/49 —

3.71/50 —

90

EX IM

0.06/47 0.06/47

0.30/47 0.31/47

2.75/48 2.75/48

72.52/48 72.52/48

0.06/48 0.06/48

0.22/48 0.16/49

1.39/49 0.52/50

36.28/49 —

120

EX IM

0.11/45 0.11/45

0.35/48 0.36/48

1.56/49 1.57/49

4.48/50 4.61/50

0.11/46 0.12/45

0.43/46 0.49/46

4.65/47 3.59/49

47.33/49 3.82/50

150

EX IM

0.07/47 0.07/47

0.32/47 0.31/47

3.63/47 3.63/47

74.47/48 74.52/48

0.14/43 0.15/43

0.70/43 0.67/44

6.55/45 5.99/46

180.72/45 85.31/48

180

EX IM

0.08/47 0.07/47

0.33/47 0.32/47

3.63/47 3.63/47

108.47/47 108.47/47

0.10/45 0.11/45

0.50/45 0.51/45

6.01/45 5.04/46

144.20/47 81.79/48

210

EX IM

0.11/47 0.11/47

0.35/47 0.34/47

3.65/47 3.64/47

74.35/48 74.31/48

0.21/40 0.21/40

0.96/41 0.96/41

9.03/43 9.82/42

187.23/45 132.32/48

240

EX IM

0.12/45 0.12/45

0.36/47 0.37/47

2.57/48 2.57/48

oom oom

0.19/41 0.19/41

0.91/41 0.91/41

10.81/41 10.81/41

324.45/41 235.63/45

In Table 4, we see results in line with Tables 2 and 3 since our algorithms’ performance is better, here. We can conclude that performance is increasing in the fraction of

negative jobs for a given setting. This is not too surprising since the fraction of jobs we can assign in EDD order is increasing. Note, however, that increasing the fraction of

D Briskorn and J Leung—Minimizing maximum lateness of jobs in inventory constrained scheduling

positive jobs beyond a specific threshold will result in better performance as well. After all, having only positive jobs leads to EDD rule yielding an optimal schedule. For ‘1-2’ and ‘Cmax’ none of FOR and EX-BACK dominates the other one. IM-BACK, however, is never inferior and significantly better for some problem classes. Tables 5–7 present results for problem instances according to ‘Cmax/2’. As mentioned above, we created these instances in order to find instances being harder to solve. Regarding FOR, we feel vindicated. Run times and the number of instances being solved optimally is lower and higher, respectively, than for corresponding classes of instances according to ‘Cmax’. Using IM-BACK and EX-BACK, however, run times are lower than for ‘Cmax’. This may be due to a high degree of freedom once a negative job is scheduled near the end because the lower bound lb4 tends to be large, then. Again, run times for solving instances according to ‘2-1’ are smallest and ‘1-2’ are largest. The latter is significant for FOR only for the runs with largest run time limits. Note, however, that for smaller run time limits only small numbers of instances can be solved to optimality, that is, our algorithm reaches the run time limit pretty often. Run time lowering effects, namely a high fraction of negative jobs and small due dates of negative jobs, culminate in results for ‘1-2’ and ‘Cmax/2’, where each single instance is solved by EX-BACK as well as IM-BACK within 1 second. Table 8 outlines results for problem instances according to ‘1-1’ and ‘Cmax’ with pj ¼ |dj|. We can directly compare them with the results for problem instances according to ‘1-1’ and ‘Cmax’ with independent processing times and inventory modifications in Table 2. Interestingly, run times for each of the four approaches are significantly lower if pj ¼ |dj| holds. In addition, the number of instances solved to optimality is higher and the number of classes of instances for which approaches run out of memory is lower. By more thorough inspection, we found that the number of nodes of the search tree explored is much lower if pj ¼ |dj| holds. Run time per node is higher, though. Nevertheless, the advantage of using less nodes is stronger than the drawback of spending more time per node. Of course, the question is why these two effects (comparing results in Table 2 and 8) can be observed. K

It is indicated in Pisinger (2005) that binary knapsack instances are hard to solve if they are strongly j and correlated, which means that the relations pj =w pj0 /wj0 of profits and weights are close to each other for each pair of items j and j0 . Note that when computing the lower bound lb4 positive job j with load dj and unloading time pj corresponds to an item j with weight j and profit pj in the corresponding knapsack instance. w Clearly, items are perfectly correlated, then. Hence, the knapsack instance we solve in order to derive a lower

K

1863

bound is hard to solve which increases run time per node. When determining upper bound ub2, it may happen that no negative jobs can be fixed to the last open position k without increasing the current lower bound, but there is more than one positive job that can be scheduled in k without doing so, that is |Jple|4 1. We, then, decide according to a simple priority rule which job from Jple to fix to k: we choose the job having maximum processing time among jobs in Jple. However, in an unfortunate case, this may decrease the current inventory level unduly. Note that we schedule in backward direction, which is why scheduling a positive job decreases the inventory level. Decreasing the inventory level unduly may result in too little freedom to choose an appropriate job for position k1. However, if pj ¼ |dj| holds, then there is a fixed relation between processing time and reduction in inventory level. Intuitively speaking, unduly reduction of inventory level is prevented.

Note that the set of instances where we have pj ¼ |dj| has been created in order to represent a common scenario in real-world logistics. Remarkably, our approaches work better for these real-world-oriented instances than for random ones. Summarizing the computational study, we state that IM-BACK solves all but two (out of 1400) instances with up to 120 jobs within half an hour. For instances with up to 90, 60, and 30 jobs, no more than 7.5, 1.0, and 0.01, respectively, seconds on average were needed to find an optimum solution and prove its optimality. Considering the length of a planning horizon covered by a sequence of these numbers of jobs to be loaded and unloaded, respectively, the run times appear to be sufficiently small to allow for multiple runs of the approach in a higher-level solution framework.

5. Conclusion and outlook This paper presents B&B algorithms for a concise scheduling problem concerning the scheduling of jobs to be loaded and unloaded, respectively, at a transshipment terminal. Jobs are assumed to have due dates and the maximum lateness among jobs is to be minimized. We present theoretical foundations for partial orders of jobs in an optimum schedule in order to reduce the search space. Furthermore, we provide lower bounding and upper bounding techniques and, on top, ideas for fixing jobs to positions in the sequence based on insights from the EDD schedule. These theoretical results are employed in B&B frameworks operating on two different representations of schedules, namely, sequences of all jobs and sequences of positive jobs. Branching is done by fixing jobs at the end or at the beginning of the respective sequence.

1864

Journal of the Operational Research Society Vol. 64, No. 12

Concluding our computational study, EX-BACK performs best. Often, EX-BACK reaches lowest average run times and largest number of instances solved to optimality within a given time span. If another approach outperforms EX-BACK, then the difference is not significant. Moreover, the backward-oriented approaches prove to be more robust in terms of memory requirements. For none of the tested instances backwardoriented approaches run out of memory within a run time limit of 1800 s. We can solve each instance with up to 60 and 90 jobs in less than 60 and 1800, respectively, seconds. Average run times for 60 and 90 jobs is less than 1 and 8 s, respectively. This seems to be considerably fast considering jobs arriving at a real-world terminal within a reasonable time horizon. For future research, we can think of two directions. First, we may investigate how to employ the approach developed in this paper in order to solve more complex problems. Varying the objective, we can think of minimizing the number of late jobs. Often, approaches for this kind of problem require a procedure which checks efficiently whether a given set of jobs can be scheduled non-tardy. Obviously, we can answer this question by finding the maximum lateness among these jobs. Slightly modifying our algorithm, we can abort optimization if a schedule without tardy job is found. Second, another branch of research may consider generalizations of the problem as presented in this paper. For example, we may tackle problem settings involving more than one gate, that is, we have to assign jobs to gates and find a sequence of jobs assigned to the same gate. Here, decomposing the problem gate-wise leads to one-gate problems. Note, however, that the decomposition is not straightforward if there is a single central inventory since jobs assigned to different gates may influence each other’s earliest start times. Another obvious generalization is to take individual arrival dates of jobs into account. In order to accomplish that generalizing step the approaches developed in this paper need modifications regarding several components. Foremost, negative jobs cannot be assumed to be sequenced in EDD anymore. This renders the idea of implicit branching, as it is useless since it is based on assuming exactly this. However, the mechanisms yielding lower bounds and upper bounds can be employed without many modifications. The explicit branching strategies can be used in a similar manner as they are now. Nevertheless, we do not only have to decide whether or not to schedule a negative job next (which is done now since once we decided to schedule a negative job next the very candidate is known) but also which negative job exactly to schedule next.

References Bartels J-H and Zimmermann J (2009). Scheduling tests in automotive R&D projects. European Journal of Operational Research 193(3): 805–819. Boysen N (2010). Truck scheduling at zero-inventory cross docking terminals. Computers & Operations Research 37(1): 32–41. Boysen N and Fliedner M (2010). Cross dock scheduling: Classification, literature review and research agenda. Omega 38(6): 413–422. Boysen N, Fliedner M and Scholl A (2010). Scheduling inbound and outbound trucks at cross docking terminals. OR Spectrum 32(1): 135–161. Briskorn D, Choi B-C, Lee K, Leung J and Pinedo M (2009). Genetic algorithms for inventory constrained scheduling on a single machine. Working Paper. Manuskripte aus den Instituten fu¨r Betriebswirtschaftslehre der Universita¨t Kiel, No 649. Briskorn D, Choi B-C, Lee K, Leung J and Pinedo M (2010). Complexity of single machine scheduling subject to nonnegative inventory constraints. European Journal of Operational Research 207(2): 605–619. Briskorn D, Jaehn F and Pesch E (2011). Exact algorithms for inventory constrained scheduling on a single machine. Journal of Scheduling, published online 20 December, doi: 10.1007/ s10951-011-0261-x. Chen F and Lee C-Y (2009). Minimizing the makespan in a twomachine cross-docking flowshop problem. European Journal of Operational Research 193(1): 59–72. Chen F and Song K (2009). Minimizing makespan in two-stage hybrid cross docking scheduling problem. Computers & Operations Research 36(6): 2066–2073. Graham RL, Lawler EL, Lenstra JK and Rinnooy Kan AHG (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics 5: 287–326. Lawler E (1973). Optimal sequencing of a single machine subject to precedence constraints. Management Science 19(5): 544–546. Martello S, Pisinger D and Toth P (1999). Dynamic programming and strong bounds for the 0-1 knapsack problem. Management Science 45(3): 414–424. Martello S, Pisinger D and Toth P (2000). New trends in exact algorithms for the 0-1 knapsack problem. European Journal of Operational Research 123(3): 325–332. McWilliams DL, Stanfield PM and Geiger CD (2005). The parcel hub scheduling problem: A simulation-based solution approach. Computers & Industrial Engineering 49(3): 393–412. Neumann K and Schwindt C (2002). Project scheduling with inventory constraints. Mathematical Methods of Operations Research 56(3): 513–533. Neumann K, Schwindt C and Trautmann N (2005). Scheduling of continuous and discontinuous material flows with intermediate storage restrictions. European Journal of Operational Research 165(2): 495–509. Pisinger D (2005). Where are the hard knapsack problems? Computers & Operations Research 32(9): 2271–2284. Schwindt C and Trautmann N (2000). Batch scheduling in process industries: An application of resource-constrained project scheduling. OR Spectrum 22(4): 501–524. Yu W and Egbelu PJ (2008). Scheduling of inbound and outbound trucks in cross docking systems with temporary storage. European Journal of Operational Research 184(1): 377–396.

Received May 2012; accepted October 2012 after one revision