# Batch Delivery Scheduling with Multiple Decentralized Manufacturers

Authors: Shi Li; Xueling Zhong; Hong Li; Sujian Li
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

This paper addresses an integrated decision on production scheduling and delivery operations, which is one of the most important issues in supply chain scheduling. We study a model in which a set of jobs ordered by only one customer and a set of decentralized manufacturers located at different locations are considered. Specifically, each job must be assigned to one of the decentralized manufacturers to process on its single machine facility. Then, the job is delivered to the customer directly in batch without intermediate inventory. The objective is to find a joint schedule of production and distribution to optimize the customer service level and delivery cost. In our work, we discuss this problem considering two different situations in terms of the customer service level. In the first one, the customer service is measured by the maximum arrival time, while the customer service is measured by the total arrival time in the second one. For each situation, we develop a dynamic programming algorithm to solve, respectively. Moreover, we identify a special case for the latter situation by introducing its corresponding solutions.


---

## Body

## 1. Introduction

Supply chain scheduling has attracted a lot of attention in recent years. One of the important issues in this research area is the integration scheduling of production and delivery operations. In the make-to-order applications, manufacturers produce the ordered products and then deliver them to the customers directly without holding intermediate inventories. Nowadays, it is a quite common background in our social production activities, since it can improve the efficiency of certain production processes. In this context, the customer may cooperate with several manufacturers whose production capacity is of no significant difference. However, we sometimes have to face the fact that these manufacturers are located at decentralized places. In consequence, the transportation between each manufacturer and customer needs time and cost. This paper thus investigates a joint schedule of production and delivery in order to optimize both customer service level and delivery cost. Here, customer service level is measured by a function of the time when the jobs are delivered to the customers, while the delivery cost consists of a fixed charge and a variable cost.The rest of this paper is organized as follows. Section2 reviews the related research work in the literature. In Section 3, we describe the problem addressed and introduce the notation used. Section 4 details the service measure form of maximum arrival time. Next, a dynamic programming algorithm is proposed to find an optimal solution. In Section 5, we first study the service measure form of total arrival time and then a dynamic programming algorithm is developed to solve it optimally as well. For this problem, we study a special case. Finally, our conclusions are given in Section 6.


## 2. Literature Review

