# Optimal Scheduling of Material Handling Devices in a PCB Production Line: Problem Formulation and a Polynomial Algorithm

Authors: Ada Che; Chengbin Chu
Journal: Mathematical Problems in Engineering
 (2008)

---

## Abstract

Modern automated production lines usually use one or multiple computer-controlled robots or hoists for material handling between workstations. A typical application of such lines is an automated electroplating line for processing printed circuit boards (PCBs). In these systems, cyclic production policy is widely used due to large lot size and simplicity of implementation. This paper addresses cyclic scheduling of a multihoist electroplating line with constant processing times. The objective is to minimize the cycle time, or equivalently to maximize the production throughput, for a given number of hoists. We propose a mathematical model and a polynomial algorithm for this scheduling problem. Computational results on randomly generated instances are reported.


---

## Body

## 1. Introduction

Modern automated
production lines usually use one or multiple computer-controlled robots or
hoists for material handling between workstations. A
typical example is an automated
electroplating line for processing printed circuit boards (PCBs). Such a
production line usually consists of a loading station, a sequence of chemical
tanks, an unloading station, and a crew of identical programmable hoists, as
shown in Figure1. Parts to be processed enter the system from the loading
station, and then are processed successively
through tanks, and finally leave the system from the unloading station. Each tank contains chemicals required for a
specific electroplating step in the processing of parts such as acid cleaning,
acid activating, copper plating, rinsing, and so on. Each tank can process only
one part at a time. The processing time in a tank may be a given constant or allowed
to vary within a given window. Due to specific characteristics of chemical
treatment, as soon as the processing operation of a part is completed in a
tank, it must be immediately removed from that tank and transported to the next
one without any delay. Otherwise, defective parts may be produced due
to oxidization and contamination. In an
automated electroplating line, the movements of parts between the tanks are
performed by a crew of computer-controlled hoists on a single track. By
optimizing the sequence and start times of the hoist moves, we can optimize the
throughput of the line. This problem is commonly known as the hoist scheduling problem in the
literature [1–9].Figure 1
An automated multihoist electroplating
line for processing PCBs.Due to large lot size in electroplating
operations, the production is often organized in a cyclic manner, and only one
part type is processed repeatedly in the line in a production period. In such a
cyclic production system, the hoists are programed to perform a fixed sequence
of moves repeatedly. Each repetition of the sequence is called acycle. The duration of a cycle is called
the cycle time or the cycle length. Normally, one raw part enters and one finished part
leaves the line within a cycle. The throughput rate is
the inverse of the cycle time. Therefore,
minimizing the cycle time is equivalent to maximizing the throughput of a
production line.This
paper addresses cyclic scheduling of a multihoist electroplating line with
constant processing times, that is,
the processing times of a part in tanks are constants. This type of scheduling
problem arises typically from high-precision electroplating systems, in which
the quality of treatment of a part mainly depends on its processing times in
tanks. In literature, some studies (e.g., [1, 3–5, 7, 8, 10–12]) deal with the scheduling problem with time
windows, that is, the processing time of parts in each tank must fall into a
given time window. This problem is NP-hard both for the single-hoist case and
for the multihoist case. Hence, the researchers proposed heuristics or
branch-and-bound algorithms for the single-hoist or multihoist scheduling
problem with time windows. It should be noted that the polynomial algorithm
developed in this paper for the problem with constant processing times can be
served as a heuristic for the problem with time windows.For the
scheduling problem with
constant processing times, Agnetis [13]
developed polynomial algorithms for lines with two
or three tanks and a single hoist
for material handling. The same problem for any given number of tanks was shown to be solvable in polynomial
time by Levner et al. [14]. Che and Chu [6] extended Levner’s work and developed an efficient
algorithm for single-hoist electroplating lines with multifunctional and/or
duplicate tanks. As the number of
tanks increases, material handling between the tanks often becomes bottlenecks. To eliminate such bottlenecks and
increase the throughput, it is a common practice to use more than one hoist in an electroplating line with more than 10 tanks. Karzanov
and Livshits [15] appear to be the first
authors to study the cyclic multihoist scheduling problem. They studied the
system with parallel tracks (i.e., hoists travel along their respective tracks)
and proposed an O(N3)
algorithm to find the minimal number of hoists for a given cycle time, where N is the number of tanks in a production line. Kats and Levner [16] extended their results and found that the
problem of minimizing the number of hoists
for all possible cycle times can be solved in O(N5) time. Kats
and Levner [17] also developed an O(N3logN) algorithm for
the multihoist scheduling problem for a given hoist assignment.In the above studies, the researchers assumed
that the hoists travel along their respective parallel tracks and, therefore,
the collision avoidance among the hoists was not
addressed. However, almost all practical electroplating lines have only one
available track. This paper
addresses the single-track,
multihoist scheduling problem with constant processing times. When the hoists travel along a common track, the problem is
much more complicated than that with parallel tracks. With parallel tracks, it
is not required to address collision avoidance constraints among the hoists and
the problem can be reduced to either an assignment problem or a simple variant of a single-hoist problem if the hoist
assignment is given. However, for electroplating lines with a single track, we must address the collision avoidance
constraints among the
hoists either on the track or on the tanks. As will be shown in this paper, the solution of the
problem with a single track differs from that for parallel tracks. Liu and
Jiang [18] proposed
an efficient algorithm for the single-track,
two-hoist scheduling problem with
constant processing times. In this paper, we develop a mathematical
model and a corresponding polynomial algorithm for the single-track, multihoist scheduling problem with constant processing times.


## 2. Problem formulation

Consider an electroplating
line consisting of a loading stationM0,N chemical tanks, M1,M2,…,MN, and an unloading station MN+1.
The stations or tanks are arranged in a row from left to right in the following
order: M0,M1,…,MN,MN+1, as shown in Figure 2. A single type
of parts is to be processed in the line. The part flow can be described as
follows. After a part is removed from M0,
it is processed successively through tanks M1,M2,…,MN and finally leaves the system from MN+1.
Each tank can process at most one part
at a time and the processing time in Mi is a given constant ti. There are K identical hoists on a single track, which are responsible for
transporting parts between the tanks. Without loss of generality, we assume
that the hoists are numbered,
from left to right, from 0 to K−1, as shown in Figure 2. For
simplicity, the hoist movement of transporting a part from Mi to Mi+1 is called movei,0≤i≤N. Each move i consists of three simple hoist operations: (1) lift up a part from Mi; (2) transport the part to Mi+1; and (3) lower the part onto Mi+1. The
time required for the hoists to
perform move i,i=0,1,…,N, is θi, where lifting up a part from Mi,i=0,1,…,N, and lowering a part onto Mi,i=1,2,…,N+1, take vi and μi, respectively. The hoist movement without transporting any part
is called a void move. The time for the hoists to perform a void
move from Mi to Mj,i,j=0,1,…,N+1, is di,j.di,j's satisfy the triangular
inequality. Finally, let constant δ be
the allowable minimum distance among the hoists on the track in order to avoid
collision, that is, if the distance between two hoists is less than δ, then a collision happens between them. For
simplicity of notation, δ is
measured in time in the remainder, which is equal to the allowable minimum
distance divided by the travel speed of the hoists.Figure 2
Part flow through an electroplating line withN chemical tanks and K hoists.The hoists are programed to perform a fixed sequence of moves
repeatedly. The sequence of moves performed by the hoists during a cycle is
called acyclicschedule.
Our objective is to find a cyclic hoist schedule such that the cycle time T is minimized. A cyclic hoist schedule
consists of the set of moves performed by each hoist and their respective
starting times relative to the start of the cycle. To define a hoist schedule, let Yi be the starting time of move i relative to the start of a cycle, i=0,1,…,N, and ri be the
index of the hoist to perform move i (i.e., move i is performed by hoist ri), ri∈{0,1,…,K−1},i=0,1,…,N. Thus, a cyclic schedule can be uniquely defined by (T,{ri,i=0,1,…,N},{Yi,i=0,1,…,N}).Figure3 illustrates
a cyclic schedule for an electroplating line with three chemical tanks (not
including the loading station M0 and the unloading station M4) and two hoists for material handling. Three complete cycles are
illustrated in Figure 3. Without loss of generality, we assume that Y0=0, that is, move 0 happens at the start of a cycle which also implies that a part is
introduced into the system at the start of a cycle. Note that if Y0>0, we can change the origin of the time axis
such that Y0=0. From Figure 3, we see
that parts are introduced into the system at time instant 0,T,2T,…. Each hoist performs a fixed
sequence of moves cyclically. For this example, we have r0=0,r1=1,r2=0,r3=1, that is, hoist 0
performs moves 0 and 2 cyclically, while hoist 1 executes moves 1 and 3
repeatedly. From Figure 3, a cyclic schedule is uniquely defined by (T,{ri,i=0,1,…,N},{Yi,i=0,1,…,N}).Figure 3
A cyclic schedule
with three tanks and two hoists.Our objective is to
find a cyclic hoist schedule denoted by(T,{ri,i=0,1,…,N},{Yi,i=0,1,…,N}) such that the cycle
time T is minimized. A cyclic schedule (T,{ri,i=0,1,…,N},{Yi,i=0,1,…,N}) is feasible if
and only if it satisfies the following four families of constraints:(i)
processing time constraints. The parts’ processing
time inMi is exactly ti,i=1,2,…,N;(ii)
tank capacity constraints. Each tank can process at
most one part at a time;(iii)
hoist availability constraints. There is no conflict
in the use of the same hoist between any pair of moves executed by that hoist, since any hoist cannot perform two moves at the same time;(iv)
collision-free constraints. The hoists travel on a
single track and no collisions happen during a cycle.As mentioned above, at the start of each cycle, a part is
introduced into the system from the loading station. This means that the
parts are introduced into the line at time instant0,T,2T,…, as shown in Figure 3. For the sake
of simplicity, the part introduced into the system at time nT(n≥0) is
called part n. With this definition, move i of part n represents the hoist movement of transporting part n from Mi to Mi+1.
Let Zj be the completion
time of the jth processing operation
of part 0, which is also the starting time of move j of part 0. From Figure 3, Zj can be
calculated by using the following formula: (2.1)Zj=∑i=1j(θi−1+ti),j=1,2,…,N, with Z0=0.
By definition, Zj+nT is the completion time of the jth
processing operation of part n and also the starting time of
move j of part n, for any 0≤j≤N, for any n≥0. In
steady state, the starting time of move j within [0,T) (i.e., relative to the start of a cycle) is given by (2.2)Yj=ZjmodT,j=0,1,…,N. Figure 3 illustrates the above relationship
between Yj and Zj.In
the following, we formulate our problem using the notion of prohibited intervals of the cycle time,
which was first introduced by Levner et al. [14] into the cyclic scheduling of no-wait systems. Note that the part
processing time requirements are implicitly taken into account by using (2.1) and
(2.2) to compute the starting times of the moves, as soon as T is known.


