:: Industrial Engineering & Management Systems ::

• Editorial Board +
• For Contributors +
• Journal Search +
Journal Search Engine
ISSN : 1598-7248 (Print)
ISSN : 2234-6473 (Online)
Industrial Engineering & Management Systems Vol.17 No.2 pp.226-242
DOI : https://doi.org/10.7232/iems.2018.17.2.226

# A Branch-and-Bound for Production-and-Delivery Scheduling with Dynamic Delivery Cost Allowed

Ik Sun Lee*
School of Business, Dong-A University, Busan, Republic of Korea
Corresponding Author, E-mail: lis1007@dau.ac.kr
January 29, 2016 October 5, 2016 March 20, 2017

## ABSTRACT

This paper considers a production-and-delivery scheduling problem where delivery cost is dependent on delivery time period. In this paper, two types of the scheduling problems having different objective cost functions (measures) are considered. For the first problem, the sum of delivery cost and makespan is considered as the objective cost. The sum of completion times and delivery cost is considered as its objective cost of the second problem. For the two scheduling problems, this paper proves to be NP-hard in the strong sense, and derives some heuristics and branch-and-bound algorithms. In the numerical experiments, the performances of the derived algorithms are tested and compared.

## 1. INTRODUCTION

This paper considers a production-and-delivery (twostage) scheduling problem where delivery cost is dependent on delivery time period, called “dynamic delivery cost”, but not dependent on individual jobs. The delivery cost is associated with the situation where delivery time depends on traffic environment or delivery time shift, but each time period has the same length. The time length of the delivery period can be a day, a week or a month. The delivery cost can be a critical factor in any industries, for example marine transportation, air shipping, and rail transportation. Referring to Lee (2015), the delivery costs can be summed up with labor costs, gas price, interest rates, tax and so on. Delivery cost can vary with each time-period. In this paper, the delivery costs are considered to be relatively large, and the time length of each period is not short. The typical applications of this paper can be marine transportations or air shipping between countries.

The proposed two-stage problem considers the situation where all the jobs are processed sequentially without preemption. Moreover, as soon as each job processing is finished, the finished job is then delivered immediately to a single customer (retailer), which represents the situation where the jobs may be represented by perishable products or where there is no intermediate stage to store any finished job. Delivery cost is charged at completion time of each associated job-processing. Moreover, it is assumed that there are a sufficient number of vehicles for each processed job delivery.

The proposed problem can be stated in detail as follows; there are n jobs available at time zero to be scheduled on a single machine without preemption. Denote by pj and Cj the processing time and the completion time of job j, respectively. Moreover, let δ1 ,…, δm denote the delivery costs for periods 1,…, m, respectively, that is, for each of the time periods (0, H], (H, 2H],…, ((m-1)H, mH], where m is the total number of time periods for delivery, (x, y] represents the time interval x < ty, and H denotes the length of each time period. It is assumed that H and pj have integer values. Moreover, it is assumed that the relation $⌈ ∑ j = 1 n p j / H ⌉$ holds, since no machine idle time is allowed in the problem, where $⌈ x ⌉$ denotes the smallest integer value no less than x. Denote by D(Cj) the delivery cost function such that D(Cj) = δk, for (k-1)H < CjkH, k = 1,…, m, which represents the delivery cost associated with completion time of job j.

Many researches on such a production-and-delivery scheduling have been reported. For example, Potts (1980) and Hall and Shmoys (1992) have studied a singlemachine problem with non-identical job release times and delivery times, under the assumption that a sufficient number of vehicles are available to deliver each processed job immediately to a customer. Lee and Chen (2001), Sung and Kim (2002), Li et al. (2005) and Chang and Lee (2004) have considered machine scheduling problems for jobs to be delivered in batches after processing, subject to capacity restrictions on delivery batches. Note that Potts (1980), Hall and Shmoys (1992), Lee and Chen (2001), Sung and Kim (2002), Li et al. (2005) and Chang and Lee (2004) have not considered any delivery cost either, but tried to minimize only the scheduling objective of either one of makespan and sum of completion times.

Yang (2000) and Hall et al. (2001) have analyzed various production-and-delivery scheduling problems with fixed batch delivery time points, under the assumption of infinite vehicle capacity and no delivery cost. Moreover, they have also assumed a sufficient number of vehicles available. Herrmann and Lee (1993), Yuan (1996), Chen (1996), Cheng et al. (1996) and Hall and Potts (2003) have analyzed various machine scheduling problems for jobs to be delivered in batches after processing, under the assumptions of infinite vehicle capacity and a sufficient number of vehicles. Note that Yang (2000), Hall et al. (2001), Herrmann and Lee (1993), Yuan (1996), Chen (1996), Cheng et al. (1996) and Hall and Potts (2003) have considered a constant delivery cost in their researches.

Lee (2015) has firstly introduced the production and delivery scheduling problem under dynamic delivery cost environments. The research of Lee (2015) analyzed the problem complexity for various scheduling measure, so that some scheduling problems were shown to be NPhard, and DP (Dynamic Programming) algorithms and simple heuristic algorithms were derived.