A considerable amount of work has been done on batch delivery problems in the literature. Cheng and Kahlbacher [1] studied a single machine batch delivery scheduling to minimize the sum of the total weighted earliness and delivery cost. In their work, the earliness of a job is defined as the difference between its delivery time and completion time. Cheng and Gordon [2] discussed a problem which involves a set of independent jobs that are to be partitioned into several batches and sequenced for processing by a single machine. Later, Cheng et al. [3] further show that this problem can be formulated as a classical parallel machine scheduling problem, and thus the complexity results and algorithms for the corresponding parallel machine scheduling problem can be easily extended to the problem. Cheng et al. [4] studied the single machine batch delivery problem to minimize the sum of the total weighted earliness and mean batch delivery time. Ji et al. [5] studied batch delivery scheduling on a single machine. The objective is to minimize the sum of the total weighted flow time and delivery cost. Wang and Cheng [6] studied parallel machine scheduling with batch delivery cost. The objective is to minimize the sum of the total flow time (i.e., equal weights) and delivery cost. Hall and Potts [7] studied a variety of problems where a supplier makes deliveries to several manufacturers, who also make deliveries to customers. The objective is to minimize the overall scheduling and delivery cost. Hall and Potts [8] considered several scheduling problems with batch delivery. The objective is to minimize the scheduling cost plus the delivery cost, and both single and parallel machine environments are considered. Note that delivery cost is defined as the nondecreasing function of the number of batch in [1–8].In fact, most of the above research work considers customer service as their objective but without taking the transportation cost into account, or they assume that jobs can be delivered to customers instantaneously without any transportation delay. However, another set of batch delivery problems take transportation time and cost into account. Lee and Chen [9] incorporated transportation time and vehicle capacity requirements into machine scheduling models. They analyzed the complexity of various models in which jobs are first processed by machines and then delivered by one or more vehicles to a single customer. The vehicles have finite or infinite capacity and there is a transportation time for each customer of the delivery. Chang and Lee [10] extended Lee and Chen’s work to the situation when each job occupies a different amount of space in the vehicle. Chen and Vairaktarakis [11] studied the problem of minimizing a convex combination of service level and distribution cost. The distribution cost of a delivery shipment consists of a fixed charge and a variable cost proportional to the total distance of the route taken by the shipment. Wang and Cheng [12] considered the identical parallel machine scheduling with job class setups and delivery to multiple customers. The delivery cost consists of a fixed charge and a variable cost related to the quantity of the delivery jobs. Li et al. [13] developed a single machine scheduling model that incorporated routing decisions of a delivery vehicle which serves customers at different locations. They considered the case where the single vehicle is infinite or bounded capacity. The objective is to minimize the sum of job arrival time. A similar problem setting of [13] is considered by Geismar et al. [14], who assume that a fixed limited number of trucks is available and the objective is to minimize the time to produce and deliver all jobs to all customers. Chen and Lee [15] studies a general two-stage scheduling problem, in which jobs of different importance are processed by one first-stage processor and then, in the second stage, the completed jobs need to be batch delivered to various prespecified destinations in one of a number of available transportation modes. The objective is to minimize the sum of weighted job delivery time and total transportation cost.It is worth mentioning that, different from all the above cases, Chen and Pundoor [16] studied a problem in which multiple decentralized manufacturers with nonidentical production capacity are located at different locations and have different production cost. Finished jobs are shipped to the single customer with fixed batch delivery cost, and each delivery batch has a capacity limit. The decision is to assign jobs to manufacturers to determine the processing sequences and to obtain a delivery schedule for the finished jobs.In this paper, we focus on the integration of production scheduling and batch delivery model where multiple decentralized manufacturers are located at different locations, but only one customer is considered. More clearly, a set of jobs needs to be produced by manufacturers for a customer. After completing jobs, all the manufacturers must directly deliver them in batch to the customer by vehicle. We assume that each manufacturer has sufficient vehicles to use. A delivery batch incurs a fixed cost and a variable cost related to the number of jobs in that batch. The batch size is bounded by the capacity of the delivery vehicle. The objective is to determine the job assignment to multiple manufacturers and job processing sequence in each manufacturer together with the delivery schedule, so as to balance the customer service level and delivery cost. As introduced above, the problems discussed by Chen-Pundoor [16] are somewhat similar to ours. However, there are the following significant differences between two research works. (1) In our model a delivery batch of each manufacturer incurs not only a fixed cost but also a variable cost. Consequently, they make our problems more difficult to solve. (2) For the problem with the service level of the maximum arrival time, we propose a dynamic programming algorithm to solve it optimally, but Chen and Pundoor solved the similar problem by heuristics. (3) For the problem with the service level of the total arrival times, we propose a dynamic programming algorithm with time complexity of O(mnm) to solve it optimally, while Chen and Pundoor solved the problem with agreeable processing time and production cost by a dynamic programming algorithm with time complexity of O(nm+1mc2m). (4) We consider a special case of the problem with the service level of the total arrival time and solve it optimally by a polynomial algorithm. However, this point was not brought by Chen and Pundoor.


## 3. Problem Description

In this section, we describe our model formally. There arem manufacturers M={M1,M2,…,Mm}, which are located at different locations. Each manufacturer has a single machine facility. A customer plans to order n job, denoted by N={1,2,…,n}. Each of these jobs should be assigned to one of decentralized manufacturers to process on its single machine facility and then delivered to the customer directly in batch without intermediate inventory. More precisely, an example with 5 manufacturers and 1 customer is shown in Figure 1, where the lines represent the delivery of job. From this figure, as introduced earlier, we can see that there exist different manufactures located at different geographic areas but only one customer to consider.Figure 1
An example of the problem.Indeed, each jobj∈N has a processing time of pj units. Job preemption is not allowed; that is, processing a job on a machine can not be interrupted until it is finished. All jobs and machines are available at time 0. All the finished jobs produced by each manufacturer need to deliver in batch to the customer by the vehicle. A vehicle used by each manufacture must depart only when all the assigned jobs have completed their processing. Suppose that there are enough homogeneous vehicles available to deliver jobs at each manufacturer location and each vehicle can be loaded at most c jobs in a batch. This indicates that the total number of jobs delivered in a batch is no greater than c. Let ti denote the spending time when a vehicle travels from manufacturer i to the customer, for Mi∈M. Let Aj denote the time when the completed jobs arrive at the customer, for j∈N. With regard to the customer service level, we consider two particular forms:(i)
maximum arrival time; that is,Amax⁡=max⁡{A1,…,An};(ii)
total arrival times; that is,∑j∈N‍Aj=A1+⋯+An.So, we consider this problem with two forms of customer service, level respectively. The batch delivery cost from manufacturer Mi to the customer needs total cost of fi+yci, where fi is denoted by the fixed charge, y≤c is denoted by the quantity of the delivered job in the batch, and ci is denoted by the cost of each job delivered from Mi to the customer, for Mi∈M. Let Bik denote thekth batch in Mi. Let T=∑i=1m‍(Vifi+∑k=1Vi‍bikci)=∑i=1m‍Vifi+nici be the total delivery cost, where Vi is denoted by the number of delivery batches in Mi, ni is denoted by the number of jobs that assigned to process on the machine of Mi, and bik is denoted by the batch size of Bik (the number of jobs in Bik).Adopting the extensive three-field notation, the problem can be denoted bym→1,1|c|Y+T, where the first part m→1 of α field represents m manufacturers service for only single customer and the second part of α field represents that the processing facility in each manufacturer is single machine. The value of c under β represents the vehicle capacity. The objective functions that we consider under γ comprise a delivery cost T and a customer service cost Y, where Y=Amax⁡ or Y=∑j∈N‍Aj.