### 2.1. Formulation of the
tank capacity constraints

The tank capacity constraints require that
the processing of any two successive parts on the same tank cannot be
overlapped, since each tank can process one part at a time. Furthermore, by
taking into account the times required for lifting up a part from a tank and lowering a part onto a tank, we
must have(2.3)T≥tj+μj+νj,∀1≤j≤N.
This relation
leads to (2.4)T≥β=max1≤j≤N(tj+μj+νj).


### 2.2. Formulation of the hoist availability
constraints

The hoist availability constraints require that there is no
conflict in the use of the same hoist between any pair of moves executed by that hoist. This implies
that there must be sufficient time interval between the start of any two moves performed by the same hoist, since any
hoist cannot perform two moves at the same time. This means that, for any pair of moves(j,i),j=0,…,N−1,i=j+1,…,N, if move i and move j are performed by the same hoist (i.e., ri=rj), then move i of any part must be
executed either sufficiently before or sufficiently after move j of any
part. Due to the cyclic nature of the problem, it is sufficient to consider
the hoist availability constraints for move i of part 0 and move j of part n (for any n≥1)
if move i and move j are performed by the same hoist.
Therefore, for any pair of
moves (j,i),j=0,1,…,N−1,i=j+1,…,N, such that ri=rj, move i of part 0 must be
done either sufficiently before
or sufficiently after move j of part n, for any n=1,2,….AppendixA shows
that when part n enters the
system, for any n≥n*+1, where n*=min(N+K,⌈(ZN+θN)/β⌉)−1, part 0 must have left the system. Hence, there is no more conflict in
the use of the hoist between
part 0 and part n when n≥n*+1. So, we need to
consider only those n's such that n=1,2,…,n*. In fact, n* is the
upper bound on the number of parts simultaneously processed in a production line.Figure4(a) shows the case when move i of part 0 happens after move j of part n, while Figure 4(b)
shows the case when move i of part 0 is done before move j of part n. By definition, move i of part 0 starts at Zj and ends at Zi+θi, and move j of part n starts at Zj+nT and ends at Zj+nT+θj, as shown in Figures4(a) and 4(b). It follows from Figure 4(a) that (2.5)Zi≥Zj+nT+θj+dj+1,i, where dj+1,i is the time for the hoist to
travel, upon completion of move j of
part n, from Mj+1 to Mi to perform move i of part 0. Similarly, it follows from Figure 4(b) that (2.6)Zj+nT≥Zi+θi+di+1,j, where di+1,j is the time for the hoist to
travel, upon completion of move i of
part 0, from Mi+1 to Mj to perform move j of part n.(a) Hoist availability constraint when movei succeeds move j(ri=rj). (b) Hoist availability constraint when
move i precedes move j(ri=rj).
(a)(b)To simplify the notation, definefij≡Zi−Zj+θi+di+1,j. According to (2.5) and (2.6), in any case, we must have (2.7)eithernT≤Zi−Zj−θj−dj+1,i=−fj,i,ornT≤Zi−Zj+θi+di+1,j=fi,j,∀1≤n≤n*,∀0≤j≤N−1,j+1≤i≤Nsuch  thatri=rj.Equations (2.7) are equivalent to (2.8)nT∉(−fj,i,fi,j),∀1≤n≤n*,∀0≤j≤N−1,j+1≤i≤Nsuch  thatri=rj.Example 2.1.
An electroplating line
consists of three tanks, that
is,N=3. There are two hoists available in the system, that is, K=2. The processing times are as follows: t1=16,t2=8,t3=14. For all0≤i<j≤4, the
time for a void move from Mi to Mj is obtained by using di,j=dj,i=∑k=ij−1dk,k+1 with d0,1=d3,4=4,d1,2=d2,3=2. For all0≤i≤4,μi=0.5,vi=0.5. The
times required for executing moves: θ0=θ3=6,θ1=θ2=4. We set δ = 1.
For this example, according to (2.1), we have Z0=0,Z1=22,Z2=34,Z3=52. By
definition, β=max1≤j≤N(tj+μj+vj)=17,n*=min(3+2,⌈(Z3+θ3)/β⌉)−1=3,f1,0=32,f2,0=46,f3,0=70,f2,1=20,f3,1=44,f3,2=30,f0,1=−16,f0,2=−26,f0,3=−42,f1,2=−8,f1,3=−24,f2,3=−14.


### 2.3. Formulation of the collision-free
constraints

In this
subsection, we formulate the collision-free constraints among the hoists. This is
accomplished by considering possible collisions in the execution of moves.
For any two movesi and j executed by different hoists, if their execution
requires that the hoists use a common zone of the track, then either move i must sufficiently precede move j or move j must sufficiently precede move i. Otherwise, possible collisions between the
hoists may happen, since they use a common zone of the
track at the same time. In the remainder of the paper, for any two moves i and j, without loss of generality, we assume that i>j. Three cases
should be considered.Case 1.
ri>rj and i>j+1, see Figure 5(a). In this
case, in view of the part flow shown in Figure 2, no collisions will happen
between the two hoists during their execution of moves i and j.(a) No collisions in the execution of two moves(ri>rj,i>j+1). (b) Execution of two moves requires using a boundary tank Mi(ri>rj,i=j+1). (c) Execution of two moves requires using an overlapping zone
of the track from Mj to Mi+1(ri<rj,i>j).
(a)(b)(c)Case 2.
ri>rj and i=j+1, see Figure 5(b). In this
case, hoist rj and hoist ri may collide at Mi, onto which a part is
lowered by hoist rj and from which another part is lifted
up by hoist ri.Case 3.
ri<rj, see Figure 5(c). In this case, hoists ri and rj will use an overlapping zone of the track
from Mj to Mi+1 in order to execute moves i and j,
and collisions may happen between them when passing through this overlapping
zone.From this
analysis, when there are multiple hoists on a single track, collisions may
happen among hoists not only when they use an overlapping zone of the track,
but also when using the same tank, from which a part is lifted up by one hoist
and onto which another part is lower down by another hoist. Such a tank is
called aboundary tank in this paper.
In the following, we will first address Case 3 and then consider Case 2.