This paper derives a branch-and-bound algorithm for production and delivery scheduling problem under the dynamic delivery cost environment, which was firstly suggested by Lee (2015). There is a difference between Lee (2015) and this paper, thus Lee (2015) considered the machine idle time between job processing, while this paper does not allow any machine idle time. This paper proves that the considered problem is NP-hard, and derives efficient heuristics and branch-and-bound algorithms.

The standard classification scheme for scheduling problems (Pinedo, 1995) α | β |γ is adapted in this paper where α indicates the scheduling environment, β describes the job characteristics or restrictive requirements, and γ defines the objective function to be minimized. Accordingly, the proposed problem is represented by a single machine problem as α =1. For β , the problem considers “DDC” and “m = q”, where “DDC” indicates the scheduling problem to be considered under dynamic delivery cost environment and “m=q” indicates that the number of dynamic periods is q. For γ , the proposed two-stage problem has the objective function being composed of the delivery cost and the associated scheduling cost. The delivery cost, DC, is expressed as $∑ j = 1 n D ( C j )$, and the scheduling cost is represented by one of the followings;

$Cmax = max C j ( makespan ) , ∑ C j = sum ofcompletion times .$

In summary, this paper considers two scheduling problems, the objective function of the first problem is DC+λCmax and that of the second problem is DC + $λ ⋅ ∑ C j ,$ , where λ denotes the job-holding cost per unit time. Therefore the two problems can be expressed as $1 | D D C | D C + λ ⋅ ∑ C max and 1 | D D C | D C + λ ⋅ ∑ C j$, respectively. In the problems, no machine idle time is allowed, so that the associated makespan is fixed at the value of $∑ j = 1 n p j$, regardless of the job sequence. Therefore, in the rest of this paper, the problem 1|DDC|DC+λCmax will be considered as 1|DDC|DC.

Table 1 provides a summary of the problem complexities in this paper with the section reference.

## 2. PRELIMINARY PROPERTIES

Lee (2015) suggested the definition of the processstarting job, that is, the process-starting job in period k is defined as a job whose processing starts during period k. For the proposed problems 1|DDC|DC and 1|DDC|DC+$λ ⋅ ∑ C j ,$, the following dominance property was characterized by Lee (2015).

Theorem 1. (Lee, 2015) For the problems 1|DDC|DC and 1|DDC|DC+$λ ⋅ ∑ C j ,$ , there exists an optimal schedule such that in each delivery period, the associated process-starting jobs are sequenced in SPT (Shortest Processing Time) order.

The results of Theorem 1 can be used to derive the associated DP algorithms, heuristic algorithms, and branchand- bound algorithms for both the problems 1|DDC|DC and 1|DDC|DC+$λ ⋅ ∑ C j ,$ .

Now Theorem 2 considers a situation where a subsequence of delivery costs is expressed as $δ i ≤ δ i + 1 ≤ ⋯ ≤ δ j − 1 ≤ δ j$ .

Theorem 2. If the relation $δ i ≤ δ i + 1 ≤ ⋯ ≤ δ j − 1 ≤ δ j$ (1 ≤ ijm) holds for the problems 1|DDC|DC and 1|DDC|DC+$λ ⋅ ∑ C j ,$ , then there exists an optimal schedule having the associated process-starting jobs in periods i, i+1, …, j which are all sequenced together in SPT order.

Proof. This can be proved using interchange arguments. ■

Corollary 1. If the relation $δ i ≥ δ i + 1 ≥ ⋯ ≥ δ j − 1 ≤ δ j ( 1 ≤ i ≤ j ≤ m )$ holds for the problem 1|DDC|DC, then there exists an optimal schedule having the associated process-starting jobs in periods i, i+1, …, j which are all sequenced together in LPT (Longest Processing Time) order.

A dominance property is now characterized for the proposed problem 1|DDC|DC+$λ ⋅ ∑ C j ,$ as in Theorem 3.

Theorem 3. Consider two jobs i and j such that pi < pj for the problem 1|DDC|DC+$λ ⋅ ∑ C j ,$ . If the relation $λ ⋅ ( p j − p i ) ≥ ( δ max − δ min )$ holds between the two jobs where δmax and δmin denote the maximum and minimum delivery costs among all the delivery costs, respectively, then job i precedes job j in any optimal schedule.

Proof. Denote by S a schedule such that jobs i and j are sequenced at the a-th and (a+x)-th positions, respectively. Let another schedule S′ be derived by exchanging the positions of jobs i and j in the schedule S. Then, the resulting objective value increment is no less than the value $λ ⋅ x ⋅ ( p j − p i )$, but the decrement is no more than the value x ⋅ (δmaxδmin). Therefore, if the relation λ ⋅(pjpi) ≥ (δmaxδmin) holds, then it may be beneficial to sequence job i prior to job j. ■

From the results of Theorem 3, the following Corollaries 2 and 3 can be characterized.

