iBusiness, 2013, 5, 27-30
doi:10.4236/ib.2013.51b006 Published Online March 2013 (http://www.scirp.org/journal/ib)
27
A Heuristic Approach for Assembly Scheduling and
Transportation Problems with Parallel Machines
Peng-Sheng You1, Yi-Chih Hsieh2, Ta-Cheng Chen3, Yung-Cheng Lee4
1Graduate Institute of Marketing and Logistics/Transportation, National Chiayi University, ChiaYi 600; 2Department of Industrial
Management, National Formosa University, Yunlin 632; 3Department of Information Management, National Formosa University,
Yunlin 632; 4Department of Security Technology and Management, WuFeng University, Chiayi 621.
Received 2013
ABSTRACT
Many firms have to deal with the problems of scheduling and transportation allocation. The problems of assembly
scheduling mainly focus on how to arrange orders in proper sequence on the assembly line with the purpose of mini-
mizing the maximum completion time before they are flown to their destinations. Transportation allocation problems
arise in how to assign processed orders to transport modes in order to minimize penalties such as earliness and tardiness.
The two problems are usually separately discussed due to their complexity. This paper simultaneously deals with these
two problems for firms with multiple identical parallel machines. We formulate this problem as a mixed integer pro-
gramming model. The problem belongs to the class of NP-complete combinatorial optimization problems. This paper
develops a hybrid genetic algorithm to obtain a compromised solution within a reasonable CPU time. We evaluate the
performance of the presented heuristic with the well-known GAMS/CPLEX software. The presented approach is shown
to perform well compared with well-known commercial software.
Keywords: Heuristic Approach; Scheduling; Transportation
1. Introduction
Assembly scheduling and transportation allocation are
two practical problems that industries usually face. Li et
al. [1,2] indicated that components in the PC industry are
usually stored in warehouses. When receiving orders
from customers, PC companies must arrange their orders’
processing sequence on the assembly line to assemble the
components for products. Then, an order is ready to be
shipped to the customer after assembly process is com-
pleted. Since each order has a due date, orders’ process-
ing sequence and transportation allocation decisions have
significant impact on whether the orders can be shipped
to their customers on time so as to reduce inventory
holding cost, and earliness and tardiness penalties. In
other words, in order to minimize overall costs, the
manufacturer must consider the following two problems
simultaneously: (1) production scheduling, which de-
scribes the orders’ processing sequence, and (2) trans-
portation allocation, which describes the allocation of
orders to various transport modes in the scheduling pe-
riod. A number of production scheduling and transporta-
tion allocation works have been separately studied [3-5].
Regarding the production scheduling problem, the pur-
pose of this research is similar to previous ones. On the
other hand, regarding the transportation allocation prob-
lem, this paper focuses on the issue of how to allocate
processed orders to transport modes. Researches on the
integration of production and distribution have received
much attention. Sarmiento and Nagi [6] provided a lit-
erature review on this area. Moreover, synchronization of
production and road transportation with emphasis on ve-
hicle routing problem also has studied by many research-
ers (Blumenfeld et al. [7], Chen and Vairaktaraki [8],
Fumero and Vercellis [9], Lee and Chen [10]). However,
limited works have studied the problem of synchronizing
production and transportation allocation. Li et al. [1] in-
vestigated a single destination’s air- transportation as-
signment problem with a single machine production floor
shop. Later, this work was extended by Li et al. [2] to a
cases with multiple destinations and by Li et al. [11] to a
case with parallel machines in assembly. Since the prob-
lem has been shown to be NP-hard [2], Li et al. [11] dealt
with the problems by decomposing it into two subprob-
lems. In the first subproblem, they solved the transporta-
tion allocation problem by determining the transportation
departure time for each order and meeting it with the as-
sembly. In the second subproblem, they dealt with the

A Heuristic Approach for Assembly Scheduling and Transportation Problems with Parallel Machines
28
assembly scheduling problem, where they scheduled the
orders in the assembly to meet the delivery requirements
of transportation. You and Hsieh [3] dealt with an assem-
bly and transportation allocation problem with a single
machine. The objective o this paper is to simultaneously
develop the decisions for production scheduling and
transportation allocation under multiple parallel machines
so as to minimize overall costs.
2. Model Description
A make-to-order manufacturer receives N orders from
distinct customers. Among these orders, order-i’s ship-
ping destination, order due date and order size are denote
by Gi, di and Qi, respectively. Before being transported to
their destinations, these orders need to be processed by
assembling components on one of Gi parallel machines.
The assembly sequence and release time of these N or-
ders have a direct impact on the inventory holding cost
and the selections of transportation. Inventory holding
cost incurs when there is waiting time before the com-
pleted order can be shipped to its destination. We use the
symbol hi to denote the holding cost of order i per unit
time. For each completed order, an order can be split and
allocated to more than one carriage and delivered sepa-
rately to its destination. Let F be the total number of car-
riages and Df be the departure time of carriage f. The
transportation cost per unit product, when allocated to
carriage f is denoted by cf. In addition to the transporta-
tion cost, an delivery earliness penalty cost exists if the
arrival time of an order reaches its destination airport
before its order due date, and a delivery tardiness penalty
cost if the order reaches its destination airport beyond its
order due date. The delivery earliness penalty cost per
unit product per unit time for order-i is denoted by αi.
The purpose is to minimize total cost, which consists of
inventory holding cost, the transportation cost of orders
allocated into carriages, delivery earliness penalty costs,
and delivery tardiness penalty. In addition to the previous
assumptions, we further make the following assumptions:
(1) The time and cost taken of transporting a completed
order by local transportation from the manufacturer to an
airport, together with the assembly setup time and cost of
each order, are included in the assembly time and cost. (2)
The total assembly processing time of an order is directly
proportional to its quantity. (3) Business processing time
and cost, together with load time and load cost of each
carriage, are included in the transportation time and
transportation cost. (4) Order fulfillment is considered to
be achieved when the order reaches its destination on
time.
The combined model aims to minimize the overall cost
by determining the orders' assembly sequence and allo-
cating orders to existing carriages. The factors which are
taken into account in the model include: (a) the number
of available carriages for the planning horizon, (b) the
departure and arrival time of the carriages, (c) the desig-
nated capacity and its corresponding transportation cost,
and (d) the possible capacity in each carriage with its
corresponding carriage cost. Prior to formulating the ma-
thematical model, we introduce some additional notation
as follows.
Notation:
k: the destination index, k =1,2,…,K.
Bf: the capacity of carriage f,
Gf: the destination of carriage f,
Pi: the processing time to assemble order i,
Af : the arrival time of carriage f,
xif : the quantity of the portion of order-i allocated to
carriage f,
yim :1 if order-i is assembled on machine m, 0 othewise,
Ri: the release time to assemble order i,
Ci: the assembly completion time of order i,
max
ij
P: maximum production capacity of manufacturer j
for order-i,
Zif : 1 if order-i is shipped by flight f, 0 otherwise,
PIijm: 1 if the processing sequence of order i precedes
processing sequence of order j on machine m, immedi-
ately, 0 otherwise.
Min

11
(max0, (
r
F
N
iff ii fif i
if
))
x
cdAhD 


 C (1)
Subject to
Z0,f=0,  f (2)
ZN+1,f=0,  f (3)
Zif=(Gi- G
f)2  0,  i, f (4)
1
1,1
r
F
if
f
Z
iN



 (5)
(1-Zif)M  Af- U
i,  i, f (6)
(1-Zif)M  Ci- D
f,  i, f (7)
xif= Z
if Qi,  i, f (8)
1
,
N
if f
i
x
Cap f



 (9)
Ci=Ri-Pi, 0iN+1 (10)
R1=0 (11)
1
1
N
N
i
i
R


P
N
(12)
1
1, 1
M
im
m
yi


 (13)
PIiim=0, 0iN+1, 0mM (14)
1
1
,1 ,1
N
ijm im
j
PIyiNm M



 (15)

A Heuristic Approach for Assembly Scheduling and Transportation Problems with Parallel Machines 29
1
,1 1,1
N
ijm jm
j
PIyjNm M


 (16)
PIi0m=0, 0iN+1, 0mM (17)
PIN+1jm=0, 0jN+1, 0mM (18)
Cj-Ci-MPIij  Pj-M, 0iN, 0jN (19)
Zif1, PIijm {0,1} (20)
3. Research Metholodgy
The proposed problem is a mix integer program. Due to
the computational complexity of the model, no approach
is guaranteed for solving the problem optimally within a
polynomial time. To overcome this difficulty, we will
develop a solution approach to obtain a compromised
solution within a reasonable CPU time. The approach is
an iteration method in which the concept of genetic algo-
rithm (GA) and mathematical programming are consid-
ered. We refer to it as HGA. GAs are a particular class of
evolutionary algorithms, which generate exact or ap-
proximate solutions to optimization and search problems
using techniques inspired by evolutionary biology. For
details, readers are referred to the textbook by Michale-
wicz [12]. The heuristic approach of HGA is addressed as
follows:
First, let smn be a n-dimensional vector with n orders
processed on machine m and element smn(j) at j-th entry
denoting the order corresponding to the j-th job processed
on machinem. Note that the processing release time of a
job does not necessarily happen immediately after the
completion time of its previous job. Let w be a
N-dimensional vector with element wj at j-th entry de-
noting the idle time between order j’s release time and its
proceeding job's completion time. For convenience, let
s0=0. Then, the relationship between Csmn(j-1) and Rsmn(j)
can be expressed as

1mn jmn jmn j
Rs Csws
 (21)
At each iteration of HGA, the values of the assembly
sequence smn and the idle times w are determined by GA.
The values of smn are used to derived the values of PIijm,
and the values of w are used to derived the values of ci
and Ri. The derived values satisfy constraints (10) to (19).
Solution procedure:
(a) Initial population:
The processing sequence is codified with N distinct in-
teger numbers within the range of [1,N]. Idle time w is
codified as a binary string. The first N elements of a
chromosome are used to generate assembly sequence on
each machine and the remaining represents the idle times.
(b) Genetic operators:
Four standard genetic operators, namely the Cloning
operator, Parent selection, Crossover operator and Muta-
tion operator repeatedly performed until the maximum
number of iterations Kmax is reached. An elitism strategy
and the Roulette-wheel selection are used in Cloning op-
erator and parent selection, respectively.
(c) Fitness:
Note the value of the first N entries of a chromosome,
(uj,…, uN), is used to generate assembly sequence on each
machine where uj is the order appearing at the j-th posi-
tion in the number sequence. The assignment of orders to
machines is according to the following rule. Let
'1
j
mj j
j
CP P

 (22)
be the minimum processed time needed to complete jobs
1 to j on machine m. In addition, let 
mj denote the num-
ber of orders assigned to machine m before order u
j is
assigned. Then, we sequentially assign orders to the ma-
chine with minimum value of CP. The sequence of the
orders on each machine also determines the values of
PIijm. Moreover, according to equation (21) and idle time,
we can further determines Ci and Ri. Let us refer to the
model obtained by substituting the known variables of
PIijm, Ci, Ri, yim into the original model as model-1. Then,
solving model-1 by linear programming, we can obtain xif,
zif and the objective value. The objective value is viewed
as fitness.
(d) Solution update:
Updating solution once the result obtained in step 3 is
smaller than the objective value found up to now.
(e) Stopping criteria:
Steps (2-4) are executed repeatedly until the stop crite-
rion is matched.
4. Experiments
The experiments was designed in terms of (K,F,M,N,T).
The combination of (3,10,2,10,24) is set. Ten test cases
were generated. The destination for each order and each
carriage was generated from uniform distribution over [1,
F]. The total assembly processing time of order i was set
at Pi =
 Qi. The due date of each order was generated over
[Pi+Ti, 6(Pi+Ti,)].
The commercial software GAMS/CPLEX modeling
language was adopted for the purpose of feasible solution
comparison with the proposed HGA for all problem types.
The proposed HGA was coded in Visual C++ 6.0 pro-
gramming language. Both HGA and the GAMS/ CPLEX
model were implemented on an Intel Core 2 Duo per-
sonal computer equipped with a speed of 2.4 GHz and
2GB of memory. For identifying the gaps between the
results obtained from CPLEX and HGA for optimal solu-
tion, the Lingo global solver was also used to solve prob-
lem type 1. For practical concerns, all algorithms were
terminated if the execution time exceeded 5 hours.
opyright © 2013 SciRes. IB

A Heuristic Approach for Assembly Scheduling and Transportation Problems with Parallel Machines
30
Table 1. Computational result for problem type 1.
Lingo CPLEX HGA Sol. Gap
No Global Time Sol Time max min sigma Time GCGH
1 1157 3656 1166 11.0 1158 1157 0.2 37 0.00%0.83%
2 682 758 708 9.5 685 682 0.2 34 -0.01%3.72%
3 515 613 532 6.1 516 515 0.1 36 -0.04%3.21%
4 883 283 895 6.7 889 883 0.4 37 -0.04%1.35%
5 1224 419 1231 3.6 1228 1224 0.4 33 -0.02%0.60%
6 593 292 612 17.9 595 593 0.2 37 0.00%3.06%
7 1181 291 1194 7.4 1184 1181 0.3 36 0.00%1.03%
8 809 292 815 9.7 811 809 0.1 34 0.00%0.68%
9 1169 424 1189 6.1 1171 1170 0.2 37 -0.01%1.62%
10 1258 280 1293 5.4 1263 1259 0.4 35 -0.06%2.70%
Average -0.02%1.88%
The parameters for the HGA were set as follows. The
process stopped when the maximum number of iteration
of Kmax=5NM is reached. Test case 1 in problem type 1
was run to determine the optimal combinations of popu-
lation size, maximum number of generations, the cross-
over rate, mutation rate and maximum number of itera-
tions. The population size was set to be 14; the maximum
number of iterations was set to be 2(J+K); the cloning
parameter was set at 1; the crossover rate was set as
100%; the mutation rate was set as 3%; the penalty val-
ues of each constraint were set as 100.
The criteria of performances considered were the qual-
ity of the total cost and the amount of CPU time (second).
The solution percentage gap, defined as 100 (HGA or
CPLEX solution - global solution) / (global solution)
percentage points, was used to evaluate the solution qual-
ity of the HGA or CPLEX for problem type 1. The sym-
bols of GC and GH are used to represent the solution
percentage gaps between the exact solutions obtained by
Lingo global solver and CPLEX's feasible solutions, and
between the exact solutions and the HGA's feasible solu-
tions, respectively. The exact solution approach using
Lingo global solver was only able to solve problem type
1. However, it failed to produce global solutions for
problem type 2 after 5 hours of CPU time.
For problem 1, we can see from Table 1 that HGA so-
lutions are very close to global solutions (the gaps are no
more than 0.07 percent), HGA solutions are superior to
the CPLEX solutions for all instances and the deviations
of the HGA solutions are very small (no more than 0.5).
This reflects that HGA can be considered as a stable ap-
proach for small-scale problems. In terms of running time,
we also find that HGA outperforms CPLEX.
5. Conclusions
This paper deals with the combinational problem of as-
sembly scheduling and transportation allocation under
multiple identical machines. A non-linear mixed integer
programming model was established and a hybrid genetic
heuristic approach was developed to solve this problem
in reasonable computational time. The computational
experiences show that the proposed approach is com-
prised and efficient.
6. Acknowledgements
The authors thank the anonymous referees for their helpful
comments. This research is supported by grant NSC
101-2221-E-415 -006 -MY2 (Taiwan).
REFERENCES
[1] K.P. Li, A.I. Sivakumar, M. Mathirajan and V.K. Gane-
san” Solution methodology for synchronizing assembly
manufacturing and air transportation of consumer elec-
tronics supply chain,” International Journal of Business,
Vol. 9, No. 4, 2004, pp. 361-380.
[2] K.P. Li, A.I. Sivakumar and V.K. Ganesan, “Synchro-
nized scheduling of assembly and multi-destination air
transportation in a consumer electronics supply chain,”
International Journal of Production Research, Vol. 43, No.
13, 2005, pp. 2671-2685.
[3] P.S. You, Y.C. Hsieh and H.H. Chen, “A hybrid heuristic
to a dynamic reverse logistics network with mul-
ti-commodities and components,” RAIRO-Operations
Research, Vol. 45, 2011, pp. 153-178.
[4] M. Zuo, W. Kuo and K.L. McRoberts, “Application of
mathematical programming to a large-scale agricultural
production and distribution system,” J. Operational Res.
Soc., Vol. 42. 1991, pp. 639-648.
[5] J.M. Garcia, S. Lozano and D. Canca, “Coordinated
scheduling of production and delivery from multiple
plants,” Robotics and Computer-Integrated Manufacturing,
Vol. 20, No. 3, 2004, pp. 191-198.
[6] A.M. Sarmiento and R. Nagi, “review of integrated analy-
sis of production-distribution systems,” IIE Transactions,
Vol. 31, 1999, pp. 1061-1074.
[7] D.E. Blumenfeld, L.D. Burns and C.F. Daganzo, “Syn-
chronizing production and transportation schedules,”
Transportation Research B, Vol. 25, 1991, pp. 23-27.
[8] Z.L. Chen and G.L. Vairaktarakis, “Integrated scheduling
of production and distribution operations,” Management
Science, Vol. 51, No. 4, 2005, pp. 614-628.
[9] F. Fumero and C. Vercellis, “Synchronized development
of production, inventory and distribution schedules,”
Transportation Science, Vol. 33, 1999, pp. 330-340.
[10] C.Y. Lee and Z.L. Chen, Machine scheduling with trans-
portation considerations, Journal of Scheduling, Vol. 4,
2001, pp. 3-24.
[11] K.P. Li, A.I. Sivakumar and V.K. Ganesan, “Complexities
and algorithms for synchronized scheduling of parallel
machine assembly and air transportation in consumer
electronics supply chain,” Europear Journal of Opera-
tional Research, Vol. 187, 2008, pp. 442-455.
[12] Z. Michalewicz, Genetic Algorithms + Data Structures =
Evolution Programs, 3rd Ed, Springer-Verlag, London,
UK, 1996.