#### 2.3.1. Execution of two moves requires using an
overlapping zone of the track

By Case3 (see Figure 5(c), hoists ri and rj will use an
overlapping zone of the track from Mj to Mi+1 in order to execute moves i and j,
and collisions may happen between them. In order to avoid collision between
hoists ri and rj such that ri<rj, they cannot use this overlapping zone at
the same time. There must be sufficient time interval between them in using this
overlapping zone. This means that, for any pair of moves (j,i),j=0,1,…,N−1,i=j+1,…,N, such that ri<rj, move i of part 0 must be done either sufficiently
before or sufficiently after
move j of part n, for any n=1,2,…,n*.Figure6(a) shows the
case when move i of part 0 is done after move j of part n, that is, Zi>Zj+nT. In order to
avoid collision, after hoist rj finishes move j of part n, it should arrive at Mi before hoist ri and should move to
a higher position than Mi (i.e., move
to a position nearer to the unloading station than Mi), as shown in Figure 6(a). Note that the earliest
time at which hoist rj arrives at Mi is Zj+nT+θj+dj+1,i, and the
latest time at which hoist ri arrives at Mi is Zi, and the allowable minimum distance among the
hoists is δ. Hence, as shown in Figure 6(a), the
following constraint must be satisfied: (2.9)Zi≥Zj+nT+θj+dj+1,i+(rj−ri)δ. Similarly, as shown in Figure 6(b), if move i of part 0 is done
before move j of part n, that is, Zi<Zj+nT, we must have (2.10)Zj+nT≥Zi+θi+di+1,j+(rj−ri)δ. From (2.9) and (2.10), we
have (2.11)eithernT≤Zi−Zj−θj−dj+1,i−(rj−ri)δ=−fj,i−(rj−ri)δ,ornT≥Zi−Zj+θi+di+1,j+(rj−ri)δ=fi,j+(rj−ri)δ,∀1≤n≤n*,∀0≤j≤N−1,j+1≤i≤Nsuch  thatri<rj. The constraints (2.11) can be equivalently written as (2.12)nT∉(−fj,i−(rj−ri)δ,fi,j+(rj−ri)δ),∀1≤n≤n*,∀0≤j≤N−1,j+1≤i≤Nsuch  thatri<rj.(a) Collision-free constraint
when movei succeeds move j(ri<rj). (b) Collision-free constraint when move i precedes move j(ri<rj).
(a)(b)


#### 2.3.2. Execution of two moves requires using a boundary
tank

By
Case2 (see Figure 5(b)), hoists rj and ri may collide at Mi, onto which a part is lowered
by hoist rj and
from which another part is lifted up by
hoist ri. In order to avoid
collision, part m (for any m≥0) must have been lifted up from Mi, for any 1≤i≤N, when part m+1 arrives at Mi.
Note that part m will leave Mi at time Zi+mT+νi, and part m+1 will arrive at Mi at time Zi−1+(m+1)T+θi−1−μi. knowing that the allowable minimum distance among
the hoists is δ, in order to avoid collision between hoists rj and ri, we must
have (2.13)Zi−1+(m+1)T+θi−1−μi≥Zi+mT+νi+(ri−ri−1)δ,∀1≤i≤Nsuch  thatri−1<ri. This relation leads to (2.14)T≥ti+μi+νi+(ri−ri−1)δ,∀1≤i≤Nsuch  thatri−1<ri. This
relation can be equivalently written as (2.15)T∉(−∞,ti+μi+νi+(ri−ri−1)δ),∀1≤i≤Nsuch  thatri−1<ri,From the above formulation of the problem, we see that the collision-free
constraints can be formulated as (2.12) and ((2.15)). It should be emphasized that
this formulation of the collision-free constraints is complete, since by Cases
1, 2, and 3 (or Figures5(a), 5(b), and 5(c)) possible combinations of ri and rj are all taken into account for any pair of
moves (j,i),j=0,1,…,N−1,i=j+1,…,N. Note that (2.8) and (2.12) can be generalized as (2.16)nT∉(−fj,i−(rj−ri)δ,fi,j+(rj−ri)δ),∀1≤n≤n*,∀0≤j≤N−1,j+1≤i≤Nsuch  thatri≤rj.According
to (2.4), (2.15)), and (2.16), the multihoist
electroplating line scheduling problem considered in this paper can be
formulated as the following prohibited intervals for the cycle time T: (2.17)MinimizeT, subject to (2.4), (2.15)), and (2.16).Note that (2.4), (2.15)), and
(2.16) can be equivalently
written as (2.18)T∉Q(R)≡(−∞,β)∪{⋃1≤i≤Nri−1<ri(−∞,ti+μi+νi+(ri−ri−1)δ)}∪{⋃0≤j≤N⋃j+1≤i≤Nri≤rj{(−fj,i−(rj−ri)δ,fi,j+(rj−ri)δ)∪(−fj,i−(rj−ri)δ2,fi,j+(rj−ri)δ2)∪⋯∪(−fj,i−(rj−ri)δn*,fi,j+(rj−ri)δn*)}}, where vector R=(r0,r1,…,rN).R is called the hoist
assignment in the remainder. It can be found from (2.18) that Q(R) is a union of R-parameterized
open prohibited intervals for the
cycle time T. For a given R,Q(R) is a union of open prohibited
intervals for the cycle time T.In this Section, we formulate our problem as a series of prohibited
intervals for the cycle time, that is,Q(R). Each family of the problem constraints (i.e., tank capacity
constraints, hoist availability constraints, and collision-free constraints) corresponds to a set of
prohibited intervals for T, for example,
the hoist availability constraint between a pair of moves (j,i) such that ri=rj corresponds to a set of prohibited
intervals nT∉(−fj,i,fi,j), for n=1,2,…,n*. Due to this property, for a given hoist assignment R, if T∉Q(R), then such a T must be feasible, since, by definition, such a T falls into no prohibited intervals in Q(R), and consequently all problem constraints
must be satisfied.


## 2.1. Formulation of the
tank capacity constraints

The tank capacity constraints require that
the processing of any two successive parts on the same tank cannot be
overlapped, since each tank can process one part at a time. Furthermore, by
taking into account the times required for lifting up a part from a tank and lowering a part onto a tank, we
must have(2.3)T≥tj+μj+νj,∀1≤j≤N.
This relation
leads to (2.4)T≥β=max1≤j≤N(tj+μj+νj).


## 2.2. Formulation of the hoist availability
constraints