Corollary 2. If the relation $λ ⋅ min { p j − p i | p j > p i , 1 ≤ i , j ≤ n } ≥ ( δ max − δ min )$ holds for the problem 1|DDC| DC+$λ ⋅ ∑ C j ,$ , then the associated SPT sequence is the optimal schedule.

Corollary 3. If the relation $λ ⋅ ( p [ 2 ] − p [ 1 ] ) ≥ ( δ max − δ min )$ holds for the problem 1|DDC|DC+$λ ⋅ ∑ C j ,$ where p[j] denotes the j-th smallest processing time, then the smallest processing time job should be processed and delivered firstly.

## 3. MINIMIZING THE SUM OF DELIVERY COST AND MAKESPAN

As mentioned in earlier, Lee (2015) proved that the scheduling problem with machine idle time allowed is NP-hard. Since this paper does not allow machine idle time, thus the problem in this paper is much easier than the problem in Lee (2015). Now this section proves firstly that the proposed problem 1|DDC|DC is NP-hard in the strong sense.

Theorem 4. The problem 1|DDC|DC is NP-hard in the strong sense.

Proof. The proof is given in Appendix A. ■

### 3.1. A DP Algorithm

This section derives a DP algorithm for the proposed problem 1|DDC|DC based on Theorem 1. Denote by sk the start-time of the job starting first during period k, and tk the completion time of the job starting last during period k (but may not be completed within period k), where (k-1)Hsk<kH, (k-1)Htk<kH+Pmax, sktk, sk, tkZ, and $P max = max 1 ≤ j ≤ n p j .$ .

DP Algorithm A

Indexing: Index all the jobs in SPT order.

Value Function:

fj (s1, ..., sm, t1, …, tm) = cost of a partial schedule for jobs 1, …, j which has the minimum delivery cost such that during period k, the start-time of the job starting first is sk and the completion time of the job starting last is tk, k = 1, …, m, where (k-1)Hsk < kH, (k-1)Htk < kH+Pmax and $P max = max 1 ≤ j ≤ n p j$.

Boundary Condition:f0(s1, ..., sm, t1, …, tm) = 0, for (k-1)Hsk = tk < kH, k = 1, …, m, and f0(s1, ..., sm, t1, …, tm) = ∞ , for sk < tk, k = 1,…, m.

$O p t i m a l S o l u t i o n V a l u e : min { ( s 1 , ... , s m , t 1 , ... , t m ) | ( k − 1 ) H ≤ s k < k H , ( k − 1 ) H ≤ t k < k H + P max , s k ≤ t k , a n d s k , t k ∈ Z , 1 ≤ k ≤ m , a n d ∑ k = 1 m ( t k − s k ) = ∑ j = 1 n p j } { f n ( s 1 , ... , s m , t 1 , ... , t m ) } R e c u r r e n c e R e l a t i o n : f i ( s 1 , ⋯ , s m , t 1 , ⋯ , t m ) = { ∞ , i f max 1 ≤ k ≤ m { t k − s k } < p j ∞ , i f { ( k 1 , k 2 ) | t k 1 > s k 2 , t k 1 > s k 1 a n d t k 2 > s k 2 f o r ∀ k 1 < k 2 } ≠ ϕ min { k | k H > t k − p j ≥ s k , 1 ≤ k ≤ m } { f j − 1 ( s 1 , ... , s m , t 1 , ... , t k − 1 , t k − p j , t k + 1 , ... , t m ) + D ( t k ) }$

where ϕ denotes an empty set.

The relation sk = tk represents the situation where any job cannot be scheduled to start during period k, while the relation sk < tk represents the situation where more jobs should be scheduled to start during period k.

In each recurrence relation, the first term represents an infeasible case such that there is no space to schedule job j. The second term also represents an infeasible case. For example, consider the two periods k1 and k2, such that $t k 1 > s k 1 , t k 2 > s k 2 and k 1 < k 2$. Then, any jobs can be scheduled during $[ s k 1 , t k 1 ] and [ s k 2 , t k 2 ]$. However, if the two time intervals $[ s k 1 , t k 1 ] and [ s k 2 , t k 2 ]$ are overlapped, as depicted in Figure 1-a), then the associated partial schedule (s1, ..., sm, t1, …, tm) will be infeasible. The third term represents the case where job Jj is scheduled to start during period k, as depicted in Figure 1-b).

In DP algorithm A, there are the total of O(nHm(H+ Pmax)m) states (partial schedules) and the function value of each state is calculated in O(m) time, so that DP algorithm A can be applied to the problem 1|DDC|DC in the complexity order of O(nmHm(H+Pmax)m).

DP algorithm A will be used to verify that Problem 1|DDC, m = q|DC is NP-hard in the ordinary sense in the next section. This is because under the condition m = q, DP algorithm A is of pseudo-polynomial complexity order.

### 3.2. Analysis of a Case with a Fixed Number of Delivery Periods

This section proves that the proposed scheduling problem with only four delivery periods, 1|DDC, m = 4|DC, is NP-hard.