## 4. Maximum Arrival Time

In this section, we focus on problemm→1,1|c|Amax⁡+T. We present the following lemma which establishes several properties for an optimal solution to the problem. The proof is trivial and omitted.Lemma 1.
There exists an optimal solution to problemm→1,1|c|Amax⁡+T in which (1) there is no idle time at the beginning or between any two consecutively processed jobs on the machine of each manufacturer; (2) each batch delivery occurs when the last job of batch completes processing; (3) if manufacturer Mi has been assigned to ni jobs, each of the first ⌈ni/c⌉-1 batches includes c jobs and the last one includes ni-(⌈ni/c⌉-1)c jobs for i=1,2,…,m.First, we consider the complexity issues. On one hand, when both the delivery cost and delivery time are negligible, problemm→1,1|c|Amax⁡+T is reduced to the parallel machine scheduling problem with minimizing the makespan, denoted by P∥Cmax⁡. On the other hand, P∥Cmax⁡ is NP-hard in the ordinary sense when m is fixed and NP-hard in the strong sense when m is arbitrary. Thus, we have the the following theorem.Theorem 2.
Even iffi=0, ci=0 and ti=0, for any i=1,2,…,m, problem m→1,1|c|Amax⁡+T is NP-hard in the ordinary sense when m is fixed and NP-hard in the strong sense when m is arbitrary.We now develop a dynamic programming algorithm to solve the problem. LetP=∑j=1n‍pj. The algorithm is formally described as follows.Algorithm DP1Step 1.
Value function: defineH(q1,…,qm,g1,…,gm) as the minimum sum of the maximum arrival time and the total delivery cost, given that qi jobs are assigned to manufacturer Mi so far and the arrival time of the last job in these qi jobs is equal to gi exactly.Step 2.
Initialization: sequence the jobs arbitrarily.
For eachgi=ti,ti+1,…,ti+P, qi=0,1,…,n, i=1,…,m,
(1)H(q1,…,qm,g1,…,gm)={0ifq1=q2=⋯=qm=0,g1=t1,g2=t2,…,gm=tm,∞otherwise.Step 3.
Recursive relations: forgi=ti,ti+1,…,ti+P, qi=0,1,…,n, i=1,…,m,
(2)H(q1,…,qm,g1,…,gm)=min⁡1≤i≤mmax⁡{H(g1,…,gi-pq,…,gmq1,…,qi-1,…,qm,g1,…,gi-pq,…,gm)+(⌈qic⌉-⌈qi-1c⌉)fi+ci,gi+∑δ=1m‍(⌈qδc⌉fδ+qδcδ).Step 4.
Optimal solution:min⁡{H(q1,…,qm,g1,…,gm)∣∑i=1mqi=n,gi=ti,ti+1,…,ti+P, qi=0,1,…,n,i=1,2,…,m}.Theorem 3.
Algorithm DP1 solves problemm→1,1|c|Amax⁡+T optimally in O(m(nP)m-1) time.Proof.
Assume that the firstj-1 jobs have been assigned. When we assign the next job j to manufacturer Mi, if job j is the one with maximum arrival time, then the objective value of these first j jobs is equal to gi+∑i=1m‍(⌈qi/c⌉fi+qici); otherwise, the objective value is the sum of H(q1,…,qi-1,…,qm,g1,…,gi-pq,…,gm) and the delivery cost of job j; that is, (⌈qi/c⌉-⌈qi-1/c⌉)fi+ci. This justifies (2). Since the value of optimal solution is determined by the minimum value with q1+⋯+qm=n, we have justified that that Algorithm DP1 solves the problem m→1,1|c|Amax⁡+T optimally.
We establish the running time complexity of Algorithm DP1 as follows. Sincem-1 of the values q1,…,qm are independent and m-1 of the values g1,…,gm are independent, the number of different states of the recursive relations is at most nPm-1. For each state, the right-hand side of (2) can be calculated in O(m) time. Thus, the overall time computational complexity of Algorithm DP1 is O(m(nP)m-1).Theorem3 implies that problem m→1,1|c|Amax⁡+T is NP-hard in the ordinary sense when m is fixed.


## 5. Total Arrival Times

### 5.1. General Case

In this subsection, we focus on problemm→1,1|c|∑j∈N‍Aj+T. When m is arbitrary, Chen and Pundoor proved the first problem in [16] is NP-hard in the strong sense by a reduction of the minimum cover problem, and when m is fixed, they pointed out that the computational complexity of the problem is open. If m is arbitrary, the computational complexity of problem m→1,1|c|∑j∈N‍Aj+T is NP-hard in the strong sense. The proof is similar to the computational complexity proof of the first problem in [16]. If m is fixed, based on the ideas from Cheng et al. [17], for a parallel machine batching problem, we propose a polynomial algorithm for problem m→1,1|c|∑j∈N‍Aj+T. The following lemma establishes several properties for an optimal solution to this problem. The proof is trivial and omitted.Lemma 4.
There exists an optimal solution to problemm→1,1|c|∑j∈N‍Aj+T in which (1) there is no idle time at the beginning or between any two consecutively processed jobs on a machine in the manufacturer; (2) all jobs assigned to the same manufacturer are scheduled with an order of nondecreasing processing times; (3) each batch is delivered when the last job in the batch completes processing; (4) any two consecutive batches Bik and Bik+1 satisfy bik≥bik+1 in each manufacturer Mi.Sort then jobs from the single customer with an order of nondecreasing processing times such that p1≤p2≤⋯≤pn. We have the following property.Lemma 5.
There exists an optimal solution to problemm→1,1|c|∑j∈N‍Aj+T in which the jobs in each batch are sequenced continuously; that is, the jobs in a batch are i,i+1,…,j, for some i,j,1≤i≤j≤n.Proof.
Given a schedule, the position weights on the machine ofMi are considered. Each job j∈Bik contributes its processing time pj to the completion time of every jobs in Bik∪Bik+1∪⋯∪BiVi. Hence, the position weight of each job in Bik is equal to wik=bik+bik+1+⋯+biVi. It is easy to see that the objective value of this schedule is equal to
(3)Δ=∑i=1m‍∑k=1Vi‍wik∑l∈Bik‍pl+(ci+ti)bik+Vifi.
If the number of batches at each manufacturer Vi(i=1,2,…,m) and the number of jobs in each batch bik(i=1,2,…,m,k=1,2,…,Vi) are fixed, then in order to minimize the value of Δ we should assign the job with the largest processing time to the position with the smallest position weight and the job with the second largest processing time to the position with the second smallest position weight and so on. Since the positions occupied by the jobs in the same batch have identical position weights, we get the desired result.Based on Lemmas4 and 5, we now develop a dynamic programming algorithm to solve problem m→1,1|c|∑j∈N‍Aj+T. The algorithm is formally described as follows:Algorithm DP2Step 1.
Value function: defineHj(q1,q2,…,qm) as the minimum sum of the total arrival times and the delivery cost if the last n-j+1 jobs have been considered and manufacturer Mi has been assigned qi jobs among the considered jobs for i=1,2,…,m. Clearly, ∑i=1m‍qi=n-j+1.Step 2.
Initialization: setj=n. For each λ=0,1,…,n,n+1, qi=0,1,…,n, and i=1,…,m,
(4)Hλ(q1,q2,…,qm)={0ifλ=n+1,q1=q2=⋯=qm=0,,∞otherwise.Step 3.
Recursive relations: forqi=0,1,…,n-j+1,
(5)Hj(q1,q2,…,qm)=min⁡{Hu(q1,…,qi-(u-j),…,qm)+qiPju+fi+(u-j)(ci+ti)∣j<u≤min⁡{j+c,n+1},i=1,…,m},
where Pju=∑l=ju-1‍pl. If Hj(q1,q2,…,qm)=Hη(q1,…,qθ-(η-j),…,qm)+qθPjη+fθ+(η-j)(cθ+tθ), then a batch containing jobs j,…,η-1 is assigned to the beginning of the processed sequence at manufacturer Mθ.
Ifj=1, then go to Step 4; otherwise, if j≠1, then set j=j-1 and repeat Step 3.Step 4.
Optimal solution:min⁡{H1(q1,q2,…,qm)∣qi=0,1,…,n,i=1,…,m, ∑i=1mqi=n}.Theorem 6.
Algorithm DP2 solves problemm→1,1|c|∑j∈N‍Aj+T optimally in O(mnm) time.Proof.
By Lemma5, we generate the batches containing consecutive jobs and construct the batch sequences in each manufacturers backwards in Algorithm DP2. Assume that manufacturer Mθ has been assigned α jobs in the current sequence and the batch containing jobs j,…,η-1(η-j≤c) is added to the beginning of the sequence. It is not difficult to calculate that the contribution of this batch to the objective value is (α+η-j)Pjη+fθ+(η-j)(cθ+tθ), where Pjη=∑l=jη-1‍pl is the total processing time of the jobs in the batch. This contribution depends only on the batch and on the number of jobs assigned to manufacturer Mθ. Then, we can recursively compute the value of Hj(q1,q2,…,qm). Finally, the optimal solution can be obtained when j=1. Thus, Algorithm DP2 solves the problem m→1,1|c|∑j∈N‍Aj+T optimally.
We establish the time complexity of Algorithm DP2 as follows. For eachj, there are at most (n-j+2)m-1 different states of (q1,q2,…,qm). For each state, computing the right-hand side of (5) needs at most O(c·m) time. Therefore, the overall computational complexity of Algorithm DP2 is O(n·c·m·∑j=1n‍(n-j+2)m-1), equivalently O(mnm).Theorem6 shows that when the number of manufacturers m is fixed, Algorithm DP2 solves the problem optimally in polynomial time.


### 5.2. Special Case

In this subsection, we consider a special case with the objective function of∑j∈N‍Aj+T. In this special case, at most, one job can be delivered in a batch; that is, c=1. Denote such a special case by m→1,1|c=1|∑j∈N‍Aj+T. It is easy to observe that when the delivery time and the delivery cost are negligible, problem m→1,1|c=1|∑j∈N‍Aj+T is reduced to the classical parallel machine scheduling problem to minimize makespan, denoted by P∥∑‍Ci. It is well known that P∥∑‍Ci is solved optimally by the generalized shortest-processing-time-first (SPT) rule, which can be described as follows: schedule the jobs with an order of nondecreasing processing time, consider the jobs in this order and assign the current considering job to the earliest available machine. By Lemma 4, we develop an algorithm, denoted by SA, which is similar to SPT rule. Let Gi denote the current value of the objective function at manufacturer Mi when considering the first j jobs, gi denote the total completion time of the jobs assigned to manufacturer Mi when considering the first j jobs, and G* denote the optimal value of the objective function. Algorithm SA is shown in detail as follows.Algorithm SAStep 1.
Sort and renumber then jobs with an order of nondecreasing processing times such that p1≤p2≤⋯≤pn. Set j=1. Set Gi=0 and gi=0 for i=1,…,m.Step 2.
WHILEj≤n DO
BEGINFind manufacturerMu with gu+fu+cu+tu=min⁡i=1,2,…,m{gi+fi+ci+ti};Assign jobj to manufacturer Mu; that is, set gu=gu+pj;SetGu=Gu+gu+fu+cu+tu;Setj=j+1.ENDStep 3.
SetG*=∑i=1mGi.Theorem 7.
Algorithm SA solves problemm→1,1|c=1|∑j∈N‍Aj+T optimally in O(nlog⁡n+mn) time.The optimality of Algorithm SA can be easily justified. In terms of the time complexity, sorting the jobs with an order of nondecreasing processing times in Step1 needs O(nlog⁡n) time, and executing Step 2 needs O(mn) time since it takes O(m) time to find the value of u. Hence, the overall running time complexity of algorithm SA is O(nlog⁡n+mn).Now, we present a numerical example for this special case to demonstrate the optimality of the algorithm.Example 8.
Consider the instance withn=6, m=3, and c=1. The delivery times and delivery cost to the customer are shown in Table 1. The processing times of jobs are given in Table 2.Table 1
The delivery time and delivery cost to the customer.
Manufacturers
1
2
3
t
i
1
4
2
f
i
+
y
c
i
2
+
6
y
4
+
3
y
5
+
yTable 2
The processing time of jobs.
j
1
2
3
4
5
6
p
i
3
5
7
8
8
10Using Algorithm SA to solve the instance, we have the following results:Whenj=1, find u=3, and so we have g3=3 and G3=11.Whenj=2, find u=1, and so we have g1=5 and G1=14.Whenj=3, find u=2, and so we have g2=7 and G2=18.Whenj=4, find u=3, and so we have g3=11 and G3=30.Whenj=5, find u=1, and so we have g1=13 and G1=36.Whenj=6, find u=2, and so we have g2=17 and G2=46.Therefore, the value of the optimal solution to Example8 generated by Algorithm SA is equal to G*=G1+G2+G3=35+46+30=112. In such an optimal solution, the assignment of all the jobs to manufacturers M1,M2, and M2 and the schedule on the machine of each manufacturer are illustrated in detail in Figure 2. In Figure 2, the horizontal axis represents time. In order to explain Figure 2, we see job 2. Job 2 is assigned to manufacturer M2; it starts to process on the single machine of manufacturer M2 at the point of time 0 and completes to process at the point of time 5 (shown in Figure 2). Once job 2 is completed to process, it is delivered as a batch to its customer immediately and needs 1 unit of delivery time and 8 units of delivery cost. Note that there does not show the delivery time and delivery cost of each job in Figure 2.Figure 2
The result of Example8.


## 5.1. General Case

In this subsection, we focus on problemm→1,1|c|∑j∈N‍Aj+T. When m is arbitrary, Chen and Pundoor proved the first problem in [16] is NP-hard in the strong sense by a reduction of the minimum cover problem, and when m is fixed, they pointed out that the computational complexity of the problem is open. If m is arbitrary, the computational complexity of problem m→1,1|c|∑j∈N‍Aj+T is NP-hard in the strong sense. The proof is similar to the computational complexity proof of the first problem in [16]. If m is fixed, based on the ideas from Cheng et al. [17], for a parallel machine batching problem, we propose a polynomial algorithm for problem m→1,1|c|∑j∈N‍Aj+T. The following lemma establishes several properties for an optimal solution to this problem. The proof is trivial and omitted.Lemma 4.
There exists an optimal solution to problemm→1,1|c|∑j∈N‍Aj+T in which (1) there is no idle time at the beginning or between any two consecutively processed jobs on a machine in the manufacturer; (2) all jobs assigned to the same manufacturer are scheduled with an order of nondecreasing processing times; (3) each batch is delivered when the last job in the batch completes processing; (4) any two consecutive batches Bik and Bik+1 satisfy bik≥bik+1 in each manufacturer Mi.Sort then jobs from the single customer with an order of nondecreasing processing times such that p1≤p2≤⋯≤pn. We have the following property.Lemma 5.
There exists an optimal solution to problemm→1,1|c|∑j∈N‍Aj+T in which the jobs in each batch are sequenced continuously; that is, the jobs in a batch are i,i+1,…,j, for some i,j,1≤i≤j≤n.Proof.
Given a schedule, the position weights on the machine ofMi are considered. Each job j∈Bik contributes its processing time pj to the completion time of every jobs in Bik∪Bik+1∪⋯∪BiVi. Hence, the position weight of each job in Bik is equal to wik=bik+bik+1+⋯+biVi. It is easy to see that the objective value of this schedule is equal to
(3)Δ=∑i=1m‍∑k=1Vi‍wik∑l∈Bik‍pl+(ci+ti)bik+Vifi.
If the number of batches at each manufacturer Vi(i=1,2,…,m) and the number of jobs in each batch bik(i=1,2,…,m,k=1,2,…,Vi) are fixed, then in order to minimize the value of Δ we should assign the job with the largest processing time to the position with the smallest position weight and the job with the second largest processing time to the position with the second smallest position weight and so on. Since the positions occupied by the jobs in the same batch have identical position weights, we get the desired result.Based on Lemmas4 and 5, we now develop a dynamic programming algorithm to solve problem m→1,1|c|∑j∈N‍Aj+T. The algorithm is formally described as follows:Algorithm DP2Step 1.
Value function: defineHj(q1,q2,…,qm) as the minimum sum of the total arrival times and the delivery cost if the last n-j+1 jobs have been considered and manufacturer Mi has been assigned qi jobs among the considered jobs for i=1,2,…,m. Clearly, ∑i=1m‍qi=n-j+1.Step 2.
Initialization: setj=n. For each λ=0,1,…,n,n+1, qi=0,1,…,n, and i=1,…,m,
(4)Hλ(q1,q2,…,qm)={0ifλ=n+1,q1=q2=⋯=qm=0,,∞otherwise.Step 3.
Recursive relations: forqi=0,1,…,n-j+1,
(5)Hj(q1,q2,…,qm)=min⁡{Hu(q1,…,qi-(u-j),…,qm)+qiPju+fi+(u-j)(ci+ti)∣j<u≤min⁡{j+c,n+1},i=1,…,m},
where Pju=∑l=ju-1‍pl. If Hj(q1,q2,…,qm)=Hη(q1,…,qθ-(η-j),…,qm)+qθPjη+fθ+(η-j)(cθ+tθ), then a batch containing jobs j,…,η-1 is assigned to the beginning of the processed sequence at manufacturer Mθ.
Ifj=1, then go to Step 4; otherwise, if j≠1, then set j=j-1 and repeat Step 3.Step 4.
Optimal solution:min⁡{H1(q1,q2,…,qm)∣qi=0,1,…,n,i=1,…,m, ∑i=1mqi=n}.Theorem 6.
Algorithm DP2 solves problemm→1,1|c|∑j∈N‍Aj+T optimally in O(mnm) time.Proof.
By Lemma5, we generate the batches containing consecutive jobs and construct the batch sequences in each manufacturers backwards in Algorithm DP2. Assume that manufacturer Mθ has been assigned α jobs in the current sequence and the batch containing jobs j,…,η-1(η-j≤c) is added to the beginning of the sequence. It is not difficult to calculate that the contribution of this batch to the objective value is (α+η-j)Pjη+fθ+(η-j)(cθ+tθ), where Pjη=∑l=jη-1‍pl is the total processing time of the jobs in the batch. This contribution depends only on the batch and on the number of jobs assigned to manufacturer Mθ. Then, we can recursively compute the value of Hj(q1,q2,…,qm). Finally, the optimal solution can be obtained when j=1. Thus, Algorithm DP2 solves the problem m→1,1|c|∑j∈N‍Aj+T optimally.
We establish the time complexity of Algorithm DP2 as follows. For eachj, there are at most (n-j+2)m-1 different states of (q1,q2,…,qm). For each state, computing the right-hand side of (5) needs at most O(c·m) time. Therefore, the overall computational complexity of Algorithm DP2 is O(n·c·m·∑j=1n‍(n-j+2)m-1), equivalently O(mnm).Theorem6 shows that when the number of manufacturers m is fixed, Algorithm DP2 solves the problem optimally in polynomial time.


## 5.2. Special Case

In this subsection, we consider a special case with the objective function of∑j∈N‍Aj+T. In this special case, at most, one job can be delivered in a batch; that is, c=1. Denote such a special case by m→1,1|c=1|∑j∈N‍Aj+T. It is easy to observe that when the delivery time and the delivery cost are negligible, problem m→1,1|c=1|∑j∈N‍Aj+T is reduced to the classical parallel machine scheduling problem to minimize makespan, denoted by P∥∑‍Ci. It is well known that P∥∑‍Ci is solved optimally by the generalized shortest-processing-time-first (SPT) rule, which can be described as follows: schedule the jobs with an order of nondecreasing processing time, consider the jobs in this order and assign the current considering job to the earliest available machine. By Lemma 4, we develop an algorithm, denoted by SA, which is similar to SPT rule. Let Gi denote the current value of the objective function at manufacturer Mi when considering the first j jobs, gi denote the total completion time of the jobs assigned to manufacturer Mi when considering the first j jobs, and G* denote the optimal value of the objective function. Algorithm SA is shown in detail as follows.Algorithm SAStep 1.
Sort and renumber then jobs with an order of nondecreasing processing times such that p1≤p2≤⋯≤pn. Set j=1. Set Gi=0 and gi=0 for i=1,…,m.Step 2.
WHILEj≤n DO
BEGINFind manufacturerMu with gu+fu+cu+tu=min⁡i=1,2,…,m{gi+fi+ci+ti};Assign jobj to manufacturer Mu; that is, set gu=gu+pj;SetGu=Gu+gu+fu+cu+tu;Setj=j+1.ENDStep 3.
SetG*=∑i=1mGi.Theorem 7.
Algorithm SA solves problemm→1,1|c=1|∑j∈N‍Aj+T optimally in O(nlog⁡n+mn) time.The optimality of Algorithm SA can be easily justified. In terms of the time complexity, sorting the jobs with an order of nondecreasing processing times in Step1 needs O(nlog⁡n) time, and executing Step 2 needs O(mn) time since it takes O(m) time to find the value of u. Hence, the overall running time complexity of algorithm SA is O(nlog⁡n+mn).Now, we present a numerical example for this special case to demonstrate the optimality of the algorithm.Example 8.
Consider the instance withn=6, m=3, and c=1. The delivery times and delivery cost to the customer are shown in Table 1. The processing times of jobs are given in Table 2.Table 1
The delivery time and delivery cost to the customer.
Manufacturers
1
2
3
t
i
1
4
2
f
i
+
y
c
i
2
+
6
y
4
+
3
y
5
+
yTable 2
The processing time of jobs.
j
1
2
3
4
5
6
p
i
3
5
7
8
8
10Using Algorithm SA to solve the instance, we have the following results:Whenj=1, find u=3, and so we have g3=3 and G3=11.Whenj=2, find u=1, and so we have g1=5 and G1=14.Whenj=3, find u=2, and so we have g2=7 and G2=18.Whenj=4, find u=3, and so we have g3=11 and G3=30.Whenj=5, find u=1, and so we have g1=13 and G1=36.Whenj=6, find u=2, and so we have g2=17 and G2=46.Therefore, the value of the optimal solution to Example8 generated by Algorithm SA is equal to G*=G1+G2+G3=35+46+30=112. In such an optimal solution, the assignment of all the jobs to manufacturers M1,M2, and M2 and the schedule on the machine of each manufacturer are illustrated in detail in Figure 2. In Figure 2, the horizontal axis represents time. In order to explain Figure 2, we see job 2. Job 2 is assigned to manufacturer M2; it starts to process on the single machine of manufacturer M2 at the point of time 0 and completes to process at the point of time 5 (shown in Figure 2). Once job 2 is completed to process, it is delivered as a batch to its customer immediately and needs 1 unit of delivery time and 8 units of delivery cost. Note that there does not show the delivery time and delivery cost of each job in Figure 2.Figure 2
The result of Example8.


## 6. Conclusion

In this paper, we study a joint schedule of production and distribution to optimize the customer service level and delivery cost. Moreover, two different situations are considered by measuring the customer service in terms of: (i) total arrival times and (ii) maximum arrival time. To deal with these two situations, two dynamic programming algorithms are introduced, respectively, which are pseudopolynomial when the number of manufacturers is fixed. We also identified a solvable special case for the latter situation. Compared with the related research work in the literature, we conclude our following contributions.(1) We extend the previous models with one manufacturer to a novel one with multiple decentralized manufacturers. (2) A delivery batch only incurs a fixed cost in the previous models. However, we consider here a model with a complicated cost structure in which a delivery batch of each manufacturer incurs not only a fixed cost but also a variable cost. (3) We propose the efficient dynamic programming algorithms to solve this problem optimally. However, heuristics was often developed for similar problems in the literature.For future research, it will be worth considering the design of efficient and effective heuristics for the problems considered here. Our interesting research topic is also to study the extension of the current scheduling model with other objective functions, such as minimizing the total (weighted) tardiness or the number of the tardy jobs. Moreover, alternative machine configurations like flowshop facilities is a promising direction to study. At last, it might be worthy to extend the model with multiple decentralized manufacturers and multiple decentralized customers.



---

*Source: 321513-2014-08-31.xml*