# Parallel-Batch Scheduling and Transportation Coordination with Waiting Time Constraint

Authors: Hua Gong; Daheng Chen; Ke Xu
Journal: The Scientific World Journal
 (2014)

---

## Abstract

This paper addresses a parallel-batch scheduling problem that incorporates transportation of raw materials or semifinished products before processing with waiting time constraint. The orders located at the different suppliers are transported by some vehicles to a manufacturing facility for further processing. One vehicle can load only one order in one shipment. Each order arriving at the facility must be processed in the limited waiting time. The orders are processed in batches on a parallel-batch machine, where a batch contains several orders and the processing time of the batch is the largest processing time of the orders in it. The goal is to find a schedule to minimize the sum of the total flow time and the production cost. We prove that the general problem is NP-hard in the strong sense. We also demonstrate that the problem with equal processing times on the machine is NP-hard. Furthermore, a dynamic programming algorithm in pseudopolynomial time is provided to prove its ordinarily NP-hardness. An optimal algorithm in polynomial time is presented to solve a special case with equal processing times and equal transportation times for each order.


---

## Body

## 1. Introduction

A supply chain is made of all the stages of value creation such as supply, production, and distribution. In logistics management, there are usually transportation of raw materials or semifinished products and distribution of products. Researches on supply chain management focus on developing strategies to help companies to improve optimal chain-wide performance by proper coordination of the different stages of supply chains. For an order, transportation of raw materials or semifinished products and production are two key operations in the supply chain system. A scheduling problem with the limited waiting time occurs when the processing of orders that finished transportation has to start in a given time. There are several industries where the transportation and production scheduling problem is influenced by the limited waiting time. Examples include fresh food and chemical and automobile industries. For instance, in case of fresh food production, canning operation must follow cooking operation to ensure freshness after transportation of raw materials. Additional applications can be found in the advanced automobile manufacturing environments such as just-in-time systems. Auto parts of orders are transported from suppliers to producers for further assembling. The producers must process the orders arrived at the factory in a given time in order to decrease the inventory level and increase the production level. This situation is relevant to logistics and supply chain management and specifically addresses how to balance the transportation rate of raw materials and the production rate.Motivated by the aforementioned problem in logistics management, this paper describes a coordinated model for scheduling transportation of raw materials or semifinished products and parallel-batch production with waiting time consideration. There is a set of orders located at the different suppliers. The orders are transported by some vehicles to a manufacturing facility to be further processed. But only one order can be transported at a time. Each order arriving at the facility must be processed in its given waiting time. The orders are processed in batches on a parallel-batch machine, where a batch contains several orders and the processing time of the batch is the largest processing time of the orders in it. The goal is to find a schedule to minimize the sum of the total flow time and the production cost.Production scheduling problems with transportation considerations have been studied by a number of researchers. The parallel-batch machine scheduling problems have been previously studied in other manufacturing systems, especially burn-in operations in the very large-scale integrated circuit manufacturing (e.g., [1–3]). We briefly discuss some work related to integrated production scheduling and transportation decisions. Some research (see [4–7]) has been done for two machine flow shop problems featuring transportation of semifinished products and batching processing. We mention the studies in [4–7]; however, the problems there do not consider parallel-batch production or they consider another kind of batching with a constant processing time. The models in [8, 9] consider the coordinated scheduling problems with two-stage transportation and machine production that incorporate the scheduling of jobs and the pickup of the raw materials from the warehouse and the delivery arrangement of the finished jobs. The above scheduling problems do not consider the waiting time constraints. Another line of production scheduling models with transportation decisions focuses on the delivery of finished jobs to customers with a limited number of vehicles. Interested readers for the delivery coordination are referred to the recent review in [10]. The parallel-batch machine scheduling problems with batch delivery are considered in [11, 12]. All of the papers reviewed in this section deal in some way with the coordination of production scheduling and transportation at logistics and operations area, but none of them addresses and deals with the problem from the limited waiting time point of view. We not only consider the scheduling problem involving transportation capacity and transportation times but also take into account the order waiting time constraint and the batch capacity. Here, the coordination of batch processing, transportation, and waiting time constraints is a decision about whether or not to reduce production cost and improve machine utilization.The remainder of this paper is organized as follows. In the next section, we introduce the notation to be used and describe the model. In Section3, we analyze the optimal properties of the problem and prove strong NP-hardness of the general problem. In Section 4, a dynamic programming algorithm is provided to solve the problem with equal processing times and we prove that this case is NP-hard in the ordinary sense. Section 5 deals with a case with equal processing times and equal transportation times and shows how to find the optimal schedule. The last section contains a conclusion and some suggestions for future research.


## 2. Description and Notation