Theorem 5. The problem 1|DDC, m = 4|DC is NPhard.

Proof. The proof is given in Appendix B. ■

The property of the problem 1|DDC, m = 4|DC being NP-hard implies that the problem 1|DDC, m = q( ≥ 4)|DC is NP-hard. Now it is proved in Corollary 4 that the problem 1|DDC, m = q( ≥ 4)|DC is NP-hard in the ordinary sense.

Corollary 4. The problem 1|DDC, m=q( ≥ 4)|DC is NP-hard in the ordinary sense.

Proof. DP algorithm A can be applied to the problem 1|DDC, m = q( ≥ 4)|DC in the pseudo-polynomial complexity order of O(nqHq(H+Pmax)q). Moreover, it was already shown that the problem 1|DDC, m = q (≥ 4)|DC is NP-hard. This implies that the problem is NP-hard in the ordinary sense. ■

The problem 1|DDC, m = 2|DC can be solved in the complexity order of O(n log n), referring to the results of Theorem 2 and Corollary 1. In other words, for the problem 1|DDC, m = 2|DC, the optimal schedule can be found in the complexity order of O(n log n) by sequencing all the jobs in SPT order if δ1δ2 , or sequencing all the jobs in LPT order if δ1 > δ2 . However, the complexity of the problem 1|DDC, m = 3|DC remains open to prove.

### 3.3. Allocation-Based Heuristic

This section derives a heuristic algorithm, called Allocation- based heuristic, for the proposed problem 1|DDC| DC based on Theorem 1, as follows.

Allocation-based heuristic

• Step 0: index all the jobs in SPT order, and find the delivery sequence in the non-decreasing cost order (δ[1] ,…, δ[m] ) such that δ[1]δ[2] ≤…≤ δ[m].

• Step 1: obtain the job set S[k] which is composed of the process-starting jobs during the nondecreasing delivery cost period [k], k = 1,…, m.

• Step 2: sequence the job sets S[k]’s, k = 1, …, m, for the original delivery cost sequence (δ1 ,…, δm).

The following example illustrates the above Allocation- based heuristic.

Example 1. Consider 8 jobs with (p1, …, p7) = (1, 2, 2, 3, 3, 5, 6) and H = 6, m = 5, (δ1 ,…, δ 5 ) = (15, 10, 8, 4, 9). Then, in Step 0, the non-decreasing delivery cost sequence (δ[1] ,…, δ[5]) is (4, 8, 9, 10, 15). In Step 1, the jobs in the set S[1] are identified as {J1, J2, J3} and the jobs in S[2] are as {J4, J5} and the jobs in S[4] are as {J6}, and the jobs in S[4] are as {J7}. In Step 2, the job sets are resequenced as in the original delivery sequence ( S[5] , S[4] , S[2] , S[1] , S[3] ) for (δ1 ,…, δ 5 ), so that the production and delivery sequence is (J7, J4, J5, J1, J2, J3, J6), as presented as follows. The sum of the delivery costs of the obtained schedule is 57.

Now, a tight upper bound on the worst-case performance ratio of the Allocation-based heuristic is derived, as in Theorem 6.

Theorem 6. The worst-case performance ratio of the Allocation-based heuristic is less than or equal to (δmaxδmin ) , which is the best possible bound.

Proof The proof is given in Appendix C. ■

Now, for test on effectiveness of the Allocationbased heuristic, the following lower bound (LB) scheme is derived.

LB scheme

Step 0: find the SPT sequence (p[1],…, p[n]), and find the non-decreasing delivery cost sequence (δ[1] ,…,δ[m] ) such that δ[1]δ[2] ≤…≤ δ[m] , and set k =1, e0 = 0 and X0=ϕ .

Step 1: find Xk as follows, where |A| denotes the number of elements in set A.

$X k = { j | 1 + ∑ i = 0 k − 1 | X i | ≤ j ≤ n − 1 a n d p [ 1 + ∑ i = 0 k − 1 | X i | ] + ... + p [ j ] < H }$

Step 2: find ek as follows.

• Step 2.1: if $∑ i = 0 k − 1 e i + | X k | < n − 1$, then set $e k = | X k | + 1$

• Step 2.2: if $X k = ϕ and ∑ i = 0 k − 1 e i < n − 1$, then set ek = 1 .

• Step 2.3: if $∑ i = 0 k − 1 e i + | X k | ≥ n − 1$, then set $e k = max { 0 , n − 1 − ∑ i = 0 k − 1 e i }$.

Step 3: if the relation k = m holds, then go to Step 4. Otherwise, set k = k + 1 and go to Step 1.

Step 4: Calculate the lower bound value LB as $∑ j = 1 m e j ⋅ δ [ j ] + δ m$.

Theorem 7. The LB scheme can provide a lower bound of the optimal solution value, DCOPT.

Proof. The proof is given in Appendix D. ■

The following example illustrates the above LB scheme.