The hoist availability constraints require that there is no
conflict in the use of the same hoist between any pair of moves executed by that hoist. This implies
that there must be sufficient time interval between the start of any two moves performed by the same hoist, since any
hoist cannot perform two moves at the same time. This means that, for any pair of moves(j,i),j=0,…,N−1,i=j+1,…,N, if move i and move j are performed by the same hoist (i.e., ri=rj), then move i of any part must be
executed either sufficiently before or sufficiently after move j of any
part. Due to the cyclic nature of the problem, it is sufficient to consider
the hoist availability constraints for move i of part 0 and move j of part n (for any n≥1)
if move i and move j are performed by the same hoist.
Therefore, for any pair of
moves (j,i),j=0,1,…,N−1,i=j+1,…,N, such that ri=rj, move i of part 0 must be
done either sufficiently before
or sufficiently after move j of part n, for any n=1,2,….AppendixA shows
that when part n enters the
system, for any n≥n*+1, where n*=min(N+K,⌈(ZN+θN)/β⌉)−1, part 0 must have left the system. Hence, there is no more conflict in
the use of the hoist between
part 0 and part n when n≥n*+1. So, we need to
consider only those n's such that n=1,2,…,n*. In fact, n* is the
upper bound on the number of parts simultaneously processed in a production line.Figure4(a) shows the case when move i of part 0 happens after move j of part n, while Figure 4(b)
shows the case when move i of part 0 is done before move j of part n. By definition, move i of part 0 starts at Zj and ends at Zi+θi, and move j of part n starts at Zj+nT and ends at Zj+nT+θj, as shown in Figures4(a) and 4(b). It follows from Figure 4(a) that (2.5)Zi≥Zj+nT+θj+dj+1,i, where dj+1,i is the time for the hoist to
travel, upon completion of move j of
part n, from Mj+1 to Mi to perform move i of part 0. Similarly, it follows from Figure 4(b) that (2.6)Zj+nT≥Zi+θi+di+1,j, where di+1,j is the time for the hoist to
travel, upon completion of move i of
part 0, from Mi+1 to Mj to perform move j of part n.(a) Hoist availability constraint when movei succeeds move j(ri=rj). (b) Hoist availability constraint when
move i precedes move j(ri=rj).
(a)(b)To simplify the notation, definefij≡Zi−Zj+θi+di+1,j. According to (2.5) and (2.6), in any case, we must have (2.7)eithernT≤Zi−Zj−θj−dj+1,i=−fj,i,ornT≤Zi−Zj+θi+di+1,j=fi,j,∀1≤n≤n*,∀0≤j≤N−1,j+1≤i≤Nsuch  thatri=rj.Equations (2.7) are equivalent to (2.8)nT∉(−fj,i,fi,j),∀1≤n≤n*,∀0≤j≤N−1,j+1≤i≤Nsuch  thatri=rj.Example 2.1.
An electroplating line
consists of three tanks, that
is,N=3. There are two hoists available in the system, that is, K=2. The processing times are as follows: t1=16,t2=8,t3=14. For all0≤i<j≤4, the
time for a void move from Mi to Mj is obtained by using di,j=dj,i=∑k=ij−1dk,k+1 with d0,1=d3,4=4,d1,2=d2,3=2. For all0≤i≤4,μi=0.5,vi=0.5. The
times required for executing moves: θ0=θ3=6,θ1=θ2=4. We set δ = 1.
For this example, according to (2.1), we have Z0=0,Z1=22,Z2=34,Z3=52. By
definition, β=max1≤j≤N(tj+μj+vj)=17,n*=min(3+2,⌈(Z3+θ3)/β⌉)−1=3,f1,0=32,f2,0=46,f3,0=70,f2,1=20,f3,1=44,f3,2=30,f0,1=−16,f0,2=−26,f0,3=−42,f1,2=−8,f1,3=−24,f2,3=−14.


## 2.3. Formulation of the collision-free
constraints

In this
subsection, we formulate the collision-free constraints among the hoists. This is
accomplished by considering possible collisions in the execution of moves.
For any two movesi and j executed by different hoists, if their execution
requires that the hoists use a common zone of the track, then either move i must sufficiently precede move j or move j must sufficiently precede move i. Otherwise, possible collisions between the
hoists may happen, since they use a common zone of the
track at the same time. In the remainder of the paper, for any two moves i and j, without loss of generality, we assume that i>j. Three cases
should be considered.Case 1.
ri>rj and i>j+1, see Figure 5(a). In this
case, in view of the part flow shown in Figure 2, no collisions will happen
between the two hoists during their execution of moves i and j.(a) No collisions in the execution of two moves(ri>rj,i>j+1). (b) Execution of two moves requires using a boundary tank Mi(ri>rj,i=j+1). (c) Execution of two moves requires using an overlapping zone
of the track from Mj to Mi+1(ri<rj,i>j).
(a)(b)(c)Case 2.
ri>rj and i=j+1, see Figure 5(b). In this
case, hoist rj and hoist ri may collide at Mi, onto which a part is
lowered by hoist rj and from which another part is lifted
up by hoist ri.Case 3.
ri<rj, see Figure 5(c). In this case, hoists ri and rj will use an overlapping zone of the track
from Mj to Mi+1 in order to execute moves i and j,
and collisions may happen between them when passing through this overlapping
zone.From this
analysis, when there are multiple hoists on a single track, collisions may
happen among hoists not only when they use an overlapping zone of the track,
but also when using the same tank, from which a part is lifted up by one hoist
and onto which another part is lower down by another hoist. Such a tank is
called aboundary tank in this paper.
In the following, we will first address Case 3 and then consider Case 2.


### 2.3.1. Execution of two moves requires using an
overlapping zone of the track

By Case3 (see Figure 5(c), hoists ri and rj will use an
overlapping zone of the track from Mj to Mi+1 in order to execute moves i and j,
and collisions may happen between them. In order to avoid collision between
hoists ri and rj such that ri<rj, they cannot use this overlapping zone at
the same time. There must be sufficient time interval between them in using this
overlapping zone. This means that, for any pair of moves (j,i),j=0,1,…,N−1,i=j+1,…,N, such that ri<rj, move i of part 0 must be done either sufficiently
before or sufficiently after
move j of part n, for any n=1,2,…,n*.Figure6(a) shows the
case when move i of part 0 is done after move j of part n, that is, Zi>Zj+nT. In order to
avoid collision, after hoist rj finishes move j of part n, it should arrive at Mi before hoist ri and should move to
a higher position than Mi (i.e., move
to a position nearer to the unloading station than Mi), as shown in Figure 6(a). Note that the earliest
time at which hoist rj arrives at Mi is Zj+nT+θj+dj+1,i, and the
latest time at which hoist ri arrives at Mi is Zi, and the allowable minimum distance among the
hoists is δ. Hence, as shown in Figure 6(a), the
following constraint must be satisfied: (2.9)Zi≥Zj+nT+θj+dj+1,i+(rj−ri)δ. Similarly, as shown in Figure 6(b), if move i of part 0 is done
before move j of part n, that is, Zi<Zj+nT, we must have (2.10)Zj+nT≥Zi+θi+di+1,j+(rj−ri)δ. From (2.9) and (2.10), we
have (2.11)eithernT≤Zi−Zj−θj−dj+1,i−(rj−ri)δ=−fj,i−(rj−ri)δ,ornT≥Zi−Zj+θi+di+1,j+(rj−ri)δ=fi,j+(rj−ri)δ,∀1≤n≤n*,∀0≤j≤N−1,j+1≤i≤Nsuch  thatri<rj. The constraints (2.11) can be equivalently written as (2.12)nT∉(−fj,i−(rj−ri)δ,fi,j+(rj−ri)δ),∀1≤n≤n*,∀0≤j≤N−1,j+1≤i≤Nsuch  thatri<rj.(a) Collision-free constraint
when movei succeeds move j(ri<rj). (b) Collision-free constraint when move i precedes move j(ri<rj).
(a)(b)


### 2.3.2. Execution of two moves requires using a boundary
tank

By
Case2 (see Figure 5(b)), hoists rj and ri may collide at Mi, onto which a part is lowered
by hoist rj and
from which another part is lifted up by
hoist ri. In order to avoid
collision, part m (for any m≥0) must have been lifted up from Mi, for any 1≤i≤N, when part m+1 arrives at Mi.
Note that part m will leave Mi at time Zi+mT+νi, and part m+1 will arrive at Mi at time Zi−1+(m+1)T+θi−1−μi. knowing that the allowable minimum distance among
the hoists is δ, in order to avoid collision between hoists rj and ri, we must
have (2.13)Zi−1+(m+1)T+θi−1−μi≥Zi+mT+νi+(ri−ri−1)δ,∀1≤i≤Nsuch  thatri−1<ri. This relation leads to (2.14)T≥ti+μi+νi+(ri−ri−1)δ,∀1≤i≤Nsuch  thatri−1<ri. This
relation can be equivalently written as (2.15)T∉(−∞,ti+μi+νi+(ri−ri−1)δ),∀1≤i≤Nsuch  thatri−1<ri,From the above formulation of the problem, we see that the collision-free
constraints can be formulated as (2.12) and ((2.15)). It should be emphasized that
this formulation of the collision-free constraints is complete, since by Cases
1, 2, and 3 (or Figures5(a), 5(b), and 5(c)) possible combinations of ri and rj are all taken into account for any pair of
moves (j,i),j=0,1,…,N−1,i=j+1,…,N. Note that (2.8) and (2.12) can be generalized as (2.16)nT∉(−fj,i−(rj−ri)δ,fi,j+(rj−ri)δ),∀1≤n≤n*,∀0≤j≤N−1,j+1≤i≤Nsuch  thatri≤rj.According
to (2.4), (2.15)), and (2.16), the multihoist
electroplating line scheduling problem considered in this paper can be
formulated as the following prohibited intervals for the cycle time T: (2.17)MinimizeT, subject to (2.4), (2.15)), and (2.16).Note that (2.4), (2.15)), and
(2.16) can be equivalently
written as (2.18)T∉Q(R)≡(−∞,β)∪{⋃1≤i≤Nri−1<ri(−∞,ti+μi+νi+(ri−ri−1)δ)}∪{⋃0≤j≤N⋃j+1≤i≤Nri≤rj{(−fj,i−(rj−ri)δ,fi,j+(rj−ri)δ)∪(−fj,i−(rj−ri)δ2,fi,j+(rj−ri)δ2)∪⋯∪(−fj,i−(rj−ri)δn*,fi,j+(rj−ri)δn*)}}, where vector R=(r0,r1,…,rN).R is called the hoist
assignment in the remainder. It can be found from (2.18) that Q(R) is a union of R-parameterized
open prohibited intervals for the
cycle time T. For a given R,Q(R) is a union of open prohibited
intervals for the cycle time T.In this Section, we formulate our problem as a series of prohibited
intervals for the cycle time, that is,Q(R). Each family of the problem constraints (i.e., tank capacity
constraints, hoist availability constraints, and collision-free constraints) corresponds to a set of
prohibited intervals for T, for example,
the hoist availability constraint between a pair of moves (j,i) such that ri=rj corresponds to a set of prohibited
intervals nT∉(−fj,i,fi,j), for n=1,2,…,n*. Due to this property, for a given hoist assignment R, if T∉Q(R), then such a T must be feasible, since, by definition, such a T falls into no prohibited intervals in Q(R), and consequently all problem constraints
must be satisfied.