Our problem is formally stated as follows. Given a set ofn orders (including some semifinished jobs or raw material in one order), J
=
{
J
1
,
…
,
J
n
}, which are located at the different suppliers. The orders need to be transported to a manufacturing facility and processed on a single parallel-batch machine. Only m vehicles are available for transporting the orders, which can load only one order in one shipment. The vehicles are initially located at a transportation center. Let t
j denote the transportation time of order J
j from the supplier to the manufacturing facility. The transportation time from the factory back to the center is negligible. In the production part, each order J
j requires a processing time of p
i on the parallel-batch machine. The preemption of orders is not allowed. The parallel-batch machine can process a number of orders simultaneously as a batch as long as the total number of orders in the batch does not exceed the machine capacity c. The processing time of a batch is the longest processing time of all orders in it. Orders processed in the same batch have the same completion time, that is, their common start time (the start time of the batch in which they are contained) plus the processing time of the batch. Suppose that loading and unloading times are included in the transportation times and the processing times of orders. Associated with each order is w
j, which is the waiting time of an order for a period time from arriving at the machine to starting its processing on the machine. Here, w
j is restricted by a constant W where max
⁡
j
p
j
≤
W
≤
∑
p
j, such that the schedule has a feasible solution at least. Each batch requires a processing cost on the parallel-batch machine which reflects the production cost. The goal is to find a feasible schedule to minimize the sum of the total flow time and the total processing cost.Decision VariablesConsider the following:T
u: the total running time of vehicleu,
r
j: the arrival time of order J
j on the machine,
s
j: the starting time of order J
j on the machine,
w
j: the waiting time of order J
j on the machine, w
j
=
s
j
-
r
j
≤
W,
B
l: batchl,
b
l: the number of orders in B
l,
P
(
B
l
): the processing time of B
l on the machine, P
(
B
l
)
=
max
⁡
j
∈
B
l
{
p
j
},
S
l: the starting time of B
l on the machine,
D
l: the completion time of B
l on the machine,
C
j: the flow time of order J
j on the machine,
x: the number of batches,
X
(
x
): the total processing cost, a nondecreasing function ofx,
F
(
π
)
=
∑
j
=
1
n
C
j
+
X
(
x
): the objective function of a schedule π.We follow the commonly used three-field notation,α
|
β
|
γ, introduced to denote the problem under study. The problem is denoted by V
m
→
batch
|
w
j
|
∑
C
j
+
X
(
x
)whereαfield indicates that the orders are first transported by m vehicles and then processed on the parallel-batch machine.βfield describes the order restrictive requirement, andγdefines the objective function to be minimized.Specifically, the tradeoff between processing and transportation gives rise to the sequence of transportation and the batch composition decisions. The schedule may produce more batches in order to satisfy the waiting time requirements of orders. This leads to the increase of the total processing cost on the machine. On the other hand, if we create very few batches, then we may not obtain a feasible schedule due to waiting time constraint. Therefore, minimizing of the objective for the problem is achieved a feasible schedule for sequencing and batching to tradeoff the total flow time and the processing cost. The following example gives an illustration of this observation.Example 1.
Consider a set of 8 orders with their transportation times and processing times as shown below for the problemV
m
→
batch
|
w
j
|
∑
C
j
+
X
(
x
).Supposem
=
2,c
=
4,W
=
4, and X
(
x
)
=
3
x(see Table 1).Table 1
Order
1
2
3
4
5
6
7
8
t
j
1
1
2
2
2
3
4
4
p
j
2
3
4
3
3
3
4
4One vehicle transports the orders in turn:J
1,J
3,J
5, and J
7. Another vehicle transports the orders in turn: J
2,J
4,J
6, and J
8. The constructed schedule π consists of three batches, B
1
=
{
J
1
,
J
2
,
J
3
,
J
4
},B
2
=
{
J
5
,
J
6
}, and B
3
=
{
J
7
,
J
8
}, and has an objective value of 85. If another constructed schedule π
′ contains two batches B
1
=
{
J
1
,
J
2
,
J
3
,
J
4
},B
2
=
{
J
5
,
J
6
,
J
7
,
J
8
}, then the waiting time of the order J
5 is 5. Although schedule π
′ has a smaller processing cost, it is not feasible. From these two schedules, we see that a minimized objective can be obtained from a proper combination of the sequence of transportation and the batching of processing under the waiting time constraints.


## 3. The ProblemV
m
→
batch
|
w
j
|
∑
C
j
+
X
(
x
)