Example 2. Consider the problem instance of Example 1. Then, in Step 0, the SPT sequence (p[1],…, p[8]) and the non-decreasing delivery cost sequence (δ[1] ,…, δ[5] ) are (1, 2, 2, 3, 3, 5, 6, 8) and (4, 8, 9, 10, 15), respectively. In Steps 1 and 2, (X1, e1) = ({1, 2, 3}, 4), (X2, e2) = ({4}, 2), (X3, e3) = ({5}, 1), (X4, e4) = ({6}, 0), (X5, e5) = (ϕ , 0) are found. In Step 2, a lower bound LB is calculated at the value 50.

### 3.4. Branch-and-Bound (B&B) Algorithm

#### 3.4.1. Branching Rule

This paper uses a forward branching tree in which each node corresponds to a subproblem which is defined as a partial sequence of a subset of jobs that are to be placed at the front of the whole sequence. At each branching stage, a subproblem (i.e., node) is selected and partitioned into one or more extended subproblems (branches) that are defined by attaching one more unscheduled job to the end of the associated partial sequence. To select such a node for generating the associated branches, the depth first rule is adapted in the algorithm.Figure 2

#### 3.4.2. Lower Bound at Each Node

This section derives a lower bound at each node in the branch-and-bound tree. Denote by πk the partial sequence of a subset of jobs that are to be selected at node k in the branch-and-bound tree, and πk′ the partial sequence of jobs that are not contained in πk . Denote by DC(πk) the total objective cost value of the partial sequence πk , and LB(πk′ ) the lower bound value for the partial sequence πk′ , which is derived by using the LB scheme in Section 3.3. Then, the lower bound value, LBk, at node k can be expressed as follows;

$L B k = D C ( π k ) + L B ( π ′ k )$

#### 3.4.3. Upper Bound at Each Node

In order to save the search effort in the suggested branch-and-bound algorithm, each node in the branchand- bound tree can be designated to carry the associated feasible solution which is an upper bound for the optimal objective solution. Denote by the Heu(πk′ ) the heuristic solution value for the partial sequence πk′ at node k, which is found by using the Allocation-based heuristic in Section 3.3. Then, the upper bound value, UBk, at node k can be expressed as follows;

$U B k = D C ( π k ) + H e u ( π ′ k ) .$

#### 3.4.4. Fathoming Rules

This paper considers two fathoming rules. In the first fathoming rule, if the lower bound at any node is larger than equal to the current best solution value, then the associated node will be fathomed, called Fathom 1. The second fathoming rule is derived, called Fathom 2, as in Theorem 8.

Theorem 8. Consider a partial sequence $π i =(J i 1 , J i 2 , ... , J i u ) ,$ i iu where u ≤n. Let another partial sequence π1′ be derived by exchanging job $J i k$ and job $J i u$ in the partial sequence π1 , where pik > piu and 1 ≤ k<u. If the relation DC(π1′ ) ≤DC(π1 ) holds, then the node associated with the partial sequence π1 will be fathomed.

Proof. If the relation DC(π1′ ) < DC(π1 ) holds, the partial sequence π1′ dominates the partial sequence π1 . Moreover, If the relation DC(π1′ ) = DC(π1 ) holds, the partial sequences π1 and π1′ are in duplicate, so that the partial sequence π1 is not necessary to consider. ■

### 3.5. Numerical Experiments

In this section, numerical experiments are performed to evaluate the Allocation-based heuristic and the branchand- bound algorithm for their effectiveness and efficiency. Several uniform distributions are considered, as commonly considered in the literature, for the processing times pi’s to be taken from the interval [1, 20], the delivery period length H taken from [20, 40], and the delivery cost δi ’s taken from [10, 50]. For each given number of jobs, 20 problems are generated to gather some statistics. The computational results are summarized in Table 2, which includes average CPU times, average number of generated nodes, number of problems solved optimally within 600 seconds (commonly considered in the literature), and the solution gaps, where the gap (%) is represented by $( D C A H − D C O P T ) D C O P T × 100$, where DCAH denotes the feasible solution value generated by the Allocation-based heuristic and DCOPT denotes the optimal solution value found by the branch-and-bound algorithm within 600 seconds. From Table 2, it is noted that the average gap of the Allocation- based heuristic is less than 10%, and the branchand- bound algorithm find optimal solutions within reasonable time for up to 18 jobs. Moreover, the average gap of the Allocation-based heuristic decreases as the number of jobs increases. The average and maximum gaps are 7.0% and 40.8% at n = 8, but the average and maximum gaps become 2.0% and 18.4%, respectively at n = 20.

To review any effect of the fathoming rule in Section 3.4.4, Table 3 is presented. Table 3 shows the performance of the branch-and-bound algorithm (for problems Table 2) without Fathom2 employed. By comparing Table 2 with Table 3, it can be concluded that Fathom2 contributes to the efficiency of the branch-and-bound algorithm.