## 2.3.1. Execution of two moves requires using an
overlapping zone of the track

By Case3 (see Figure 5(c), hoists ri and rj will use an
overlapping zone of the track from Mj to Mi+1 in order to execute moves i and j,
and collisions may happen between them. In order to avoid collision between
hoists ri and rj such that ri<rj, they cannot use this overlapping zone at
the same time. There must be sufficient time interval between them in using this
overlapping zone. This means that, for any pair of moves (j,i),j=0,1,…,N−1,i=j+1,…,N, such that ri<rj, move i of part 0 must be done either sufficiently
before or sufficiently after
move j of part n, for any n=1,2,…,n*.Figure6(a) shows the
case when move i of part 0 is done after move j of part n, that is, Zi>Zj+nT. In order to
avoid collision, after hoist rj finishes move j of part n, it should arrive at Mi before hoist ri and should move to
a higher position than Mi (i.e., move
to a position nearer to the unloading station than Mi), as shown in Figure 6(a). Note that the earliest
time at which hoist rj arrives at Mi is Zj+nT+θj+dj+1,i, and the
latest time at which hoist ri arrives at Mi is Zi, and the allowable minimum distance among the
hoists is δ. Hence, as shown in Figure 6(a), the
following constraint must be satisfied: (2.9)Zi≥Zj+nT+θj+dj+1,i+(rj−ri)δ. Similarly, as shown in Figure 6(b), if move i of part 0 is done
before move j of part n, that is, Zi<Zj+nT, we must have (2.10)Zj+nT≥Zi+θi+di+1,j+(rj−ri)δ. From (2.9) and (2.10), we
have (2.11)eithernT≤Zi−Zj−θj−dj+1,i−(rj−ri)δ=−fj,i−(rj−ri)δ,ornT≥Zi−Zj+θi+di+1,j+(rj−ri)δ=fi,j+(rj−ri)δ,∀1≤n≤n*,∀0≤j≤N−1,j+1≤i≤Nsuch  thatri<rj. The constraints (2.11) can be equivalently written as (2.12)nT∉(−fj,i−(rj−ri)δ,fi,j+(rj−ri)δ),∀1≤n≤n*,∀0≤j≤N−1,j+1≤i≤Nsuch  thatri<rj.(a) Collision-free constraint
when movei succeeds move j(ri<rj). (b) Collision-free constraint when move i precedes move j(ri<rj).
(a)(b)


## 2.3.2. Execution of two moves requires using a boundary
tank

By
Case2 (see Figure 5(b)), hoists rj and ri may collide at Mi, onto which a part is lowered
by hoist rj and
from which another part is lifted up by
hoist ri. In order to avoid
collision, part m (for any m≥0) must have been lifted up from Mi, for any 1≤i≤N, when part m+1 arrives at Mi.
Note that part m will leave Mi at time Zi+mT+νi, and part m+1 will arrive at Mi at time Zi−1+(m+1)T+θi−1−μi. knowing that the allowable minimum distance among
the hoists is δ, in order to avoid collision between hoists rj and ri, we must
have (2.13)Zi−1+(m+1)T+θi−1−μi≥Zi+mT+νi+(ri−ri−1)δ,∀1≤i≤Nsuch  thatri−1<ri. This relation leads to (2.14)T≥ti+μi+νi+(ri−ri−1)δ,∀1≤i≤Nsuch  thatri−1<ri. This
relation can be equivalently written as (2.15)T∉(−∞,ti+μi+νi+(ri−ri−1)δ),∀1≤i≤Nsuch  thatri−1<ri,From the above formulation of the problem, we see that the collision-free
constraints can be formulated as (2.12) and ((2.15)). It should be emphasized that
this formulation of the collision-free constraints is complete, since by Cases
1, 2, and 3 (or Figures5(a), 5(b), and 5(c)) possible combinations of ri and rj are all taken into account for any pair of
moves (j,i),j=0,1,…,N−1,i=j+1,…,N. Note that (2.8) and (2.12) can be generalized as (2.16)nT∉(−fj,i−(rj−ri)δ,fi,j+(rj−ri)δ),∀1≤n≤n*,∀0≤j≤N−1,j+1≤i≤Nsuch  thatri≤rj.According
to (2.4), (2.15)), and (2.16), the multihoist
electroplating line scheduling problem considered in this paper can be
formulated as the following prohibited intervals for the cycle time T: (2.17)MinimizeT, subject to (2.4), (2.15)), and (2.16).Note that (2.4), (2.15)), and
(2.16) can be equivalently
written as (2.18)T∉Q(R)≡(−∞,β)∪{⋃1≤i≤Nri−1<ri(−∞,ti+μi+νi+(ri−ri−1)δ)}∪{⋃0≤j≤N⋃j+1≤i≤Nri≤rj{(−fj,i−(rj−ri)δ,fi,j+(rj−ri)δ)∪(−fj,i−(rj−ri)δ2,fi,j+(rj−ri)δ2)∪⋯∪(−fj,i−(rj−ri)δn*,fi,j+(rj−ri)δn*)}}, where vector R=(r0,r1,…,rN).R is called the hoist
assignment in the remainder. It can be found from (2.18) that Q(R) is a union of R-parameterized
open prohibited intervals for the
cycle time T. For a given R,Q(R) is a union of open prohibited
intervals for the cycle time T.In this Section, we formulate our problem as a series of prohibited
intervals for the cycle time, that is,Q(R). Each family of the problem constraints (i.e., tank capacity
constraints, hoist availability constraints, and collision-free constraints) corresponds to a set of
prohibited intervals for T, for example,
the hoist availability constraint between a pair of moves (j,i) such that ri=rj corresponds to a set of prohibited
intervals nT∉(−fj,i,fi,j), for n=1,2,…,n*. Due to this property, for a given hoist assignment R, if T∉Q(R), then such a T must be feasible, since, by definition, such a T falls into no prohibited intervals in Q(R), and consequently all problem constraints
must be satisfied.


## 3. Problem analysis

