1. INTRODUCTION
This paper considers a productionanddelivery (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 timeperiod. 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 twostage 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 jobprocessing. 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 p_{j} and C_{j} 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],…, ((m1)H, mH], where m is the total number of time periods for delivery, (x, y] represents the time interval x < t ≤ y, and H denotes the length of each time period. It is assumed that H and p_{j} have integer values. Moreover, it is assumed that the relation $\lceil {\displaystyle {\sum}_{j=1}^{n}{p}_{j}}/H\rceil $ holds, since no machine idle time is allowed in the problem, where $\lceil x\rceil $ denotes the smallest integer value no less than x. Denote by D(C_{j}) the delivery cost function such that D(C_{j}) = δ_{k}, for (k1)H < C_{j} ≤ kH, k = 1,…, m, which represents the delivery cost associated with completion time of job j.
Many researches on such a productionanddelivery scheduling have been reported. For example, Potts (1980) and Hall and Shmoys (1992) have studied a singlemachine problem with nonidentical 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 productionanddelivery 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 branchandbound 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 NPhard, and derives efficient heuristics and branchandbound 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 twostage problem has the objective function being composed of the delivery cost and the associated scheduling cost. The delivery cost, DC, is expressed as ${\sum}_{j=1}^{n}D({C}_{j})$, and the scheduling cost is represented by one of the followings;
In summary, this paper considers two scheduling problems, the objective function of the first problem is DC+λ ⋅C_{max} and that of the second problem is DC + $\lambda \cdot {\displaystyle \sum {C}_{j}},$ , where λ denotes the jobholding cost per unit time. Therefore the two problems can be expressed as $1\leftDDC\rightDC+\lambda \cdot {\displaystyle \sum {C}_{\text{max}}}\hspace{0.17em}\text{and}\hspace{0.17em}1\leftDDC\rightDC+\lambda \cdot {\displaystyle \sum {C}_{j}}$, respectively. In the problems, no machine idle time is allowed, so that the associated makespan is fixed at the value of $\sum}_{j=1}^{n}{p}_{j$, regardless of the job sequence. Therefore, in the rest of this paper, the problem 1DDCDC+λ ⋅C_{max} will be considered as 1DDCDC.
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 processstarting job in period k is defined as a job whose processing starts during period k. For the proposed problems 1DDCDC and 1DDCDC+$\lambda \cdot {\displaystyle \sum {C}_{j}},$, the following dominance property was characterized by Lee (2015).
Theorem 1. (Lee, 2015) For the problems 1DDCDC and 1DDCDC+$\lambda \cdot {\displaystyle \sum {C}_{j}},$ , there exists an optimal schedule such that in each delivery period, the associated processstarting 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 1DDCDC and 1DDCDC+$\lambda \cdot {\displaystyle \sum {C}_{j}},$ .
Now Theorem 2 considers a situation where a subsequence of delivery costs is expressed as ${\delta}_{i}\le {\delta}_{i+1}\le \cdots \le {\delta}_{j1}\le {\delta}_{j}$ .
Theorem 2. If the relation ${\delta}_{i}\le {\delta}_{i+1}\le \cdots \le {\delta}_{j1}\le {\delta}_{j}$ (1 ≤ i ≤ j ≤ m) holds for the problems 1DDCDC and 1DDCDC+$\lambda \cdot {\displaystyle \sum {C}_{j}},$ , then there exists an optimal schedule having the associated processstarting 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 ${\delta}_{i}\ge {\delta}_{i+1}\ge \cdots \ge {\delta}_{j1}\le {\delta}_{j}\left(1\le i\le j\le m\right)$ holds for the problem 1DDCDC, then there exists an optimal schedule having the associated processstarting 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 1DDCDC+$\lambda \cdot {\displaystyle \sum {C}_{j}},$ as in Theorem 3.
Theorem 3. Consider two jobs i and j such that p_{i} < p_{j} for the problem 1DDCDC+$\lambda \cdot {\displaystyle \sum {C}_{j}},$ . If the relation $\lambda \cdot \left({p}_{j}{p}_{i}\right)\ge \left({\delta}_{\mathrm{max}}{\delta}_{\mathrm{min}}\right)$ 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 ath 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 $\lambda \cdot x\cdot \left({p}_{j}{p}_{i}\right)$, but the decrement is no more than the value x ⋅ (δ_{max} − δ_{min}). Therefore, if the relation λ ⋅(p_{j} − p_{i}) ≥ (δ_{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 $\lambda \cdot \mathrm{min}\{{p}_{j}{p}_{i}{p}_{j}>{p}_{i},1\le i,j\le n\}\ge \left({\delta}_{\mathrm{max}}{\delta}_{\mathrm{min}}\right)$ holds for the problem 1DDC DC+$\lambda \cdot {\displaystyle \sum {C}_{j}},$ , then the associated SPT sequence is the optimal schedule.
Corollary 3. If the relation $\lambda \cdot \left({p}_{\left[2\right]}{p}_{\left[1\right]}\right)\ge ({\delta}_{\mathrm{max}}{\delta}_{\mathrm{min}})$ holds for the problem 1DDCDC+$\lambda \cdot {\displaystyle \sum {C}_{j}},$ where p_{[j]} denotes the jth 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 NPhard. 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 1DDCDC is NPhard in the strong sense.
Theorem 4. The problem 1DDCDC is NPhard 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 1DDCDC based on Theorem 1. Denote by s_{k} the starttime of the job starting first during period k, and t_{k} the completion time of the job starting last during period k (but may not be completed within period k), where (k1)H≤ s_{k}<kH, (k1)H≤ t_{k}<kH+P_{max}, s_{k} ≤ t_{k}, s_{k}, t_{k} ∈ Z, and ${P}_{\mathrm{max}}={\mathrm{max}}_{1\le j\le n}{p}_{j}.$ .
DP Algorithm A
Indexing: Index all the jobs in SPT order.
Value Function:
f_{j} (s_{1}, ..., s_{m}, t_{1}, …, t_{m}) = cost of a partial schedule for jobs 1, …, j which has the minimum delivery cost such that during period k, the starttime of the job starting first is s_{k} and the completion time of the job starting last is t_{k}, k = 1, …, m, where (k1)H≤ s_{k} < k_{H}, (k1)H≤ t_{k} < kH+P_{max} and ${P}_{\mathrm{max}}={\mathrm{max}}_{1\le j\le n}{p}_{j}$.
Boundary Condition:f_{0}(s_{1}, ..., s_{m}, t_{1}, …, t_{m}) = 0, for (k1)H≤ s_{k} = t_{k} < k_{H}, k = 1, …, m, and f_{0}(s_{1}, ..., s_{m}, t_{1}, …, t_{m}) = ∞ , for s_{k} < t_{k}, k = 1,…, m.
where ϕ denotes an empty set.
The relation s_{k} = t_{k} represents the situation where any job cannot be scheduled to start during period k, while the relation s_{k} < t_{k} 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 k_{1} and k_{2}, such that ${t}_{{k}_{1}}>{s}_{{k}_{1}},\hspace{0.17em}{t}_{{k}_{2}}>{s}_{{k}_{2}}\hspace{0.17em}\text{and}\hspace{0.17em}{k}_{1}<{k}_{2}$. Then, any jobs can be scheduled during $\left[{s}_{{k}_{1}},\hspace{0.17em}{t}_{{k}_{1}}\right]\hspace{0.17em}\text{and}\hspace{0.17em}\left[{s}_{{k}_{2}},\hspace{0.17em}{t}_{{k}_{2}}\right]$. However, if the two time intervals $\left[{s}_{{k}_{1}},\hspace{0.17em}{t}_{{k}_{1}}\right]\hspace{0.17em}\text{and}\hspace{0.17em}\left[{s}_{{k}_{2}},\hspace{0.17em}{t}_{{k}_{2}}\right]$ are overlapped, as depicted in Figure 1a), then the associated partial schedule (s_{1}, ..., s_{m}, t_{1}, …, t_{m}) will be infeasible. The third term represents the case where job J_{j} is scheduled to start during period k, as depicted in Figure 1b).
In DP algorithm A, there are the total of O(nH^{m}(H+ P_{max})^{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 1DDCDC in the complexity order of O(nmH^{m}(H+P_{max})^{m}).
DP algorithm A will be used to verify that Problem 1DDC, m = qDC is NPhard in the ordinary sense in the next section. This is because under the condition m = q, DP algorithm A is of pseudopolynomial 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, 1DDC, m = 4DC, is NPhard.
Theorem 5. The problem 1DDC, m = 4DC is NPhard.
Proof. The proof is given in Appendix B. ■
The property of the problem 1DDC, m = 4DC being NPhard implies that the problem 1DDC, m = q( ≥ 4)DC is NPhard. Now it is proved in Corollary 4 that the problem 1DDC, m = q( ≥ 4)DC is NPhard in the ordinary sense.
Corollary 4. The problem 1DDC, m=q( ≥ 4)DC is NPhard in the ordinary sense.
Proof. DP algorithm A can be applied to the problem 1DDC, m = q( ≥ 4)DC in the pseudopolynomial complexity order of O(nqH^{q}(H+P_{max})^{q}). Moreover, it was already shown that the problem 1DDC, m = q (≥ 4)DC is NPhard. This implies that the problem is NPhard in the ordinary sense. ■
The problem 1DDC, m = 2DC 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 1DDC, m = 2DC, 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 1DDC, m = 3DC remains open to prove.
3.3. AllocationBased Heuristic
This section derives a heuristic algorithm, called Allocation based heuristic, for the proposed problem 1DDC DC based on Theorem 1, as follows.
Allocationbased heuristic

Step 0: index all the jobs in SPT order, and find the delivery sequence in the nondecreasing cost order (δ_{[1]} ,…, δ_{[m]} ) such that δ_{[1]} ≤ δ_{[2]} ≤…≤ δ_{[m]}.

Step 1: obtain the job set S_{[k]} which is composed of the processstarting 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 (p_{1}, …, p_{7}) = (1, 2, 2, 3, 3, 5, 6) and H = 6, m = 5, (δ_{1} ,…, δ 5 ) = (15, 10, 8, 4, 9). Then, in Step 0, the nondecreasing delivery cost sequence (δ_{[1]} ,…, δ_{[5]}) is (4, 8, 9, 10, 15). In Step 1, the jobs in the set S_{[1]} are identified as {J_{1}, J_{2}, J_{3}} and the jobs in S[2] are as {J_{4}, J_{5}} and the jobs in S[4] are as {J_{6}}, and the jobs in S[4] are as {J_{7}}. 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 (J_{7}, J_{4}, J_{5}, J_{1}, J_{2}, J_{3}, J_{6}), as presented as follows. The sum of the delivery costs of the obtained schedule is 57.
Now, a tight upper bound on the worstcase performance ratio of the Allocationbased heuristic is derived, as in Theorem 6.
Theorem 6. The worstcase performance ratio of the Allocationbased 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 nondecreasing delivery cost sequence (δ_{[1]} ,…,δ_{[m]} ) such that δ_{[1]} ≤ δ_{[2]} ≤…≤ δ_{[m]} , and set k =1, e_{0} = 0 and X_{0}=ϕ .
Step 1: find X_{k} as follows, where A denotes the number of elements in set A.
Step 2: find e_{k} as follows.

Step 2.1: if ${\sum}_{i=0}^{k1}{e}_{i}}+\left{X}_{k}\right<n1$, then set ${e}_{k}=\left{X}_{k}\right+1$

Step 2.2: if ${X}_{k}=\varphi \hspace{0.17em}\text{and}\hspace{0.17em}{\displaystyle {\sum}_{i=0}^{k1}{e}_{i}}<n1$, then set e_{k} = 1 .

Step 2.3: if ${\sum}_{i=0}^{k1}{e}_{i}}+\left{X}_{k}\right\ge n1$, then set ${e}_{k}=\mathrm{max}\left\{0,\hspace{0.17em}\hspace{0.17em}n1{\displaystyle {\sum}_{i=0}^{k1}{e}_{i}}\right\}$.
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 ${\sum}_{j=1}^{m}{e}_{j}\cdot {\delta}_{\left[j\right]}}+{\delta}_{m$.
Theorem 7. The LB scheme can provide a lower bound of the optimal solution value, DC_{OPT}.
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 nondecreasing 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, (X_{1}, e_{1}) = ({1, 2, 3}, 4), (X_{2}, e_{2}) = ({4}, 2), (X_{3}, e_{3}) = ({5}, 1), (X_{4}, e_{4}) = ({6}, 0), (X_{5}, e_{5}) = (ϕ , 0) are found. In Step 2, a lower bound LB is calculated at the value 50.
3.4. BranchandBound (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 branchandbound tree. Denote by π_{k} the partial sequence of a subset of jobs that are to be selected at node k in the branchandbound 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, LB_{k}, at node k can be expressed as follows;
3.4.3. Upper Bound at Each Node
In order to save the search effort in the suggested branchandbound 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 Allocationbased heuristic in Section 3.3. Then, the upper bound value, UB_{k}, at node k can be expressed as follows;
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 ${\pi}_{i}{\text{=(J}}_{{i}_{1}},{\text{J}}_{{i}_{2}},\mathrm{...},{\text{J}}_{{i}_{u}}),$ i iu where u ≤n. Let another partial sequence π_{1}′ be derived by exchanging job ${\text{J}}_{{i}_{k}}$ and job ${\text{J}}_{{i}_{u}}$ in the partial sequence π_{1} , where p_{ik} > p_{iu} 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 Allocationbased 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 p_{i}’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 $\frac{\left(D{C}_{AH}D{C}_{OPT}\right)}{D{C}_{OPT}}\times 100$, where DC_{AH} denotes the feasible solution value generated by the Allocationbased heuristic and DC_{OPT} denotes the optimal solution value found by the branchandbound 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 Allocationbased 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 branchandbound 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 branchandbound algorithm.
In Table 4, performance trends with deviation in delivery cost δ_{i}. are shown for the Allocationbased heuristic and the branchandbound 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 Allocationbased 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 Allocationbased heuristic and the branchandbound algorithm. It is observed from Table 5 that the maximum and average gaps of the Allocationbased heuristic are 20.8% and 5.3% as the delivery cost δ_{i} taken from [10, 30], but the maximum and average gaps of the Allocationbased 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 Allocationbased 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 Allocationbased heuristic and the branchandbound 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 Allocationbased heuristic and the branchandbound algorithm get better, since it seems that the difficulty of the problem instances may decrease.
Now, the computational tests are carried out for largesized problems having between 20 and 200 jobs. The test results are presented in Table 7. The gap (%) is represented by $\frac{\left(D{C}_{AH}LB\right)}{LB}\times 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\leftDDC\rightDC+\lambda \cdot {\displaystyle \sum {C}_{j}}$ is NPhard in the strong sense.
Theorem 9. The problem 1DDCDC+$\lambda \cdot {\displaystyle \sum {C}_{j}},$ is NPhard 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 1DDCDC+$\lambda \cdot {\displaystyle \sum {C}_{j}},$ based on Theorem 1 as follows, where s_{k} and t_{k} are defined as in DP algorithm A.
DP Algorithm B
Indexing: Index all the jobs in SPT order.
Value Function:
f_{j}(s_{1}, ..., s_{m}, t_{1}, …, t_{m}) = cost of a partial schedule for jobs 1, …, j which has the minimum objective value such that during period k, the starttime of the job starting first is s_{k} and the completion time of the job starting last is t_{k}, k = 1,…, m, where (k1)H≤s_{k}<k_{H}, (k1)H≤ t_{k}<k_{H}+P_{max} and ${P}_{\mathrm{max}}={\mathrm{max}}_{1\le j\le n}{p}_{j}.$.
Boundary Condition:f_{0}(s_{1}, ..., s_{m}, t_{1}, …, t_{m}) = 0, for (k1)H≤ s_{k} = t_{k} < kH, k = 1,…, m, and f_{0}(s_{1}, ..., s_{m}, t_{1}, …, t_{m}) = ∞ , for s_{k} < t_{k}, k = 1, …, m.
where ϕ denotes an empty set.
In DP algorithm B, there are the total of O(nH^{m}(H+P_{max})^{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 1DDCDC+$\lambda \cdot {\displaystyle \sum {C}_{j}},$ in the complexity order of O(nmH^{m}(H+P_{max})^{m}).
DP algorithm B will be used to verify that Problem 1DDC, m = qDC+$\lambda \cdot {\displaystyle \sum {C}_{j}},$ $\lambda \cdot {\displaystyle \sum {C}_{j}},$ is NPhard in the ordinary sense in the next section. This is because under the condition m = q, DP algorithm B is of pseudopolynomial 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, 1DDC, m = 4DC+$\lambda \cdot {\displaystyle \sum {C}_{j}},$ , is NPhard.
Theorem 10. The problem 1DDC, m = 4DC+$\lambda \cdot {\displaystyle \sum {C}_{j}},$ is NPhard.
Proof. The proof is given in Appendix F. ■
The property of the problem 1DDC, m = 4DC+ $\lambda \cdot {\displaystyle \sum {C}_{j}},$ being NPhard implies that the problem 1DDC, m = q( ≥4)DC+$\lambda \cdot {\displaystyle \sum {C}_{j}},$ is NPhard. Now it is proved in Corollary 5 that the problem 1DDC, m = q( ≥ 4)DC+ $\lambda \cdot {\displaystyle \sum {C}_{j}},$ is NPhard in the ordinary sense.
Corollary 5. The problem 1DDC, m = q( ≥ 4)DC+ $\lambda \cdot {\displaystyle \sum {C}_{j}},$ is NPhard in the ordinary sense.
Proof. DP algorithm B can be applied to the problem 1DDC, m = q(≥4)DC+$\lambda \cdot {\displaystyle \sum {C}_{j}},$ in the pseudopolynomial complexity order of O(nqH^{q}(H+P_{max})^{q}). Moreover, it was already shown that the problem 1DDC, m = q( ≥ 4)DC+ $\lambda \cdot {\displaystyle \sum {C}_{j}},$ is NPhard. This implies that the problem is NPhard in the ordinary sense. ■
The problem 1DDC, m=2, δ_{1} ≤ δ_{2} DC + $\lambda \cdot {\displaystyle \sum {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 1DDC, m = 2, δ_{1} > δ_{2} 4 DC+$\lambda \cdot {\displaystyle \sum {C}_{j}},$ and 1DDC, m = 3DC+$\lambda \cdot {\displaystyle \sum {C}_{j}},$ remain open to prove.
4.3. SPTBased 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 SPTbased heuristic, for the proposed problem 1DDCDC +$\lambda \cdot {\displaystyle \sum {C}_{j}},$ .
SPTbased 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 worstcase performance ratio of the SPTbased heuristic is derived, as in Theorem 11.
Theorem 11. The worstcase performance ratio of the SPTbased 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 $\sum}_{j=1}^{m}{e}_{j}\cdot {\delta}_{\left[j\right]}}+{\delta}_{m}+{\displaystyle {\sum}_{j=1}^{n}\left(nj+1\right)\cdot {p}_{\left[j\right]$.
4.4. Numerical Experiments
For the proposed problem 1DDCDC+$\lambda \cdot {\displaystyle \sum {C}_{j}},$ , the Allocationbased heuristic in Section 3.3 can be applied. Moreover, a branchandbound algorithm can be derived by modifying the branchandbound algorithm derived in Section 3.4. Thus a branchandbound 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 SPTbased heuristic, the Allocationbased heuristic and the branchandbound algorithm for their effectiveness and efficiency. The jobholding cost λ is randomly generated from the realvalued 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 SPTbased heuristic outperforms the Allocationbased heuristic, and produces good solutions with 2% average gap. The branchandbound algorithm produces optimal solutions within reasonable time for up to 26 jobs.
In Table 9, performance trends with jobholding cost λ are shown for each of the SPTbased heuristic, the Allocationbased heuristic and the branchandbound algorithm. For each combination of the number of jobs 12, 16, 20 and the jobholding 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 jobholding cost λ from [0.1, 0.5], the maximum and average gaps of the SPTbased heuristic are 22.38% and 4.98% and the average computation time of the branchandbound algorithm is 123.7, but as the jobholding cost λ from [2.6, 3.0], the maximum and average gaps of the SPTbased heuristic are 0.47% and 0.06% and the average computation time of the branchandbound algorithm is 0.2, since it seems that the difficulty of the problem instances may decrease.
5. CONCLUSION
CONCLUSION This paper considers a productionanddelivery 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 NPhard in the strong sense, and an Allocationbased heuristic and also a branchandbound algorithm are derived. The numerical experiments show that the Allocationbased heuristic finds good quality of solutions within average gap 10% for reasonablesize problems. Even for largesize problems, it is tested that the Allocationbased 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 NPhard in the strong sense, and a SPTbased heuristic and a branchandbound algorithm are derived. The numerical experiments show that the SPTbased heuristic finds very good quality of solutions within average gap 2% for reasonablesize problems.