In this section, we analyze two properties of the scheduling problem and prove thatVm→batch|
w
j
|
∑
C
j
+
X
(
x
) is NP-hard in the strong sense by a reduction from the 3-Partition Problem, which is well known to be NP-hard in the strong sense [13].3-Partition Problem (3-PP). Given 3h items, H
=
{
1,2
,
…
,
3
h
}, each item i
∈
H has a positive integer size a
i satisfying a
/
4
<
a
i
<
a
/
2 and ∑
i
=
1
3
h
a
i
=
h
a, for some integer a. The question asked is whether there are h disjoint subsets H
1
,
H
2
,
…
,
H
h of H such that each subset contains exactly three items and its total size ∑
i
∈
H
j
a
i
=
a, j
=
1,2
,
…
,
h.Lemma 2.
For the problemVm→batch|
w
j
|
∑
C
j
+
X
(
x
), there exists an optimal schedule without idle time between orders on any vehicle.The proof of Lemma2 is straightforward and is omitted.The following result describes a candidate set of possible processing times.Lemma 3.
For the problemVm→batch|
w
j
|
∑
C
j
+
X
(
x
), there exists an optimal schedule in which each processing on the parallel-batch machine is made either at the arrival time of an order on the machine or immediately when the machine becomes available.Proof.
Assume that there is a process which is scheduled neither at the arrival time of an order nor at a time when the machine becomes available. This process can be changed to the latest earlier time which fits either of those conditions. Since the same orders can be processed at that earlier time and there are no additional processes, the objective value is not increased.Theorem 4.
The problemVm→batch|
w
j
|
∑
C
j
+
X
(
x
) is strongly NP-hard even if m
=
2.Proof.
To show the NP-hardness of the scheduling problem, we establish the following polynomial time reduction from the 3-PP. Given a 3-PP instance, we construct an instance forV
m
→
batch
|
w
j
|
∑
C
j
+
X
(
x
) as follows.
Number of Orders. Consider
(1)
n
=
7
h
+
7
,
Ordinary Orders. Consider
(2)
t
j
=
⌈
j
6
⌉
a
⌊
(
1
/
2
)
(
j
+
1
)
⌋
,
p
j
=
2
(
⌈
j
6
⌉
+
1
)
a
,
j
∈
H
=
{
1,2
,
…
,
6
h
}
.
Auxiliary Orders. Consider
(3)
t
j
=
2
(
j
-
6
h
)
a
,
j
∈
G
=
{
6
h
+
1
,
…
,
7
h
}
p
j
=
p
6
h
+
i
=
2
(
i
+
1
)
(
a
3
i
-
2
+
a
3
i
-
1
+
a
3
i
)
,
j
∈
G
=
{
6
h
+
1
,
…
,
7
h
}
,
t
j
=
0
,
p
j
=
2
a
,
j
∈
Y
=
{
7
h
+
1
,
…
,
7
h
+
7
}
,
Machine Capacity. Consider
(4)
c
=
7
,
Limited Waiting Time. Consider
(5)
W
=
2
a
h
,
Processing Cost Function. Consider
(6)
X
(
x
)
=
[
5
3
a
(
h
+
1
)
(
h
+
2
)
(
h
+
3
)
]
x
-
h
,
Threshold Value. Consider
(7)
y
=
4
a
(
h
+
1
)
(
h
+
2
)
(
h
+
3
)
.
Clearly, in a solution to this instance ofV
m
→
batch
|
w
j
|
∑
C
j
+
X
(
x
) with the objective value not exceedingy, we first prove the following properties: (
1
) since t
j
=
0, for j
∈
Y, all the orders of Y as the first batch must be processed on the machine in the time interval [
0
,
2
a
]; (
2
) there will be exactly h
+
1 batches in the optimal schedule, and each batch contains 7 orders. Suppose that there areq (more than h
+
1) batches in the schedule. Then 7
h
+
7 orders need at least h
+
1 batches due to c
=
7. If q
=
h
+
2, then the total processing cost is X
(
x
)
=
X
(
h
+
2
)
=
[
(
5
/
3
)
a
(
h
+
1
)
(
h
+
2
)
(
h
+
3
)
]
2
>
y. Thus, all the orders of H
∪
G are divided into h batches; that is, all the batches are full.
We will show that the 3-PP instance has a solution if and only if there is a scheduleπ for the scheduling instance such that its objective value of π is no more thany.
→Assume that there is a solution to the 3-PP instance, H
1
,
H
2
,
…
,
H
h, then there is a schedule to our problem with an objective value of no more than y. We construct a schedule π for our problem as shown in Figure 1.
In this schedule, two vehicles begin to transport orders at time point 0. All the orders ofY are processed first on the machine as the first batch. In the interval [
a
l
(
l
-
1
)
,
a
l
(
l
+
1
)
], vehicle 1 transports the orders of H
l,H
l
=
{
6
l
-
5
,
6
l
-
4
,
…
,
6
l
}, vehicle 2 transports J
6
h
+
l , for l
=
1
,
2
,
…
,
h. Since t
6
h
+
l
=
2
l
a and ∑
j
∈
H
l
t
j
=
2
l
a
,
J
6
h
+
l  and the last order of H
l arrive at the machine simultaneously, for l
=
1
,
2
,
…
,
h
,then  J
6
h
+
l and the corresponding orders of H
l form batch B
l. The waiting time of each order in B
l is smaller than W. Hence, the starting time of B
l on the machine is a
l
(
l
+
1
); the completion time of B
l is a
(
l
+
1
)
(
l
+
2
), for l
=
0,1
,
2
,
…
,
h. It is easy to see that the above schedule is optimal and the objective value isy.
←On the contrary, suppose that there exists a schedule for the constructed instance with the objective value not exceedingy.
Fact  1. In the schedule, B
l contains an auxiliary order J
6
h
+
l, for l
=
1
,
2
,
…
,
h.
Assume that there is some batchB
l that contains more than one auxiliary order. Assume that B
l contains two auxiliary jobs J
6
h
+
l  and J
6
h
+
k ; then there must be some batch B
k only consisting of the ordinary jobs, k
≠
l. Consider the following two cases.
Case  1. If k
=
l
-
1, then it is shown that B
l
-
1
=
{
J
6
l
-
11
,
…
,
J
6
l
-
6
,
J
j
′
∣
j
′
∈
H
l
}. The corresponding flow time of each order in B
l
-
1 satisfies C
j
=
a
l
(
l
+
1
)
+
2
a, forj
∈
B
l
-
1. The flow times of orders in each batch after B
l
-
1 will be greater than a
(
l
+
1
)
(
l
+
2
)
+
2
a. It is easy to see that ∑
C
j
=
4
a
(
h
+
1
)
(
h
+
2
)
(
h
+
3
)
+
14
(
h
-
l
+
2
)
a, 2
≤
l
≤
h. Hence, F
′
=
∑
C
j
+
X
(
h
+
1
)
>
y.
Case  2. If k
=
l
+
1, then it can be shown that two vehicles must transport two auxiliary orders of batch B
l, respectively. Due to the limited waiting time of orders, the completion time of batch B
l on the machine is greater than a
(
l
+
1
)
(
l
+
2
)
+
2
a. Furthermore, it is easy to see that ∑
C
j
>
4
a
(
h
+
1
)
(
h
+
2
)
(
h
+
3
)
+
14
(
h
-
l
+
1
)
a, 1
≤
l
≤
h
-
1, which implies F
′
>
y.
Fact  2. Each batch B
l must contain 6 orders of H
l
=
{
6
l
-
5,6
l
-
4
,
…
,
6
l
} such that ∑
j
∈
H
l
t
j
=
2
l
a, for l
=
1
,
2
,
…
,
h.
By the above argument, since each batch is full, we can show that one vehicle transports the orders ofH
l one by one, and another vehicle transports J
6
h
+
l  in the time interval [
a
l
(
l
-
1
)
,
a
l
(
l
+
1
)
]. The orders {
J
6
h
+
l
,
H
l
} as B
l are processed on the machine in the time interval [
a
l
(
l
+
1
)
,
a
(
l
+
1
)
(
l
+
2
)
]. It must be true that ∑
j
∈
H
l
t
j
=
2
l
a, for l
=
1,2
,
…
,
h. Otherwise, if ∑
j
∈
H
l
t
j
<
2
l
a, then p
6
h
+
l
=
2
(
l
+
1
)
·
(
a
3
l
-
2
+
a
3
l
-
1
+
a
3
l
)
<
2
(
l
+
1
)
a. We can obtain some batch B
k whose processing time is greater than 2
(
k
+
1
)
a, k
≠
l. Hence, F
′
>
y, which is a contradiction.
Therefore, a partition for the setH is obtained by letting the elements be corresponding to batch B
l. Then it is easy to see that q
=
h
+
1 and h batches B
1
,
…
,
B
h form a solution to the 3-PP instance. The proof is concluded.Figure 1
The schedule of Theorem4.Theorem4 indicates that the existence of a polynomial time algorithm to solve the scheduling model is unlikely. Since the general problem is strongly NP-hard, we next consider two special cases of the problem.