In this Section, we perform a property analysis for the mathematical
model we developed in the above Section. Based on this analysis, we will show that the optimal cycle time for the problem is necessarily one of
special values of the cycle time. Hence, the optimal cycle time can be
found by detecting the feasibility for each one of these special values of the cycle time, and our problem is thus reduced to a
feasibility checking problem for a given value ofT.Theorem 3.1.
Given a hoist assignmentR, the optimal cycle time T*(R)∈A(R), where (3.1)A(R)≡{β}∪{x∣x=ti+μi+νi+(ri−ri−1)δ,x>β,1≤i≤N,ri−1<ri}∪{y∣y=fi,j+(rj−ri)δn,y>β,1≤n≤n*,0≤j≤N−1,j+1≤i≤N,ri≤rj}.Proof.
Given a hoist assignmentR,Q(R) is a union of open prohibited intervals which are not
necessarily disjoint. However, Q(R) can be considered as a union of disjoint prohibited intervals after merging of the intersecting
ones. Therefore, Q(R) can be rewritten
as (3.2)Q(R)=(a1,b1)∪(a2,b2)∪⋯∪(aH,bH) with −∞=a1<b1≤a2<⋯<bi−1≤ai<bi≤ai+1<⋯<bH.Example 1 (continued)
IfR=(r0,r1,r2,r3)=(0,1,0,1), that is, move 0 and move 2 are performed by hoist 0 while move 1 and move 3 are
executed by hoist 1, according to (2.18), the following relation holds (3.3)T∉Q(R)=(−∞,β)∪{(−∞,t1+μ1+ν1+δ)∪(−∞,t3+μ3+ν3+δ)}∪{(−f0,2,f2,0)∪(−f0,22,f2,02)∪(−f0,23,f2,03)}∪{(−f1,2−δ,f2,1+δ)∪(−f1,2−δ2,f2,1+δ2)∪(−f1,2−δ3,f2,1+δ3)}∪{(−f1,3,f3,1)∪(−f1,32,f3,12)∪(−f1,33,f3,13)}=(−∞,17)∪{(−∞,18)∪(−∞,16)}∪{(26,46)∪(13,23)∪(8.66,15.33)}∪{(7,21)∪(3.5,10.5)∪(2.33,7)}∪{(24,44)∪(12,22)∪(8,14.66)}. After merging of the intersecting prohibited intervals in Q(R), we have T∉Q(R)=(−∞,23)∪(24,46). Hence,
a1=−∞,b1=23,a2=24,b2=46.We can easily find that the optimal cycle timeT*(R) is
necessarily the upper bound of the
first open prohibited interval, that is, b1, since b1 is the smallest cycle time that is not prohibited by Q(R). Note that the upper bound of any disjoint prohibited interval, after merging of the intersecting
intervals, is necessarily an upper bound of one of the prohibited intervals
before merging of the intersecting intervals. This means that b1 is necessarily one of the upper bounds of the prohibited intervals before
merging of the intersecting ones. Therefore,
it follows from (2.18)
that b1∈A(R). Thus, we have Theorem 3.1.Corollary 3.2.
Forany hoist
assignment R, A(R)⊂AT always holds where (3.4)AT≡{β}∪{x^∣x^=ti+μi+νi+kδ,x^>β,1≤i≤N,1≤k≤K−1}∪{y^∣y^=fi,j+kδn,y^>β,0≤j≤N−1,j+1≤i≤N,0≤k≤K−1,1≤n≤n*}.The correctness of Corollary3.2 is straightforward, since we have (ri−ri−1)∈{1,2,…,K−1} for any 1≤i≤N such that ri−1<ri, and (rj−ri)∈{0,1,…,K−1} for any 0≤j≤N−1,j+1≤i≤N such that ri≤rj.By Theorem3.1 and Corollary 3.2, we have the following corollary.Corollary 3.3.
The optimal
cycle timeT* for the
problem T*∈AT.By Corollary3.3, the
optimal cycle time T* can
be found by detecting the feasibility for each value of the cycle time in AT in increasing order until the first feasible cycle time is
found, which is the optimal cycle time for the problem. Our problem is thus reduced
to the feasibility checking problem for a given value of T.Example 1 (continued)
The setAT = {17,
18, 21, 22, 22.5, 23, 23.5, 30,
31, 32, 33, 35, 35.5, 44, 45, 46, 47, 70, 71}. Th optimal cycle time for the
problem can be found by checking the feasibility of these values of the cycle time in
increasing order.


## 4. Feasibility checking for a given value ofT