In Table 4, performance trends with deviation in delivery cost δi. are shown for the Allocation-based heuristic and the branch-and-bound algorithm. For each combination of the number of jobs 12, 16, 20 and the delivery cost taken from [10, 20], [10, 30], [10, 40], [10, 50], 20 problems are generated to gather some statistics. The rest of the cost parameters are randomly generated as done for Table 2. It is observed from Table 4 that the maximum and average gaps of the Allocation-based heuristic are 10.7% and 2.5% as the delivery cost δi taken from [10, 20], but the maximum and average gaps of the Allocation- based heuristic are 31.0% and 7.5% as the delivery cost δi taken from [10, 50]. Thus as the deviation in delivery cost δi gets larger, the performance of the Allocation- based heuristic get worse, therefore it seems that the difficulty of the problem instances may increase.

In Table 5, performance trends with the amount of delivery cost δi are shown for the Allocation-based heuristic and the branch-and-bound algorithm. It is observed from Table 5 that the maximum and average gaps of the Allocation-based heuristic are 20.8% and 5.3% as the delivery cost δi taken from [10, 30], but the maximum and average gaps of the Allocation-based heuristic are 8.2% and 2.0% as the delivery cost δi taken from [40, 60]. Thus as the delivery cost δi increases, the solution gap of the Allocation-based heuristic decreases, therefore it seems that the difficulty of the problem instances may decrease.

In Table 6, performance trends with delivery period length are shown for the Allocation-based heuristic and the branch-and-bound algorithm. For each combination of the number of jobs 12, 16, 20 and the delivery period length 20, 25, 30, 35, 40, 20 problems are generated to gather some statistics. It is observed from Table 6 that as the delivery period length H increases, the performances of the Allocation-based heuristic and the branch-andbound algorithm get better, since it seems that the difficulty of the problem instances may decrease.

Now, the computational tests are carried out for large-sized problems having between 20 and 200 jobs. The test results are presented in Table 7. The gap (%) is represented by $( D C A H − L B ) L B × 100$, where LB denotes the lower bound value generated by the LB scheme in Section 3.3. It is observed from Table 7 that the Allocationbased heuristic finds good solutions having average gap value about 15.9% with very small time elapsed. Moreover, Table 7 shows that the average gap does not vary much with the number of jobs. This implies that the Allocation- based heuristic may find about the same quality of good solutions for larger problems.

## 4. MINIMIZING THE SUM OF COMPLETION TIMES AND DELIVERY COST

This section proves firstly that the proposed problem $1 | D D C | D C + λ ⋅ ∑ C j$ is NP-hard in the strong sense.

Theorem 9. The problem 1|DDC|DC+$λ ⋅ ∑ C j ,$ is NP-hard in the strong sense.

Proof. The proof is given in Appendix E. ■

### 4.1. A DP Algorithm

This section derives a DP algorithm for the problem 1|DDC|DC+$λ ⋅ ∑ C j ,$ based on Theorem 1 as follows, where sk and tk are defined as in DP algorithm A.

DP Algorithm B

Indexing: Index all the jobs in SPT order.

Value Function:

fj(s1, ..., sm, t1, …, tm) = cost of a partial schedule for jobs 1, …, j which has the minimum objective value such that during period k, the start-time of the job starting first is sk and the completion time of the job starting last is tk, k = 1,…, m, where (k-1)Hsk<kH, (k-1)Htk<kH+Pmax and $P max = max 1 ≤ j ≤ n p j .$.

Boundary Condition:f0(s1, ..., sm, t1, …, tm) = 0, for (k-1)Hsk = tk < kH, k = 1,…, m, and f0(s1, ..., sm, t1, …, tm) = ∞ , for sk < tk, k = 1, …, m.