## 4. The ProblemV
m
→
batch
|
p
j
=
p
,
w
j
|
∑
C
j
+
X
(
x
)

We now turn our attention to a special case with identical processing time condition on the machine. In this section, we prove that the problemV
m
→
batch
|
p
j
=
p
,
w
j
|
∑
C
j
+
X
(
x
) is ordinarily NP-hard by a reduction of the Partition Problem [13] which is a known NP-hard problem and provides a dynamic programming algorithm in pseudopolynomial time.Suppose a feasible scheduleπ
=
{
B
1
,
B
2
,
…
B
x
} with x
∈
{
⌈
n
/
c
⌉
,
…
,
n
} batches for the problem V
m
→
batch
|
p
j
=
p
,
w
j
|
∑
C
j
+
X
(
x
). We now present some properties for the problem.Lemma 5.
ForVm→batch|
p
j
=
p
,
w
j
|
∑
C
j
+
X
(
x
), there exists an optimal schedule π
*such that all orders assigned into the same vehicle are scheduled in the nondecreasing sequence of their transportation times.Proof.
Assume that ordersJ
i and J
j are assigned to the same vehicle. J
i is followed by J
j immediately such that t
i
≥
t
j in π
*. Let π
′ be a schedule obtained by swapping J
i and J
j. In π
′, it is easy to see that r
i
>
r
j
′ and r
i
′
=
r
j. Regardless of whether J
i and J
j are processed in the same batch or not, the starting times of J
i and J
j on the machine cannot increase. We have F
(
π
*
)
≥
F
(
π
′
).Lemma 6.
For any scheduleof the problemVm→batch|
p
j
=
p
,
w
j
|
∑
C
j
+
X
(
x
), the starting time of batch B
l satisfies S
l
+
1
≥
S
l
+
p for l
=
1,2
,
…
,
x.Proof.
It is easily obtained based on Lemma3.Lemma 7.
For any schedule of the problemVm→batch|
p
j
=
p
,
w
j
|
∑
C
j
+
X
(
x
), B
l contains all orders which have arrived at the machine if the number of the orders is no more than the capacity c in the time interval (
S
l
-
1
,
S
l
].Proof.
Assume that the batches are numbered in accordance with their start times, and the number of orders in each batch is smaller than the machine capacityc. Suppose that J
j is the first order assigned in B
l
+
1 in π
*, and the arrival time of J
j on the machine satisfies r
j
≤
S
l. Let π
′ be a new schedule obtained by simply assigning J
j to B
l. Then C
j
′
=
S
l
+
p
<
S
l
+
1
+
p
≤
C
j. The schedule of the remaining orders in π
′ are the same as in π
*. It is obvious that F
(
π
′
)
≤
F
(
π
*
). We can see that there exists an optimal schedule in which all batches consist of a number of orders which finish processing contiguously.We will show that the problem with equal processing times is NP-hard by a reduction from the Partition Problem.Theorem 8.
The problemVm→batch|
p
j
=
p
,
w
j
|
∑
C
j
+
X
(
x
) is NP-hard even if m
=
2.Proof.
We prove this result by reducing the Partition Problem toVm→batch|
p
j
=
p
,
w
j
|
∑
C
j
+
X
(
x
). The Partition Problem (PP) can be stated as follows: given h items, H
=
{
1,2
,
…
,
h
}, each item i
∈
H has a positive integer size a
i, such that ∑
i
=
1
h
a
i
=
2
a, for some integer a. The question asked is whether there are two disjoint subsets H
1 and H
2, such that ∑
i
∈
H
1
a
i
=
∑
i
∈
H
2
a
i
=
a.
We construct a corresponding instance of the problemVm→batch|
p
j
=
p
,
w
j
|
∑
C
j
+
X
(
x
) as follows.
Number of Orders. Consider
(8)
n
=
2
h
.
Transportation Times. Consider
(9)
t
j
=
a
j
,
j
∈
H
=
{
1,2
,
…
,
h
}
;
t
j
=
0
,
j
∈
Y
=
{
h
+
1
,
h
+
2
,
…
,
2
h
}
.
Processing Times. Consider
(10)
p
j
=
a
,
j
=
1,2
,
…
,
2
h
.
Limited Waiting Time. Conider
(11)
W
=
a
.
Processing Cost Function. Consider
(12)
X
(
x
)
=
3
a
h
x
.
Machine Capacity. Consider
(13)
c
=
h
.
Threshold Value. Consider
(14)
y
=
9
a
h
.
First, it is easy to see that, in a solution to this instance ofVm→batch|
p
j
=
p
,
w
j
|
∑
C
j
+
X
(
x
) with the objective value not exceeding y. We first prove the following property: since t
h
+
1
=
⋯
=
t
2
h
=
0, all the orders of Y as the first batch must be processed on the machine in the time interval [0,a]. Now, we prove that there is a solution to the constructed instance ofVm→batch|
p
j
=
p
,
w
j
|
∑
C
j
+
X
(
x
) with total cost not exceeding y if and only if there is a solution to the PP instance.
→If there is a solution to the PP instance, we show that there is a schedule for the above-constructed instance with an objective value of no more than y. Let H
1 and H
2 be subsets of H that solves the PP instance. Vehicle 1 and Vehicle 2 transport the orders of H
1 and the orders of H
2, respectively. Let T
u be the total running time of vehicleu, for u
=
1,2. Since ∑
j
∈
H
1
t
j
=
∑
j
∈
H
2
t
j
=
a, we have T
1
=
T
2
=
a. In fact, the completion time of the first batch on the machine is a. We can obtain that the waiting time of each order on the machine is not greater than a. Let B
1
=
Y and B
2
=
H. It is easy to see that b
1
=
b
2
=
h, and the total flow time of all the orders is 3ha. Hence, the objective isy.
←Given a schedule with an objective value not exceedingy, then there must be a solution to the PP instance. We can obtain that all the orders in H are processed in the second batch on the machine; that is, all the orders are divided into two batches and b
1
=
b
2
=
h. Suppose that the number of the batches is greater than 2. Note that even if the waiting time constraint is ignored, the objective value is F
≥
a
h
+
∑
j
∈
H
C
j
+
9
a
h
>
y, which is a contradiction. Thus, π
=
{
B
1
,
B
2
} and B
1
=
Y and B
2
=
H.
IfT
1
=
∑
j
∈
H
1
t
j
<
a, then it implies T
2
=
∑
j
∈
H
2
t
j
>
a. Hence, the starting time of batch B
2 is S
2
=
T
2. It implies that the total flow time is ∑
C
j
=
a
h
+
(
S
2
+
a
)
h
>
3
a
h. We have F
>
y, which is a contradiction. Thus, ∑
j
∈
H
1
a
j
=
∑
j
∈
H
2
a
j
=
a.LetT
=
∑
j
=
1
n
t
j. In the following, we derive a dynamic programming algorithm in pseudopolynomial time to solve the problemVm→batch|
p
j
=
p
,
w
j
|
∑
C
j
+
X
(
x
).Algorithm D1.
Index the orders in the nondecreasing transportation time sequence; that is,t
1
≤
t
2
≤
⋯
≤
t
n.
DefineH
R
(
j
,
i
,
l
,
T
1
,
T
2
,
…
,
T
m
) and f
R
(
j
,
i
,
l
,
T
1
,
T
2
,
…
,
T
m
) as the minimum objective value and the minimum total flow time of a partial schedule of orders J
1
,
…
,
J
j, respectively, where orders J
1
,
…
,
J
j have finished transporting and processing by using l batches on the machine, and the current batch B
l contains orders J
i
,
…
,
J
j.
Initial Conditions. Consider
(15)
H
x
(
j
,
i
,
l
,
T
1
,
T
2
,
…
,
T
m
)
=
{
0
,
j
=
0
,
i
=
0
,
l
=
0
,
T
1
=
T
2
=
⋯
T
m
=
0
∞
,
otherwise
,
for S
1
≥
t
1, l
=
1,2
,
…
,
x, x
∈
{
⌈
n
/
c
⌉
,
…
,
n
}, and T
u
=
0,1
,
…
,
T.
Recursive Relations. Consider
(16)
f
x
(
j
,
i
,
l
,
T
1
,
T
2
,
…
,
T
m
)
=
{
min
⁡
1
≤
u
≤
m
{
f
x
(
j
-
1
,
i
,
l
,
T
1
,
…
,
T
u
-
t
j
,
…
,
T
m
)
+
C
j
}
if
b
l
<
c
∞
if
b
l
≥
c
,
where C
j
=
{
S
l
+
p
|
S
l
-
1
<
T
u
≤
S
l
≤
T
u
′
+
W
,
l
=
1,2
,
…
,
x
}, for S
l
+
p
≤
S
l
+
1
≤
T
u
′
+
W
,
l
=
1
,
2
,
…
,
x, x
∈
{
⌈
n
/
c
⌉
,
…
,
n
}, and T
u
′
=
min
⁡
S
l
-
1
<
T
u
≤
S
l
{
T
u
}.
Optimal Solution. Consider
(17)
F
*
=
min
⁡
{
H
x
(
n
,
n
+
1
,
l
,
T
1
,
T
2
,
…
,
T
m
)
+
X
(
x
)
}
.Theorem 9.
Algorithm D1 can find an optimal schedule for the problemVm→batch|
p
j
=
p
,
w
j
|
∑
C
j
+
X
(
x
) inO(mn
3
T
m−1
W) time.Proof.
Based on Lemma5, there exists an optimal schedule with orders assigned to each vehicle in the nondecreasing transportation time sequence. If order J
j is assigned to vehicleu, then its starting time on the machine satisfies r
j
+
W
≤
T
u. If the number of orders in the current batch B
l is less thanc, order J
j can be assigned into B
l. The corresponding flow time increases S
l
+
p. Based on Lemma 3, we have S
l
-
1
<
T
u
≤
S
l
≤
T
u
′
+
W. This shows that Algorithm D1 can find optimal solution for the problem.
The time complexity of the algorithm can be established as follows. We observe thati
,
j
,
l
≤
n, T
u
≤
T, and m
-
1 of the value T
1
,
T
2
,
…
,
T
m are independent. Thus, the number of different states of the recursive relations is at mostn
3
T
m−1. For each state, each use requires O
(
m
W
). Therefore, the overall time complexity of Algorithm D1 isO(mn
3
T
m−1
W).The existence of such a pseudopolynomial time algorithm for a NP-hard problem means that the problem is NP-hard in the ordinary sense. We have the following theorem.Theorem 10.
The problemVm→batch|
p
j
=
p
,
w
j
|
∑
C
j
+
X
(
x
) is ordinarily NP-hard.


## 5. The ProblemV
m
→
batch
|
p
j
=
p
,
t
j
=
t
,
w
j
|
∑
C
j
+
X
(
x
)

In this section, we consider a special case with identical processing times and identical transportation times and derive a polynomial-time algorithm to solve it. It is evident that the problem reduces to an optimal batching problem on the machine for the special case. Note thatx is a decision variable denoting the number of batches on the machine. Note that n
0
=
⌈
n
/
m
⌉ and g
=
n
0
m
-
n; let n
u be the number of orders transported on vehicle u under a specific schedule. Note that n
0
′
=
⌈
n
/
c
⌉ and n
0
′
≤
x
≤
n
0, if c
≥
m. Hence, the number of batches x on the machine can be numbered by n
0
′, n
0
′
+
1
,
…
,
n
0. Otherwise, n
0
≤
x
≤
n
0
′ if c
<
m. Without loss of generality, assume that c
≥
m in the following discussion. Let π
*
=
(
B
1
,
B
2
,
…
B
L
) be an optimal schedule with given x
=
L batches for the problemVm→batch|
p
j
=
p
,
t
j
=
t
,
w
j
|
∑
C
j
+
X
(
x
). Then we have the following lemma.Lemma 11.
For the problemVm→batch|
p
j
=
p
,
t
j
=
t
,
w
j
|
∑
C
j
+
X
(
x
), there exists an schedule with L batches in which (
1
)   n
0
-
1
≤
n
u
≤
n
0, u
=
1,2
,
…
,
m, (
2
)   b
-
l
=
b
l
/
m, b
-
l is integral, and l
=
1,2
,
…
,
L
-
1, and (
3
)    S
l
+
1
=
max
⁡
{
r
j
,
S
l
+
p
}, where r
j denotes the arrival time of some m jobs on the machine, l
=
1,2
,
…
,
L
-
1.Proof.
(
1
) Based on Lemma 2, each vehicle has no inserted idle time during transporting. Assume that there exists an optimal schedule π
* in which the condition is not satisfied. Then there must be a pair of vehicles u and v such that n
u
≥
n
v
+
2 and the last order on vehicle u is processed in the last batch. If the last order on vehicle u is moved to the last position on vehiclev, then the objective value will not increase. By repeating this process, we can obtain a desired optimal schedule.
(
2
) According to Lemma 7, in the optimal schedule, B
l contains all orders which finish transportation in the time interval (
S
l
-
1
,
S
l
], if the number of orders in a batch is no more than c. Since t
j
=
t for each order J
j,m orders arrive at the machine together. A batch contains m orders orkm
(
k
m
≤
c
) orders, if their waiting times are not greater than the limited value W. Hence, b
-
l is integral, for l
=
1,2
,
…
,
L
-
1.
(
3
) It is trivial according to Lemma 3.Based on these results, we can easily construct an optimal schedule for the problem.Algorithm D2.
Calculaten
0
=
⌈
n
/
m
⌉, n
0
′
=
⌈
n
/
c
⌉.
For eachL
=
n
0
′
,
n
0
′
+
1
,
…
,
n
0, compute b
-
l
=
b
-
0
-
1, l
=
1
,
⋯
,
h, b
-
l
=
b
-
0, and l
=
h
+
1
,
…
,
L, where b
-
0
=
⌈
n
0
/
L
⌉ and h
=
b
-
0
L
-
n
0.
Consider the following two cases.Case 1.
Considerh
=
0.
If(
b
-
0
-
1
)
t
>
W or m
b
-
0
>
c, then the constructed schedule is not feasible, and denote F
(
π
L
*
)
=
∞. If (
b
-
0
-
1
)
t
≤
W and m
b
-
0
≤
c, then S
1
=
b
-
0
t. According to Lemma 6, there must be b
-
0
t
l
+
t
+
W
≥
S
l
+
p. Otherwise, it is not feasible. Based on Lemma 7, we can obtain
(18)
S
l
+
1
=
max
⁡
{
b
-
0
t
(
l
+
1
)
,
S
l
+
p
}
,
l
=
1,2
,
…
,
L
-
1
.
The associated objective value can be derived as
(19)
F
1
(
π
L
*
)
=
min
⁡
{
∑
l
=
1
L
m
b
-
0
(
S
l
+
p
)
}
-
g
(
S
L
+
p
)
+
X
(
L
)
.Case 2.
Considerh
>
0.
If(
b
-
0
-
2
)
t
>
W or m
b
-
0
>
c, then it is not feasible, and denote F
(
π
L
*
)
=
∞. If (
b
-
0
-
2
)
t
≤
W and m
b
-
0
≤
c, then we can show S
1
=
(
b
-
0
-
1
)
t. According to Lemma 6, we have
(20)
(
b
-
0
-
1
)
t
l
+
t
+
W
≥
S
l
+
p
if
l
≤
h
(
b
-
0
-
1
)
t
h
+
b
-
0
t
(
l
-
h
)
+
t
+
W
≥
S
l
+
p
if
l
>
h
.
Otherwise, the constructed schedule is not feasible, and denote F
(
π
L
*
)
=
∞.
According to Lemma6, we have
(21)
S
l
+
1
=
max
⁡
⁡
{
(
b
-
0
-
1
)
t
(
l
+
1
)
,
S
l
+
p
}
if
l
≤
h
-
1
S
l
+
1

=

max
⁡
⁡
{
(
b
-
0
-
1
)
t
h
+
b
-
0
t
(
l
+
1
-
h
)
,
S
l
+
p
}
if
l
≥
h
,
l
=
1,2
,
…
,
L
-
1
.
The associated objective value can be derived as
(22)
F
2
(
π
L
*
)
=
min
⁡
{
∑
l
=
1
h
m
(
b
-
0
-
1
)
(
S
l
+
p
)
+
∑
l
=
h
+
1
L
m
b
-
0
(
S
l
+
p
)
}
-
g
(
S
L
+
p
)
+
X
(
L
)
.
Thus, the objective value is
(23)
F
(
π
L
*
)
=
min
⁡
{
F
1
(
π
L
*
)
,
F
2
(
π
L
*
)
}
.Theorem 12.
The problemVm→batch|
p
j
=
p
,
t
j
=
t
,
w
j
|
∑
C
j
+
X
(
x
) can be solved by Algorithm D2 in O
(
n
/
m
) time.Proof.
Equations (18) and (21) present that the machine can start to process B
l
+
1 as soon as the orders assigned into B
l
+
1 have arrived at the machine and the machine has finished processing B
l. The local optimal solution in two cases can be obtained by (19) and (22). The optimal solution is derived as (23). Hence, the optimal schedule to this special case can be obtained by repeating the above procedure for n
0
′
≤
L
≤
n
0 and selecting the best candidate among the solutions generated. This shows that Algorithm D2 can find optimal solution. It is clear that the overall time complexity of Algorithm D2 is O
(
n
/
m
).We now demonstrate the above algorithm with the following numerical example.Example 13.
Consider the instance with 11 orders,m
=
2,t
=
1,c
=
4,W
=
2,p
=
2, and X
(
x
)
=
5
x. Based on the above method, we know n
0
=
6, g
=
1, and n
0
′
=
2. Then, L
=
2
,
3
,
4
,
5
,
6. We have the following results:whenL
=
2, we have b
-
0
=
3, h
=
0,S
1
=
3, and F
(
π
*
)
=
80;
whenL
=
3, we have b
-
0
=
2, h
=
0,S
1
=
2, and F
(
π
*
)
=
79;
whenL
=
4, we have b
-
0
=
2, h
=
2,S
1
=
1, and F
(
π
L
*
)
=
101;
whenL
=
5, we have b
-
0
=
2
,
h
=
4,b
-
0
t
·
3
+
t
+
W
<
S
3
+
p, and F
(
π
L
*
)
=
∞;
whenL
=
6, we have b
-
0
=
1
,
h
=
0,b
-
0
t
·
3
+
t
+
W
<
S
3
+
p, and F
(
π
L
*
)
=
∞.
Therefore, we can obtain an optimal scheduleπ
* for L
=
3 with B
1
=
{
J
1
,
J
2
,
J
3
,
J
4
}, B
2
=
{
J
5
,
J
6
,
J
7
,
J
8
}, and B
3
=
{
J
9
,
J
10
,
J
11
}.


## 6. Concluding Remarks

In this paper, we address a coordinated scheduling problem with order transportation before processing and parallel-batch production under the limited waiting time consideration. Our goal is to optimize the sum of the total flow time and the total processing cost. First, we prove that the general problem is NP-hard in the strong sense. We also demonstrate that the problem with equal processing times on the machine is NP-hard. Furthermore, a dynamic programming algorithm in pseudopolynomial time is provided to prove its ordinarily NP-hardness. The problem with equal processing times and equal transportation times for each order can be solved in polynomial time through taking into account the properties of the special case. Our work has practical implications for the coordination of batch-production and transportation to improve the overall system performance in logistics and operations management. Simultaneously, another important implication of our paper may provide a vital approach to deal with the waiting time constraint applied to reduce the raw material consumption and improve the machine utilization.There are several possible extensions to this research. First, it is interesting to investigate the problems with other objective functions such as minimizing the makespan or minimizing maximum order tardiness/earliness. Another interesting issue is to develop effective heuristics to solve the general problem and investigate polynomial time algorithms for other special cases.



---

*Source: 356364-2014-04-15.xml*