As mentioned in Section2, for a given hoist
assignment R, if T∉Q(R), then such a T must be feasible. Hence, given a value of T, say T0,T0 must
be feasible if there exists a hoist assignment R such that T0∉Q(R). Such an R is
accordingly called a feasible hoist assignment for T0.
Thus, to check feasibility for T0, we only need to check whether there exists a feasible hoist assignment R for T0. If so, then T0 is feasible. Our basic idea is to
first derive sufficient and necessary constraints that R must satisfy in
order that T0∉Q(R). By solving the derived
constraints for R, we then detect the feasibility for T0 and obtain a feasible hoist assignment R if T0 is feasible.Theorem 4.1.
For a given cycle timeT0, in order that T0∉Q(R), a sufficient and necessary condition is that R satisfies the
following constraints: (4.1)ri−ri−1≤k−1,ifT0∈(−∞,ti+μi+νi+kδ),∀1≤k≤K−1,∀1≤i≤N,(4.2)rj−ri≤k−1,if(si,jk−1)T0∈(−fj,i−kδ,fi,j+kδ),∀0≤j≤N−1,j+1≤i≤N,0≤k≤K−1,(4.3)ri−r0≥0,∀1≤i≤N,(4.4)ri−r0≤K−1,∀1≤i≤N, where si,jk=⌈(fi,j+kδ)/T0⌉, where ⌈x⌉ is the smallest integer greater than or equal
to x.Proof.
Note thatT0∉Q(R) is equivalent to (2.4), (2.15), and (2.16) hold for T0. Constraint
(2.4)) means that if T0<β, then T0 must be infeasible and no further feasibility checking is needed. Hence, in the
remainder, without loss of generality, we assume that T0≥β. With this assumption, (2.4)) is always satisfied. In the following,
we will first derive the sufficient and necessary constraints
that R must satisfy in order that ((2.15)) holds for T0(Part A), and then we will derive the sufficient and necessary constraints
that R must satisfy in order that (2.16) holds for T0(Part B).Part A.
The sufficiency and necessity of (4.1) in order that ((2.15)) holds for T0.We
first derive the necessary constraints
thatR must satisfy in order that ((2.15)) holds for T0. Since 1≤ri−ri−1≤K−1 for
any 1≤i≤N such that ri−1<ri, in order that ((2.15)) holds for T0, the following relation must hold  (4.5)ri−ri−1<k,ifT0∈(−∞,ti+μi+νi+kδ),∀1≤k≤K−1,∀1≤j≤N. The correctness of (4.5) is clear, since if (4.5) was not satisfied, then we have T0∈(−∞,ti+μi+νi+kδ) and ri−ri−1≥k, for some 1≤k≤K−1 and 1≤i≤N, and consequently ((2.15))
will be violated for T0. Since ri takes only
integer, (4.5) is
equivalent to (4.1). Hence, in
order that ((2.15)) holds for T0,R must satisfy (4.1).We now prove the
sufficiency of (4.1) in order that ((2.15)) holds for T0. Assume that ((2.15)) does NOT hold for T0 when
(4.1) holds. We
will show that this assumption will lead to contradictory facts and thus is
incorrect. By assumption, since ((2.15))
does NOT hold for T0, there must exists an i such that ri−1<ri and T0∈(−∞,ti+μi+νi+(ri−ri−1)δ). By lettingm=ri−ri−1, we have T0∈(−∞,ti+μi+νi+mδ) for
this specified i. Since, by
assumption, (4.1) holds and T0∈(−∞,ti+μi+νi+mδ), according to (4.1), we must have ri−ri−1≤m−1. This is in
contradiction with the fact that m=ri−ri−1. This means that the assumption that ((2.15)) does NOT hold
for T0 when (4.1) holds is incorrect. We, thus, prove the
sufficiency of (4.1) in order that ((2.15)) holds for T0.Part B.
The
sufficiency and necessity of (4.2) in order that (2.16) holds for T0.We first derive the necessary constraints thatR must satisfy in order
that (2.16) holds for T0. Since 0≤rj−ri≤K−1, for
any 0≤j≤N−1,j+1≤i≤N such that ri≤rj, in order that (2.16)
holds for T0, the following relation must hold (4.6)rj−ri<k,if  there  exists  ann,1≤n≤n*such  thatnT0∈(−fj,i−kδ,fi,j+kδ)∀0≤j≤N−1,j+1≤i≤N,0≤k≤K−1.The correctness
of (4.6) is clear, since if (4.6) was not satisfied, then we have nT0∈(−fj,i−kδ,fi,j+kδ) and rj−ri≥k, for some 1≤n≤n*,0≤k≤K−1,0≤j≤N−1,j+1≤i≤N, and consequently (2.16)
will be violated for T0. As shown in Appendix B, checking whether there exists an n,1≤n≤n* such that nT0∈(−fj,i−kδ,fi,j+kδ),for  all0≤j≤N−1,j+1≤i≤N,0≤k≤K−1 is
equivalent to checking whether (si,jk−1)T0∈(−fj,i−kδ,fi,j+kδ), where si,jk=⌈(fi,j+kδ)/T0⌉. As a result, (4.6) can be equivalently expressed as (4.7)rj−ri<k,if(si,jk−1)T0∈(−fj,i−kδ,fi,j+kδ),∀0≤j≤N−1,j+1≤i≤N,0≤k≤K−1. Since rj and ri take only
integers, (4.7) is
equivalent to (4.2). Hence, in
order that (2.16) holds for T0,R must satisfy (4.2).We now prove the
sufficiency of (4.2) in order that (2.16) holds for T0. Similarly, assume that (2.16) does NOT hold for T0 when (4.2) holds. We
will also show that this assumption will lead to contradictory facts and thus
is incorrect. By assumption, since (2.16) does NOT hold
for T0, we must have nT0∈(−fj,i−(rj−ri)δ,fi,j+(rj−ri)δ) for some 1≤n≤n*,0≤j≤N−1,j+1≤i≤N, such that ri≤rj. By lettingm=rj−ri, we have nT0∈(−fj,i−mδ,fi,j+mδ) for the specified n,i,and j. Since, by assumption, (4.2) holds and nT0∈(−fj,i−mδ,fi,j+mδ) for the
specified n,i,and j, according to (4.2), we must have rj−ri≤m−1. This is in
contradiction with the fact that m=rj−ri. This means that the assumption that (2.16) does NOT hold for T0 when (4.2) holds is incorrect.
We, thus, prove the sufficiency of (4.2) in order that (2.16) holds for T0.Since there areK hoists in the production line, we must
have (4.8)0≤ri≤K−1,∀0≤i≤N. With the line configuration in Figure 2, it is easy to find that move 0
must be performed by hoist 0 in order to avoid collision among the hoists. Thus, without loss of generality, we
assume that r0=0. With this assumption, constraints (4.8) can be equivalently written
as (4.3) and (4.4).To sum up, in
order thatT0∉Q(R), a sufficient and necessary condition is that R satisfies the
constraints (4.1)–(4.4).Example 1 (continued)
We illustrate the
feasibility checking forT0=23.
According to (4.1)–(4.4), in order that T0∉Q(R), a sufficient and necessary condition is that R satisfies the
following constraints:(4.9)r0−r1≤−1,(4.10)r0−r2≤0,(4.11)r0−r3≤−1,(4.12)r2−r3≤−1,(4.13)ri−r0≤1,∀1≤i≤3.
We illustrate
how to derive (4.12). By
definition, we derive s3,20=2,s3,21=2. Hence, (s3,20−1)T0=23∈(−f2,3,f3,2)=(14,30);(s3,21−1)T0=23∈(−f2,3−δ,f3,2+δ)=(13,31). This leads to r2−r3≤−1 and r2−r3≤0 according to (4.2). The latter relation is redundant. We, thus, derive (4.12). The
other constraints can be derived
in a similar way. Note that the
constraints ri−r0≥0, for all1≤i≤3, are
redundant with the consideration of (4.9)–(4.11) and thus were not
shown here.
By Theorem4.1, (4.1)–(4.4) are the sufficient
and necessary constraints that R must satisfy in order that T0∉Q(R). Note that each constraint in (4.1)–(4.4) can be equivalently written in the form of rj−ri≥cij, where cij is an integer, 0≤i,j≤N. Due to this special structure, solving (4.1)–(4.4) can be transformed into a longest-path problem in a directed
graph, as will be described in detail.
In
a directed graph G(V,E), where V and E are, respectively, the set of
vertices and the set of arcs, a weight w(e) is associated with each arc e∈E.
Let h(e) and t(e) be, respectively, the head and the
tail of arc e∈E (i.e., arc e goes from vertex t(e) to vertex h(e)). Let πν denote the
potential of vertex ν∈V. Thus,
each arc e represents a constraint πh(e)−πt(e)≥w(e).
The directed
graph constructed from (4.1)–(4.4) contains N+1 vertices, 0,1,…,N,the potentials of which are,
respectively, r0,r1,…,rN. Each constraint in the form of rj−ri≥ci,j,0≤i,j≤N from (4.1)–(4.4) is represented by an arc from vertex i to vertex j with
weight ci,j. Thus, the set
of constraints in (4.1)–(4.4) can be represented
as (4.14)rj−ri≥ci,j,∀(i,j)∈E. With the constructed directed graph, a hoist
assignment R satisfies (4.1)–(4.4) if and only if all
the arcs in graph G(V,E) satisfy (4.14). Let C be a directed cycle (circuit) on graph G(V,E),
then by (4.14)(4.15)∑∀(i,j)∈C(rj−ri)≥∑∀(i,j)∈Cci,j. Since ∑∀(i,j)∈C(rj−ri)=0, we have (4.16)∑∀(i,j)∈Cci,j≤0. Thus, if there are positive circuits in the
associated directed graph, then (4.1)–(4.4) are said to be infeasible
in sense that they cannot lead to any feasible hoist assignment. On the other
hand, if there is no positive circuit in the directed graph, then (4.1)–(4.4) are said to be feasible
or self-consistent and a feasible hoist assignment can be derived from them.
The following theorem gives how to derive a feasible hoist assignment R if (4.1)–(4.4) are feasible or
self-consistent and its complexity.Theorem 4.2.
For a given cycle timeT0, if there is no positive circuit in the
directed graph constructed from
(4.1)–(4.4), then a feasible
hoist assignment R must exist and it can be obtained in O(N3) in the worst case.Proof.
Letli be the
length of the longest path from vertex 0 to vertex i on graph G(V,E) satisfying (4.17)lk+∥Pk,i∥≤li,0≤i,k≤N,k≠i, where Pk,idenotes the longest path
from vertex k to vertex i. By definition, l0=0. It is easy to see that R=(r0,r1,…,rN)=(l0,l1,…,lN) satisfies (4.14), which also implies that such an R satisfies (4.1)–(4.4). By Theorem 4.1, such an R is a
feasible hoist assignment for T0. Thus,
solving
(4.1)–(4.4) and consequently checking the feasibility for T0 can be transformed into solving a
longest path problem for the corresponding directed graph, which can be solved
in O(|V∥E|), where |V| and |E| are, respectively, the number of vertices
and the number of arcs in the directed graph. For this problem, we have |V|=N+1,|E|≤(N+1)(N+2)/2. Hence, we have
Theorem 4.2.Example 1 (continued)
The directed
graph corresponding to (4.9)–(4.13) is shown in Figure 7.
By solving
the longest path problem for this graph, we obtain l0=0,l1=1,l2=0,l3=1. We, thus, find a
feasible hoist assignment R=(r0,r1,r2,r3)=(0,1,0,1) for T0=23. This implies that T0=23 is feasible. It can be shown that the
values of the cycle time less than T0=23 in AT are all
infeasible. Therefore, T0=23 is the
optimal cycle time for the problem. From (2.2), we have Y0=0,Y1=22,Y2=11,Y3=6. The optimal cyclic schedule for T0=23 is shown in Figure 3. We see from Figure
3 that hoists 0 and 1 use the overlapping zone from M1 to M3. We also see
that there is sufficient time interval between them in entering into the
overlapping zone. Hence, possible collisions between them are avoided.Figure 7
The directed graph
corresponding to (4.9)–(4.13).


## 5. Algorithm and complexity analysis