$O p t i m a l S o l u t i o n V a l u e min { ( s 1 , ... , s m , t 1 , ... , t m ) | ( k − 1 ) H ≤ s k < k H , ( k − 1 ) H ≤ t k < k H + P max , s k ≤ t k , a n d s k , t k ∈ Z , 1 ≤ k ≤ m , a n d ∑ k = 1 m ( t k − s k ) = ∑ j = 1 n p j } { f n ( s 1 , ... , s m , t 1 , ... , t m ) } R e c u r r e n c e R e l a t i o n : f i ( s 1 , ⋯ , s m , t 1 , ⋯ , t m ) = { ∞ , i f max 1 ≤ k ≤ m { t k − s k } < p j ∞ , i f { ( k 1 , k 2 ) | t k 1 > s k 2 , t k 1 > s k 1 a n d t k 2 > s k 2 f o r ∀ k 1 < k 2 } ≠ ϕ min { k | k H > t k − p j ≥ s k , 1 ≤ k ≤ m } { f j − 1 ( s 1 , ... , s m , t 1 , ... , t k − 1 , t k − p j , t k + 1 , ... , t m ) + λ ⋅ t k + D ( t k ) }$

where ϕ denotes an empty set.

In DP algorithm B, there are the total of O(nHm(H+Pmax)m) states (partial schedules) and the function value of each state is calculated in O(m) time, so that DP algorithm B can be applied to the problem 1|DDC|DC+$λ ⋅ ∑ C j ,$ in the complexity order of O(nmHm(H+Pmax)m).

DP algorithm B will be used to verify that Problem 1|DDC, m = q|DC+$λ ⋅ ∑ C j ,$ $λ ⋅ ∑ C j ,$ is NP-hard in the ordinary sense in the next section. This is because under the condition m = q, DP algorithm B is of pseudo-polynomial complexity order.

### 4.2. Analysis of a Case with a Fixed Number of Delivery Periods

This section proves that the proposed scheduling problem with only four delivery periods, 1|DDC, m = 4|DC+$λ ⋅ ∑ C j ,$ , is NP-hard.

Theorem 10. The problem 1|DDC, m = 4|DC+$λ ⋅ ∑ C j ,$ is NP-hard.

Proof. The proof is given in Appendix F. ■

The property of the problem 1|DDC, m = 4|DC+ $λ ⋅ ∑ C j ,$ being NP-hard implies that the problem 1|DDC, m = q( ≥4)|DC+$λ ⋅ ∑ C j ,$ is NP-hard. Now it is proved in Corollary 5 that the problem 1|DDC, m = q( ≥ 4)|DC+ $λ ⋅ ∑ C j ,$ is NP-hard in the ordinary sense.

Corollary 5. The problem 1|DDC, m = q( ≥ 4)|DC+ $λ ⋅ ∑ C j ,$ is NP-hard in the ordinary sense.

Proof. DP algorithm B can be applied to the problem 1|DDC, m = q(≥4)|DC+$λ ⋅ ∑ C j ,$ in the pseudo-polynomial complexity order of O(nqHq(H+Pmax)q). Moreover, it was already shown that the problem 1|DDC, m = q( ≥ 4)|DC+ $λ ⋅ ∑ C j ,$ is NP-hard. This implies that the problem is NPhard in the ordinary sense. ■

The problem 1|DDC, m=2, δ1δ2 |DC + $λ ⋅ ∑ C j ,$ can be solved in the complexity order of O(nlogn), based on the results of Theorem 2. However, the complexities of the problems 1|DDC, m = 2, δ1 > δ2 4 |DC+$λ ⋅ ∑ C j ,$ and 1|DDC, m = 3|DC+$λ ⋅ ∑ C j ,$ remain open to prove.

### 4.3. SPT-Based Heuristic

In a classical single machine scheduling problem, SPT sequence is optimal for the objective measure of the sum of completion times. This provides the authors with the motivation of deriving a heuristic algorithm, called SPT-based heuristic, for the proposed problem 1|DDC|DC +$λ ⋅ ∑ C j ,$ .

SPT-based heuristic

Step 1: process and deliver all the jobs in SPT order.

The following example illustrates the above SPTbased heuristic.

Example 4. Consider the problem instance of Example 1. Then, according to Step 1, all the jobs are processed and delivered in SPT order, which results in the total cost value of 182.

Now, an upper bound on the worst-case performance ratio of the SPT-based heuristic is derived, as in Theorem 11.

Theorem 11. The worst-case performance ratio of the SPT-based heuristic is less than or equal to (δmaxδmin ) .

Proof. The proof is given in Appendix G. ■

Now, the following lower bound scheme LB is derived by modifying the LB scheme in Section 3.3, as follows.

LB scheme

Steps 0, 1, 2 and 3 are identical with those in the LB scheme in Section 3.3.

Step 4: Calculate the lower bound value LB as $∑ j = 1 m e j ⋅ δ [ j ] + δ m + ∑ j = 1 n ( n − j + 1 ) ⋅ p [ j ]$.

### 4.4. Numerical Experiments

For the proposed problem 1|DDC|DC+$λ ⋅ ∑ C j ,$ , the Allocation-based heuristic in Section 3.3 can be applied. Moreover, a branch-and-bound algorithm can be derived by modifying the branch-and-bound algorithm derived in Section 3.4. Thus a branch-and-bound algorithm for the problem can be derived from the modifying process of the lowerbound and objective cost calculation.

Now we perform the numerical experiments to evaluate the SPT-based heuristic, the Allocation-based heuristic and the branch-and-bound algorithm for their effectiveness and efficiency. The job-holding cost λ is randomly generated from the real-valued interval [0.1, 3.0], and the rest of the cost parameters are randomly generated as done for Table 2. For each given number of jobs, 20 problems are generated to gather some statistics. The computational results are summarized in Table 8. From Table 8, it is noted that the SPT-based heuristic outperforms the Allocation-based heuristic, and produces good solutions with 2% average gap. The branch-and-bound algorithm produces optimal solutions within reasonable time for up to 26 jobs.

In Table 9, performance trends with job-holding cost λ are shown for each of the SPT-based heuristic, the Allocation-based heuristic and the branch-and-bound algorithm. For each combination of the number of jobs 12, 16, 20 and the job-holding cost taken from [0.1, 0.5], [0.6, 1.0], [1.1, 1.5], [1.6, 2.0], [2.1, 2.5], [2.6, 3.0], 20 problems are generated to gather some statistics. It is observed from Table 9 that as the job-holding cost λ from [0.1, 0.5], the maximum and average gaps of the SPT-based heuristic are 22.38% and 4.98% and the average computation time of the branch-and-bound algorithm is 123.7, but as the job-holding cost λ from [2.6, 3.0], the maximum and average gaps of the SPT-based heuristic are 0.47% and 0.06% and the average computation time of the branch-and-bound algorithm is 0.2, since it seems that the difficulty of the problem instances may decrease.

## 5. CONCLUSION

CONCLUSION This paper considers a production-and-delivery scheduling problem where delivery cost depends on delivery time period. Two different objective cost functions (measures) are considered. For the first scheduling problem having the sum of delivery cost and makespan as the objective cost function, it is proved to be NP-hard in the strong sense, and an Allocation-based heuristic and also a branch-andbound algorithm are derived. The numerical experiments show that the Allocation-based heuristic finds good quality of solutions within average gap 10% for reasonable-size problems. Even for large-size problems, it is tested that the Allocation-based heuristic can work well. For the second scheduling problem having the sum of completion times and delivery cost as its objective cost function, it is also proved to be NP-hard in the strong sense, and a SPT-based heuristic and a branch-and-bound algorithm are derived. The numerical experiments show that the SPT-based heuristic finds very good quality of solutions within average gap 2% for reasonable-size problems.

## ACKNOWLEDGMENT

This study was supported by research funds from Dong-A University.

## Figure

The possible cases in DP algorithm A.

The possible cases in DP algorithm A.

## Table

Complexity results of the scheduling problems

Summary of the computational results

Npl: number of solved problems optimally by B&B within 600 seconds (out of 20 problems).

Results of the branch-and-bound algorithm without Fathom 2 employed

Summary of the computational results associated with deviation in delivery costs

Summary of the computational results associated with the amount of delivery costs

Summary of the computational results associated with various delivery period lengths

Summary of the computational results for large-sized problems

Summary of the computational results

Summary of the computational results associated with various job-holding costs λ

## REFERENCES

1. Y.C. Chang , C.Y. Lee (2004) Machine scheduling with job delivery coordination., Eur. J. Oper. Res., Vol.158 (2) ; pp.470-487
2. Z.L. Chen (1996) Scheduling and common due date assignment with earliness-tardiness penalties and batch delivery costs., Eur. J. Oper. Res., Vol.93 (1) ; pp.49-60
3. T.C.E. Cheng , V.S. Gordon , M.Y. Kovalyov (1996) Single machine scheduling with batch deliveries., Eur. J. Oper. Res., Vol.94 (2) ; pp.277-283
4. M.R. Garey , D.S. Johnson (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness., Freeman,
5. L.A. Hall , B. Shmoys (1992) Jacksons rule for single-machine scheduling: Making a good heuristic better., Math. Oper. Res., Vol.17 (1) ; pp.22-35
6. N.G. Hall , C.N. Potts (2003) Supply chain scheduling: Batching and delivery., Oper. Res., Vol.51 (4) ; pp.566-584
7. N.G. Hall , M.A. Lesaoana , C.N. Potts (2001) Scheduling with fixed delivery dates., Oper. Res., Vol.49 (1) ; pp.134-144
8. J.W. Herrmann , C.Y. Lee (1993) On scheduling to minimize earliness-tardiness and batch delivery costs with a common due date., Eur. J. Oper. Res., Vol.70 (3) ; pp.272-288
9. C.Y. Lee , Z.L. Chen (2001) Machine scheduling with transportation considerations., J. Sched., Vol.4 ; pp.3-24
10. I.S. Lee (2015) A coordinated scheduling of productionand- delivery under dynamic delivery cost environments., Comput. Ind. Eng., Vol.81 ; pp.22-35
11. C.L. Li , G. Vairaktarakis , C.Y. Lee (2005) Machine scheduling with deliveries to multiple customer locations., Eur. J. Oper. Res., Vol.164 (1) ; pp.39-51
12. M. Pinedo (1995) Scheduling: Theory, Algorithms, and Systems., Prentice Hall,
13. C.N. Potts (1980) Analysis of a heuristic for one machine sequencing with release dates and delivery times., Oper. Res., Vol.28 (6) ; pp.1436-1441
14. C.S. Sung , Y.H. Kim (2002) Minimizing makespan in a two-machine flowshop with dynamic arrivals allowed., Comput. Oper. Res., Vol.29 (3) ; pp.275-294
15. X. Yang (2000) Scheduling with generalized batch delivery dates and earliness penalties., IIE Trans., Vol.32 (8) ; pp.735-741
16. J. Yuan (1996) A note on the complexity of singlemachine scheduling with a common due date, earliness-tardiness, and batch delivery costs., Eur. J. Oper. Res., Vol.94 (1) ; pp.203-205
 오늘하루 팝업창 안보기 닫기