The process to
solve the hoist scheduling problem considered in this paper can be summarized
as follows.Step 1.
Calculate the completion timeZj, for all j=0,1,…,N, according to (2.1).Step 2.
Calculatefi,j for all 0≤j≤N−1,j+1≤i≤N, and β.Step 3.
Construct setAT.Step 4.
Sort all the values of the cycle
time inAT in increasing order. Check the feasibility for each
given value of T, say T0, in AT in increasing order as follows.Step.
Calculatesi,jk, for all 0≤j≤N−1,j+1≤i≤N,0≤k≤K−1.Step.
Using (4.1)–(4.4) to derive the sufficient and necessary constraints that R must satisfy in order that T0∉Q(R).Step.
Construct the directed graph and solve the corresponding longest path problem. IfT0 is feasible, obtain the corresponding R, and go to Step 5. Otherwise,
go to Step 4.1 to check the feasibility for the next value of
the cycle time in AT.Step 5.
Compute the move starting times
for the optimal cycle time by using (2.2).Theorem 5.1.
The multihoist scheduling problem with constant processing times is solvable inO(N6K) time in the worst case.Proof.
Steps1 and 2, respectively, require O(N) and O(N2)times.
By the definition of AT, the total number of the values of
the cycle time in AT is O(N2Kn*). Hence, Step 3 can be
implemented in O(N2Kn*) time. In Step 4, sorting all the values of the cycle time in AT in increasing order requires O(N2Kn*(logN+logK+logn*)) time.
For each givenT0,
Step 4.1 can be done in O(N2K) time. Step 4.2 can be implemented in O(N2K). By Theorem 4.2, Step 4.3 can be implemented in O(N3) in the worst case. Without loss of
generality, we assume that each hoist in the line must perform at least one
move and each move can be performed by one and only one hoist. With this
assumption, there are at most (N+1) hoists really used for material handling in a production line with N processing tanks. Hence, we assume
that K≤(N+1). Thus, for each given T0,
Steps 4.1–4.3 can be done
in O(N3). It is known that the total number of the values of
the cycle time in AT is O(N2Kn*). To sum up, the
algorithm runs in O(N5Kn*) time.
Note thatn*=min(N+K,⌈(ZN+θN)/β⌉)−1. This
leads to n*≤(N+K)≤2N+1. Therefore, the algorithm runs in O(N6K) time in the worst case.


## 6. Computational results

The proposed algorithm was
encoded in C++. In this section, we
first use an example to verify the correctness of the proposed algorithm. Randomly generated instances
are then used to further evaluate the performance of the algorithm. The
computational experiment was done on a PC with a Pentium IV 3.0 GHz processor.The example has 20 processing tanks
numbered from 1
to 20, stations 0 and
21 being the
loading station and the unloading station, respectively. The
processing times for tanks 1 to 20 are 160, 180, 90, 150, 200, 190, 290, 170, 290,
230, 240, 86, 180, 300, 240, 180, 310, 200, 170, and 70, respectively. For anyi such that 0≤i≤N, the time for a void move from Mi to Mi+1, that is, di,i+1=3. The
other void move times are obtained accordingly with di,j=dj,i=∑k=ij−1dk,k+1, where 0≤i<j≤N+1. The move times θi=di,i+1+20, where νi=μi=10 for any 0≤i≤N.Note
that the problem with constant processing times, as addressed in this study, can be considered as a special case of the
problem with time windows, that is,
zero-width time window. Hence,
we can also solve the example using the branch-and-bound algorithm proposed in
[5]. Table 1 gives the computational
results for the example using the proposed algorithm and the branch-and-bound algorithm in [5]. In
Table 1, the columns with T* provide with the optimal multihoist cycle
times for the example, while the columns with CPU represent their corresponding
computation times (measured in seconds).Table 1
Optimal multihoist
cycle times for the example.
Number of hoistsProposed algorithmB and B algorithmT*CPU (s)T*CPU (s)K=123160.01523160.2K=211600.078116024.6K=36280.106628143.6K=43580.10935859.8K=53440.156344153.1It can be observed from Table1 that the optimal multihoist cycle times obtained with the proposed polynomial
algorithm are the same as those obtained with the branch-and-bound algorithm in
[5]. However, our polynomial algorithm significantly outperforms the
branch-and-algorithm regarding computation times. This is due to the fact that the algorithm developed in this study exploits specific properties to the problem
with constant processing times. The optimal 4-hoist schedule for the example
is shown in Figure 8.Figure 8
Optimal 4-hoist schedule for
the example.In addition,
randomly generated instances were used to evaluate the performance of the proposed
algorithm. The test
instances were generated as follows using integer uniform distributions. For anyi such that 0≤i≤N, the time for a void move from Mi to Mi+1, that is, di,i+1, was
randomly generated on [2, 5]. The other void move times are obtained
accordingly with di,j=dj,i=∑k=ij−1dk,k+1, where 0≤i<j≤N+1. The move times θi is set to θi=di,i+1+20, where νi=μi=10 for any i such that 0≤i≤N. The processing times ti were generated
on [30, 300]. We fix the value of N = 20,
30, 40, and 50. For each N = 20, 30, 40,
and 50, 100 test instances were generated. We consider five values of K : 1, 2, 3, 4, and 5, and 2000(=4×100×5) test problems were solved.Table2 reports the average reduction
in optimal cycle times (or equivalently improvement on the throughput) achieved
by the multihoist schedules with respect to the single-hoist schedules,
calculated by the optimal single-hoist cycle time divided by the optimal
multihoist cycle time. We see from Table 2 that the reduction in optimal cycle times achieved by the multihoist schedules
is very significant, ranging
from 2.08 to 9.37.Table 2
Average reduction
in cycle times by using multihoist for test instances.
ProblemK=2K=3K=4K=5N=202.083.986.257.63N=302.264.396.819.37N=402.103.896.288.79N=502.183.816.068.67Table3 gives the
average computation times in CPU seconds for test instances. It can be seen
from Table 3 that the algorithm developed in this study is very efficient. Note that
practical electroplating lines generally have 10 to 20 processing tanks and 1
to 3 hoists. For this size of problems, the computation times are within 80 milliseconds. For the 20-tank and 30-tank instances with 1 to 5 hoists, our algorithm found optimal cycle times
generally within
one second. Even
for the very large problem with 50 tanks and 5 hoists, the proposed algorithm
can obtain the optimal solution within 25 seconds.Table 3
Average computation
times for test instances (s).
ProblemK = 1K = 2K = 3K = 4K = 5N = 200.010.050.080.100.14N = 300.050.220.570.901.30N = 400.130.621.984.116.26N = 500.281.394.4611.9023.92A further examination of Table3
reveals that the computation times increase with the number of tanks and hoists,
as the algorithm runs in O(N6K) time in the worst case
according to its complexity estimation, but the computation times increase not so
rapidly with the number of tanks as the complexity of the algorithm indicates.
This may be due to the fact that the complexity analysis is a worst-case
estimation and sometimes may be far from the reality. To find the optimal cycle time, the values of the cycle
time in AT are checked in increasing order until a feasible one is found. In the
complexity estimation, the number of values
of the cycle time to be checked is estimated at O(N3K) in the worst case. This estimation is
too pessimistic. In fact, only a small part of the values of the cycle time in ATneeds to be checked before the optimal cycle time is found,
and more importantly, the total number of values of the cycle time in AT is
significantly less than its theoretical estimation O(N3K) (less than 10% for most of the instances), since most values of x^ and y^ in AT are less than β and the values of x^ and/or y^ may
take the same value.


## 7. Conclusion

This paper proposed
a polynomial algorithm for the no-wait cyclic multihoist scheduling problem in
an electroplating line. Computational results on randomly generated instances
have shown that the algorithm is very efficient. The algorithm developed
in this study can be served as a subroutine or a heuristic in solving the
problem with time windows.An important extension of this
study is to develop efficient heuristic for the hoist scheduling problem with
time windows, which is an NP-hard problem, using the algorithm developed in this
study as a subroutine. To achieve this extension, we should take the processing
times, which must be within given time windows, as decision variables of our
problem. If all processing times are fixed, then the corresponding problem can
be solved using the proposed algorithm. Thus, the key to solving the problem with
time windows is to design efficient search strategy to find an optimal combination
of fixed processing times within given time windows. This is our ongoing work.



---

*Source: 364279-2008-05-18.xml*