The International Journal of Flexible Manufacturing Systems, 7 (1995): 207-227 © 1995 Kluwer Academic Publishers, Boston. Manufactured in The Netherlands.

Scheduling Algorithms for a Two-Machine Flexible Manufacturing System G. ANDREATTA

Department of Pure and Applied Mathematics, University of Padova, Via Belzoni, n. 7, 1-35131 Padova, Italy L. DESERTI

Ipsia Giorgi, Treviso, Italy L.N. GIRALDO

Cerved, Padova, Italy

Abstract. The flexible manufacturing system (FMS) considered in this paper is composed of two CNC machines working in series--a punching machine and a bending machine connected through rollers acting as a buffer system of finite capacity. The main difference between the present problem and the standard two-machine flow shop problem with finite intermediate capacity is precisely the buffer system, which in our problem consists of two stacks of parts supported by rollers: the first stack contains the output of the punching machine, while the second stack contains the input for the bending machine. When the second stack is empty, the first stack may be moved over. Furthermore, the capacity of each stack depends on the particular part type being processed. The FMS can manufacture a wide range of parts of different types. Processing times on the two machines are usually different so that an unbalance results in their total workload. Furthermore, whenever there is a change of the part type in production, the machines must be properly reset--that is, some tools need to be changed or repositioned. A second important difference between the present problem and the usual two-machine flow shop problem is the objective. Given a list of p part types to be produced in known quantities, the problem considered here is how to sequence or alternate the production of the required part types so as to achieve various hierarchical targets: minimize the makespan (the total time needed to complete production) and, for instance, compress the idle periods of the machine with less workload into a few long enough intervals that could be utilized for maintenance or other reasons. Although Johnson's rule is optimal in some particular cases, the problem addressed in the paper is NP-hard in general: heuristic procedures are therefore provided.

Key Words: two-machine FMS, scheduling, heuristic algorithms.

1. Introduction I n the last few years, f l e x i b l e m a n u f a c t u r i n g systems ( F M S s ) have b e c o m e i n c r e a s i n g l y interesting f r o m b o t h a n e c o n o m i c a l a n d a scientific p o i n t o f view. A n F M S m a y b e defined as a set o f a u t o m a t i c m a c h i n e s that a r e n u m e r i c a l l y c o n t r o l l e d , a b l e to m a n u f a c t u r e p a r t s o f v a r i o u s types a n d sizes, a n d c o n n e c t e d by a t r a n s p o r t a t i o n system, w h i c h is also c o m p u t e r c o n t r o l l e d . F o r a n o v e r v i e w o f o p e r a t i o n s r e s e a r c h m o d e l s a n d m e t h o d s a p p l i e d to F M S s , w e a d d r e s s t h e i n t e r e s t e d r e a d e r to t h e r e f e r e n c e s listed at t h e e n d o f this article (e.g., Stecke a n d Suri, 1985, 1988).

208

G. ANDREATTA, L. DESERTI, AND L.N. GIRALDO

In this article we present scheduling algorithms for a two-machine FMS (see Figure 1), which is described in detail in Section 2. The data, in particular those used in Section 6, were obtained from an Italian factory that specializes in the production of FMSs for sheetmetal cold-working. Each of these FMSs costs from $1 to 2 million U.S. Several papers in the literature deal with the problem of scheduling a two-machine FMS (see, for instance, Agnetis, Arbib, and Stecke, 1990). However, none is directly applicable to our problem. The motivation for this study is primarily that of evaluating the performance of a heuristic algorithm used by the factory and, eventually, to suggest a better one. The present investigation actually proved that the heuristic algorithm was not only far from optimal but was also implemented in the wrong way. It gave incorrect results: they looked better than they were in practice. In Section 2, after we describe the particular FMS considered, the problem is stated more precisely and is shown to be NP-hard in general. In Section 3 we discuss the maximum cardinality of a pack--a concept, defined in Section 2, that plays a crucial role in the sequel. Section 4 is devoted to the scheduling of a single pack. In Section 5 the scheduling of two packs is discussed and Johnson's rule is proved to be optimal in this case. Section 6 is devoted to the general scheduling problem with p part types: heuristic procedures are presented together with a pair of real-life examples for which Johnson's rule is not optimal.

2. A particular FMS The FMS considered in this article (see Figure 1) is composed of two CNC machines working in series: a punching machine (denoted by M1 in the following) and a bending machine (M2). The FMS can manufacture a wide range of parts of different types. Whenever there is a change of the type in production, the machines need to be properly reset. The setups are done manually. The setup times, which in practice may vary from a few minutes to half an hour, are assumed by the factory to be fixed and identical on the two machines (10 minutes). The setup operations include replacement or repositioning of some tools.

Punching Machine

Bending Machine Stack P1

Rollers Figure 1. Graphical representation of a particular two-machine FMS.

SCHEDULING ALGORITHMSFOR A TWO-MACHINEFMS

209

Every part is first processed by machine M1 and then by machine M2. The part processing times, which depend on the type of part being processed and on the machine processing it, are assumed known and deterministic. The two machines are connected through rollers that also act as a buffer system of finite capacity. The rollers may support two stacks of parts: the first stack contains the output of the punching machine, and the second stack contains the input for the bending machine. When the second stack is empty, the first stack may be moved over (the two stacks will be denoted by P1 and P2). The transfer times from M1 to P1, from P1 to P2, and from P2 to M2 are considered negligible by the factory and therefore are assumed equal to zero in this article. Each stack may contain only parts of the same type and size. Furthermore there is an upper bound (stack capacity) to the number of parts that each stack may contain: this bound depends on the weight, thickness, and type of parts being processed. For instance, in the FMS considered in the examples to be presented later on, the maximum allowed weight is 5 tons, and the maximum allowed height of a stack is 400 millimeters (about 16 inches). The buffer system just described constitutes a first difference between the problem here considered and the classical flow shop problem with finite intermediate capacity. In fact, if stack P1 reaches its maximum allowed number of parts and stack P2 is not empty, then machine M1 must stop and wait. A second difference concerns the objectives that the firm is aiming at: here we not only want to minimize the makespan--that is, the time interval during which the FMS manufactures the required production--but we also want to aggregate the idle times of the machines into a few long enough intervals (at least half an hour, so that they may be used for maintenance or for processing atypical parts that only require one machine) instead of many short unused intervals. For the case here discussed, other objectives or constraints such as due dates are of no interest: the production list is composed of part types of the same priority. Theorem 2.1. The problem of finding an optimal scheduling for the FMS just described

is NP-hard. Proof First, notice that finding a schedule for the described FMS that is optimal with respect to the hierarchical objectives considered is at least as hard as finding a schedule that only minimizes the makespan. Consider now a subcase of the problem in which we assume that no setup is needed (setup time = 0), that only one part for each part type is required, and that each stack has capacity 1 (and we only want tO minimize the makespan). In order to prove the assertion of the theorem, it is enough to prove that this subcase is NP-hard. Notice that any two-machine flowshop, having an intermediate buffer of capacity 2 with a FIFO discipline in the buffer, can be interpreted as a particular instance of our subcase. This concludes the proof, since the problem of scheduling a two-machine flowshop, having an intermediate buffer of capacity 2 has been shown to be NP-complete by Papadimitriou and Kanellakis (1980). • In the literature there are two main approaches to part type selection. In the batching approach (Whitney and Gaul, 1985; Hwang, 1986; Rajagopalan, 1986), all part types are partitioned into disjoint batches, and all parts in a particular batch are machined continuously

210

G. ANDREATTA,L. DESERTI,AND L.N. GIRALDO

until all requirements of all part types are finished. In the flexible approach (Stecke, 1992; Stecke and Kim, 1988, 1989, 1991) all part types in a particular batch are machined in certain relative ratios that balance machine workloads until the requirements of some part type are finished. The approach followed in this paper is somehow related to the batching rather than to the flexible approach to part type selection. Let us now introduce the concept of lot and that, slightly different, of pack. By lot we mean a subset of parts of the same type and size that are manufactured consecutively by the FMS: in other words, the production of a lot is not interrupted for producing parts of a different lot. Notice that during the production of a lot the machine with lower workload may have to stay idle for some time intervals (we will be interested in combining these idle periods into as few and as long periods as possible). By pack we mean a subset of a lot that can be processed consecutively without either machine having to stop. In other words, the difference between a pack and a lot is that during production of a lot, one of the two machines might be idle for some time, whereas a machine can only be idle either before the beginning or after the completion, but never during the production of a pack. As a consequence, during the production of a pack, the capacity of the stacks is never saturated and therefore the entire system behaves like a system with infinite buffer capacity. The decision variables are the following: • The number and consistency of the lots into which each part type production has to be divided, • The sequence according to which the various lots (of the various part types) have to be manufactured, and • The number of packs into which each lot has to be subdivided and their scheduling. Table 7 shows a possible production schedule for a problem discussed later in Section 6 (example 6.2) whose characteristics are reported in Table 4. Notice that the production of type D parts is broken into two packs (but only one lot) with machine M1 having an idle period of approximately 22 minutes amid the processing of the two packs.

3. Maximum cardinality of a pack In this section, we assume that all parts belong to the same part type and we want to find the maximum cardinality of a pack (i.e., the maximum number of parts that may be processed consecutively, without interruptions, on both machines). This number will be denoted in the following by n*. In order to find n*, let us explicitly assume that the time moment when the parts contained in stack P1 are moved to P2 coincides with the moment when M2 has completed the processing of the parts previously waiting in P2 (with the exception, of course, of the first transfer). Let us denote by t 1 and t2, the part processing times on M1 and M2, respectively. Furthermore, let tr be the setup time (which, as already said, is the same on both machines) and let k be the maximum buffer capacity, which depends on the characteristics of the parts to be produced.

SCHEDULING ALGORITHMSFOR A TWO-MACHINEFMS

211

It is useful to classify a part type according to one of the following two classes. We will say that a part type belongs to class o~ if tl < t2; if t 1 > t 2 we say that the part type is of class co. The case tl = t?_ may be treated as an extreme case of any of the previous cases.

3.1. Case 1: Part type o f class o~ 01 < t2) In this case, it is better that the first transfer (from P1 to P2) be accomplished as soon as M1 has completed the processing of the first part. Let nl = 1, An 1 = 0, and, for any j _> 2, let us recursively define

L

nj=

nj-1 • ~tl + z X n j _ l

,Anj =

-1

tl

The sequence n/ is monotone nondecreasing and there exists an index j* such that

nj* < k and nj*+l > k. The quantities nj and Anj may be interpreted as follows: nj is the number of parts that will pile up on stack P1 while machine M2 is processing the previous nj_l parts and Anj is a number between 0 and 1 representing the partial processing of the part present on machine M1 when M2 just completes the processing of the nj-1 parts. From all of the above it is easy to verify that

j* n* = ~-]j nj + k. j=l

3.LL Example 3.1. Consider a simple toy problem where tr = 0 seconds, t 1 = 11 seconds, t2 = 20 seconds, and k = 4. We get nl = 1, Anl = 0, n2 --- L 2 0 / l l J = 1, An2 = 9/11, n 3 = L20/ll + 9 / l l J = 2 , ~ n 3 = 7/11, n4 = L2 . 2 0 / 1 1 + 7 / l l J = 4 , An4 = 3/11, and finally n5 = L4 • 20/11 + 3 / l l J = 7 > k = 4. In this example then j* = 4 and n* = n 1 + n2 + n3 + n4 + k = 1 + 1 + 2 + 4 + 4 = 12. The scheduling of this pack, which contains only 12 parts, is depicted in Figure 2. Its makespan is 251 seconds. Machine M1 stays idle for a period of 119 consecutive seconds and machine M2 stays idle for only 11 seconds.

M1 P1 P2

OlO

11o

21o

41o

314

I I

I I

I I

I I

I I

o 13

11 1

91

132

Ol 0

OlO o I1

11

31

M2 time

51

Figure 2. Scheduling of a pack of class or.

251

212

G. ANDREATTA, L. DESERTI, AND L.N. GIRALDO

Notice that transfers of parts form P1 to P2 occur at the following times (and in the following quantities): 1 (= nl) part at time 11, 1 (= n2) part at time 31, 2 (= n3) parts at time 51, and 4 (= n4) parts at time 91. At this point, stack P1 is filled up to its capacity (k = 4), which happens at time 132, and then machine M1 stays idle. Notice also that, at time 31, exactly 9/11 (= Anz) of the part currently in M1 has been processed. Analogously, at time 51, exactly 7/11 (= An3) of the part in M1 has been processed and finally, at time 91, exactly 3/11 (= An4) of the part in M1 has been processed. Denoting by (Pl, P2) the state of stacks P1 and P2 when P1 contains Pl parts and P2 contains P2 parts, the state of the stacks evolves as follows: (0,0) up to time 22, from time 22 to 31 the state is (1,0), from time 31 to 33 it is (0,0), from 33 to 44 it is (1,0), from 44 to 51 it is (2,0), from 51 to 55 it is (0,1), from 55 to 66 it is (1,1), from 66 to 71 it is (2,1), from 71 to 77 it is (2,0), from 77 to 88 it is (3,0), from 88 to 91 it is (4,0), from 91 to 99 it is (0,3), from 99 to 110 it is (1,3), from 110 to 111 it is (2,3), from 111 to 121 it is (2,2), from 121 to 131 it is (3,2), from 131 to 132 it is (3,1), from 132 to 151 it is (4,1), from 151 to 171 it is (4,0), from 171 to 191 it is (0,3), from 191 to 211 it is (0,2), from 211 to 231 it is (0,1), from 231 until the end it is (0,0).

3.2. Case 2: Part type of class ~ (q > t2) In this case, it is better to operate the first transfer only when there are k parts in P1 (the buffer capacity has been reached). The maximum number of parts in a pack is then given by j* n* =k+

E nj, j=l

where nl = k, An1 = 0, and the remaining nj and Anj, for j _> 2, are recursively computed as follows:

nj = nj-1 " ~t2 -[" ARj-1 ~ , Anj = QnJ-1 " t2 tl + Anj-l~ - nj' where j* satisfies the conditions nj* > 1; nj*+l < 1. The interpretation of nj and Anj is the same as in Case 1.

4. Scheduling of a single pack Let tl, t2, tr, k, and n* be defined as in Section 3 and let N be the actual number of parts in the pack (N < n*). It is again convenient to distinguish two cases.

4.1. Case 1: Pack of class ~ (t 1 < t2) The minimum makespan obviously is T = tr + tl + N " t2.

SCHEDULING ALGORITHMSFOR A TWO-MACHINEFMS

213

The proposed scheduling is as follows: M1 consecutively processes the N parts and then remains idle during an interval of length S1 =

T - (tr + N " tl)

= q + N ' ( t 2 - q)

= t2 + (N - 1) • (t2 - tl). M2 initially is idle during an interval of length s2 = q and then consecutively processes the N parts. This schedule is optimal with respect to the following objectives: • Makespan minimization, • The makespan being minimum, minimization of the completion time on M1; • The makespan being minimum, minimization of the number of idle periods of M1, or, which is equivalent in this case, maximization of the length of idle periods of M1.

4.2. Case 2: Pack o f class o~ (t 1 > t2)

The minimum makespan is T=tr

+ N'tl

+ t 2.

The proposed scheduling is the following: M1 consecutively processes the N parts composing the pack and then stays idle during an interval of length Sl = t2. M2 remains initially idle during an interval of length s2 = T

-

(t r +

N " t2)

= t2 + N ' ( t 1 - t2) = q + (N-

1)'(q

- t2).

and then consecutively processes the N parts. This scheduling is optimal with respect to the same objectives stated in the above Case 1, provided that M2 is substituted for M1.

5. S c h e d u l i n g of two packs

The main result of this section is the following Theorem 5.1. Johnson's rule is optimal for scheduling any two packs. We postpone the proof of this theorem until the end of the section.

214

G. ANDREATTA, L. DESERTI, AND L.N. GIRALDO

A second important aspect of this section is that it provides some details on how to compute, for any two packs A and B, the maximum reduction in the overall makespan that can be obtained by starting the processing of the pack B on M1 before the processing of A has been completed on M2. These reductions, denoted by raB, will be called savings and will be needed in Section 6. Their computation is not trivial andfor this purpose it is convenient to distinguish three cases. Before doing that, let us introduce some notations. Given two packs of different part types (let us call them pack A and pack B), let

tr, ~11, ~1, ~2, I~2, kA, kB, NA, NB, n'A, n~, TA, TB, s~, s~, s A, be defined as in the previous section: the addition of indices A and B is used only to distinguish between the two types of products. Since we are speaking of packs it must be

NA <- nA and NB --< nn. For clarity sake let us assume that the production sequence is: pack A first and then pack B (this sequence may well not be optimal). Since M1 stops processing parts A before M2 does, and given that M2 starts processing parts B after M1 does, one can obtain a reduction in the overall makespan by trying to properly anticipate the production of B. In other words, M1 may start the processing of B before M2 has completed the processing of A. In order to compute the minimum makespan (conditional upon the fact that the processing of A occurs before the processing of B) let us define the following functions n'(t) and

n"(t). n'(t) is the number of parts of type A present in stack P1 after a period of time t has elapsed since the beginning of the processing of A;

n"(t) is given by the number of parts of type A in stack P2 at time t plus the fraction representing the ratio between the remaining processing time of the part currently being processed by M2 and the quantity ~. Notice that ~ • n" (t) represents the time needed by M2 to fully process all parts present in P2. The functions n'(t) and n" (t) are well defined and easy to compute for any t _> 0. Furthermore, let

~

ifn'(tr + N A ' ~

~ 0,

if NB <- kB;

0,

h1 =

h2 =

ifn'(tr + NA " l~l + tr + /ffl) = 0;

Max{0; ~ " n"(t r + N A • ~ + tr) - ~ll },

+ tr + ~) > O.

Max{O; ~ " [n"(tr + Na" ~ + hi + tr + ~)] -- ~ " kB},

h 3 = Max{0; (S~l - hi - h2) - sB}.

if N~ > kB.

215

SCHEDULING ALGORITHMS FOR A TWO-MACHINE FMS

The quantity

(tr + NA" 71 + tr) corresponds to the first moment in which M1 could start the processing of B. Notice, however, that, if P1 is not empty as soon as the first part of B is processed by M1, i.e., if n'(t r + N A • ~

+ t r + t~l) >

0,

then M1 will have to wait for a period of length h I that is the time needed by M2 to complete the processing of the parts in P2, minus the time needed by M1 to process one part of B. In other words, h 1 is the minimum amount of time required between the end of the processing of A on M1 and the beginning of B on M1 in order to find stack PI free when needed by the first part of B. The quantity h2, if positive, corresponds to a further delay of the start of processing of B on M1 due to the fact that otherwise M1 will process kB parts before M2 had the time to process all the parts in P2, thus saturating P1 and therefore causing a forced idle period (on M1) of length h 2. The quantity h 3 represents a possible third delay due to the fact that the time displacement among the starting of processing B on the two machines may not be bigger than s~.

Example 5.1. Consider the case where tr = 0 seconds, ~ = 11 seconds, ~ = 20 seconds,/cA = 4, and NA = 12 (same data as for example 3.1) and B is such that ~ = 11 seconds, ~ = 5 seconds, kB = 4, and NB = 7. For such an instance one obtains hi = 28, h2 = 36, and h 3 = 8. They are shown in Figure 3. Notice that if NB > 8, then h 3 would have been zero.

h1

h3

h2 ~1

4A 0

3A I 4A I I 1A I 1A

P1

P2 m

time

~1

IBI I I I I I__ I I

MI

M2

TM

__

I I I

0 3A

I I I 1A

-

I 132

I

I

I! 204

Figure 3. Scheduling of a pack of class oL followed by a pack of class co.

I A I 11 I

251

216

G. ANDREATTA,L. DESERTI, AND L.N. GIRALDO

The state of the stacks, at selected times, is as follows: from time 204 to time 211 it is (0,2A), from 211 to 215 it is (0,1A), from 215 to 226 it is (1B,1A), from 226 to 231 it is (2B,1A), from 231 to 237 it is (2B,0), from 237 to 248 it is (3B,0), from 248 to 251 it is (4B,0), from 251 to 256 it is (0,3B), from 256 to 259 it is (0,2B), from 259 to 261 it is (1B,2B), from 261 to 266 it is (1B,1B), from 266 to 270 it is (1B,0), from 270 to 271 it is (2B,0), from 271 to 276 it is (0,1B), and from 276 to 286 it is (0,0). If two packs A and B are of different type and are processed in this order, then the minimum makespan is given by TAB = t r + NA " ~ + h 1 + h 2 + h 3 + t r + NB" ~II + Sf <-- TA + T B.

Furthermore, the saving obtained by anticipating the processing of B is given by ran = ( T A + TB) -

TAB = SA -- (h 1 + h 2 + h3) = M i n { s ~ - h I - h2; s~}.

L e m m a 5.1. ran > O. Proof Let us distinguish between two cases according to whether h 3 > 0 or h 3 = 0. If h 3 > 0, then

rAB = Sla -- (hi + h2) - [sA - hi - hz - s B] = s B > 0. If h 3 = 0, then: rAS = SlA -- (hi + h2). Notice that i) s A = ~ " [n'(t~ + N z " ~ ) + n" (t~ + NA" ~ ) I , ii) hi <- ~ " [n"(tr + Na " d + t~)], iii) h 2 < ~ • [n"(t r + N A • ~ + t r + hi)] = ~ • [n'(t r + N A • ~11 + tr)]. From (i), (ii), and (iii), one obtains that hi + hz < ~ ' [ n ' ( t r

+ NA'~

+ tr) + n"(t~ + N A ' ~

+ tr)]

< ~ • [n'(t~ + N a " ~ ) + n"(tr + NA" ~)1 = s A

so that rAB = sA1 -- (h 1 + h2) > O.

If the packs A and B belong to the same part type, then TAB = TA + TB - Min{#11, 4 } ran = M i n { ~ , 4 } .

217

SCHEDULING ALGORITHMS FOR A TWO-MACHINE FMS

The optimal scheduling of the two packs may be obtained by virtue of the following propositions. Proposition 5.1. I f A and B both belong to class ot and 4 < ~ , then TAB < TBa. P r o o f A necessary and sufficient condition for TAn < TBa is that ran > rBA.

Hence, if we prove the following two facts, we are done: I) rBA = 4 II) rAB > 4 . P r o o f of (I) rBA = 4 .

Let hA = h 1 and hA = h 2 as previously defined, and let hiB and hi be defined in an analogous way (corresponding to B being processed first and A second). We have: rBa = M i n { s ~ - h B - h~; sA}.

In order to prove that rBA = 4, taking into account that s~ = 4, it suffices to prove t h a t s ~ - h~ - h~ _ s A. To this aim, let us distinguish the following three subcases: (I.i) Ifh~ = h l

= 0, then

s~ - hB1 - h l = s a = ~ + (NB -

1)'(~--

~ ) > ~ > ~ > 4 = sA

s o t h a t rBA = ~;

(I.ii) If h~ > 0, then, by using an analogous argument as in the proof of Lemma 5.1, one obtains

h f - hl > 4"k

> 4 = 4,

so that rBA = 4 also in this case; (I.iii) If h~ > 0 and h~ = 0, we have

n'(tr + NB'd~ + tr) >- 1, so that sB1 -- h B - h~ = s~ - h f = ~ " n ' ( t r + N B " ~ + tr) >_ ~ > ~ > 4

and therefore rBa = 4 in all cases and this completes the proof of the first part.

218

G. ANDREATTA,L. DESERTI,AND L.N. GIRALDO

(II) rAB > ~11" rAB = M i n { s : - hA -- hA; s~)

IfrAB = s BthenrAB = s B = ~ > 4. If rAB = s~ -- h A - hA, then, once more, it is convenient to distinguish three subcases: (II.i) If hA = hA = 0 t h e n s A - h A - h A = s A = ~ + (N A -

1)'(~

- 4 ) > ~ > 4;

(II.ii) If hA > O, then, by using an argument analogous to the proof of Lemma 5.1, one obtains:

# - h A - h A > g . k . > # > #; (II.iii) If hA = 0 and h~ > 0, then s~ - hA - hA = s• - h A = ~ 2 " n ' ( t r + NA" ~11 + tr) >-- ~ >

and thus rAB > # in all cases.

•

Proposition 5.2. I f A and B both belong to class ¢o and ~ > 2 then TAB < TBA. Proof. A necessary and sufficient condition for TAB < TBa is that r ~ > r ~ .

Let us use the same notation as in the proof of Proposition 5.1. Since h A = hA = hi~ = h~ = 0, we have rAB = Min{s~ - hA - hA; s B} = M i n { ~ ; 2 + N " ( ~ - 2)} > 2; rBA = Min {SB1 -- h B - h~; sA} = M i n { 2 ; ~ + N " ( 4 - ~)} = 2

and therefore rAB > rBA.

•

Proposition 5.3. I f A belongs to class ~ and B belongs to class co then TAB < TBA. Proof A necessary and sufficient condition for TAB < TBA is that ran > rBA. Let h~, h~,

hiB, and h~ be defined as in the proof of Proposition 5.1. We have rBA = Min{s~ - h f - h~; s~} = M i n { 2 ; 4 }

so that rnn < 2 < s~ and rBA <_ 4 < SA1

-

-

hA -- hA,

and therefore rBA < MinlsA - hA - h A ; s ~ }

= ran

•

SCHEDULINGALGORITHMSFOR A TWO-MACHINEFMS

219

Proof of Theorem 5.1. Let us distinguish the following three cases: if both packs belong to class a, then the result follows from Proposition 5.1; if both packs belong to class w, then the result follows from Proposition 5.2, and finally, if one pack is of class a and the other of class ~, then the result follows from Proposition 5.3. •

6. Production and scheduling of p part types Although Johnson's rule is optimal in some particular cases, the problem addressed in the article is NP-hard in general, as we have proved in Section 2. It is therefore natural to resort to heuristic procedures. In this section, heuristic methods are outlined for the following cases: when all parts of a same type have to be processed consecutively as a unique lot and when production of parts of a same type may be broken into several lots.

61. Case 1: Each part type has to be processed consecutively as a unique lot This is the typical case when the setup time (or cost) is excessively high; often it is actually an explicit constraint imposed by the factory. The decision variables are the number of packs into which every lot (which corresponds to a part type) has to be divided; the number of parts in each pack, and the scheduling of the various lots and packs so obtained. As for the division of lots into packs, we suggest dividing each lot into the minimum number of packs: each pack is of maximum cardinality, with the possible exception of one pack per lot that will be called the residual pack. This proposal has the advantage of minimizing, within each lot, the number of idle periods. On the other hand, since the total idle time on the machine with less workload, during the production of a lot, is a given constant, which does not depend upon the way the lot is divided into packs, it is clear that minimizing the number of idle periods (of equal length) is equivalent to maximizing the duration of each idle period, with the possible exception of one period per lot. This strategy then achieves one of the secondary objectives stated in Section 2. There is no guarantee, of course, that it should be optimal. For obtaining the scheduling of the lots and packs, we suggest resorting to an approach based on the traveling salesman problem (TSP). Of course, the idea of resorting to a TSPbased approach is not new in scheduling theory. See, for instance, Gilmore and Gomory (1964) or, more recently, Kise, Shioyama, and Ibaraki (1991). We first describe the suggested approach, we then apply it to an example, and finally we briefly discuss the relationship between the problem and the TSP formulation.

6.L1. A TSP-based approach. Let us introduce a simple, complete, and directed graph G as follows. To every lot there correspond in the graph G at most two nodes: every node of G corresponds either to a residual pack or to the set of all packs of maximum cardinality of the same lot. Besides, there is also a dummy node s in G. To the arcs of the graph G just introduced there is associated a length function defined as follows. The length d(u, v) of the generic arc (u, v) is equal to the saving, computed

220

G. ANDREATTA, L. DESERTI, AND L.N. GIRALDO

as described in the previous section, that can be achieved by processing first one of the packs corresponding to node u and then one of the packs corresponding to node v. If u = s o r v = s, then we put d(u, v) = O. In the graph thus obtained, we look for a Hamiltonian Cycle of Maximum Length. In order to prevent that the production of a lot be split, we augment d(u, v) by a properly chosen constant M every time u and v correspond to packs of the same lot.

6.1.2. Example 6.1. Both this and the following example use real data. Consider a production list consisting of five part types with the characteristics reported in Table 1. The required number of parts of type A, C, D, and E is less than the corresponding n* so that each of these part types is associated with only one mode {a, c, d, e}. Part type B, however, has to be split into three lots: two of maximum cardinality (382 parts each) and the residual one (containing thirty-six parts). So in the graph we introduce two more nodes b' (corresponding to the two lots of maximum cardinality) and b" (corresponding to the residual one). The set of nodes of G is therefore the following: V(G) = {s, a, b', b", c, d, e}. Since, for the example considered, tr = 600 seconds, the matrix of all possible savings results as follows: s s

--

a

0

a

b' 0

--

b"

c

d

e

0

0

0

0

0

38

38

45

45

45

b'

0

10045

--

M

9060

55

48

b"

0

1730

M

--

1730

55

48

c

0

60

38

38

--

55

48

d

0

3018

38

38

3018

--

48

e

0

10045

38

38

9060

55

--

The exact TSP solution is then given by

s~b"~b'~

c~d~e~a~s,

Table I. Example 6.1 (time in seconds).

Part Type

Production Requirements

Part Processing Time on M1

Part Processing Time on M2

Stack Capacity

n*

A B C D E

500 800 300 250 600

65 38 90 55 48

45 85 60 78 90

320 200 266 400 266

1,357 382 1,062 1,663 658

221

SCHEDULING ALGORITHMS FOR A TWO-MACHINE FMS

Table 2. Optimal schedule for Example 6.1: Makespan 185,038 (time in seconds).

Part Type

Pack Cardinality

Pack Starting Processing Time on M1

Pack Starting Processing Time on M2

Idle Time on M1

Idle Time on M2

B B B C D E A

36 382 382 300 250 600 500

0 3,660 36,130 52,118 87,183 107,290 142,618

38 3,698 36,168 68,638 87,238 107,338 161,938

1,692 17,954 1,472 7,465 5,757 5,928 9,320

38 0 0 0 0 0 0

which may be translated into the schedule given in Table 2, with a makespan of 185,038 seconds (approximately 51 hours and 24 minutes). This schedule is optimal with respect to the objective of minimizing the makespan. In fact, machine M2, that is the machine with more workload, has no idle periods during the entire production. Furthermore, notice that all idle periods on M1 have a duration that is considered sufficiently long: the minimum such duration is nearly 25 minutes long. If we apply Johnson's rule to this example we would obtain the schedule

s~b"~b'~

e~d~c~a~s

that is illustrated in Table 3, with a makespan of 201,065 seconds. This proves that Johnson's rule is not optimal for this problem.

6.1.3. Discussion of the TSP-based approach. We have already seen that the problem considered in this paper is NP-hard in general (Theorem 2.1). Of course, there are particular cases that may be solved directly, by means of simple algorithms. For instance, in the particular case when all part types belong to the same class a (or w), the solution may be trivially obtained. By virtue of the propositions of Section 5, the optimal scheduling is to process the lots according to increasing values of tl (decreasing values of t2), which happens to be Johnson's rule. In the general case, given the particular nature of the savings, one may wonder if the considered TSP has in fact a special structure that makes it a polynomial problem. To this Table 3. Johnson's schedule for Example 6.1: Makespan 201,065 (time in seconds).

Part Type

Pack Cardinality

Pack Starting Processing Time on M1

Pack Starting Processing Time on M2

Idle Time on M1

Idle Time on M2

B B B E D C A

36 382 382 600 250 300 500

0 3,660 36,130 68,590 123,183 140,320 167,920

38 3,698 36,168 68,638 123,238 149,380 177,965

1,692 17,954 17,944 25,193 2,787 0 45

38 0 0 0 6,042 9,985 0

222

G. ANDREATTA,L. DESERTI,AND L.N. GIRALDO

purpose,let us recall the notion of "large" TSP. Letp and q be two arbitrary n-dimensional real vectors. The large TSP is the problem of finding a Hamiltonian tour (that optimizes the objective function) where the length matrix C = [cij] is of the special form cij = max{pi, qj}. Van Dal, van der Veen, and Sierksma (1993) prove that the maximum of the objective function for the large TSP can be obtained in polynomial time. As a matter of fact, for many of the real cases that we have encountered, the savings matrix R is such that there are two vectors p and q that satisfy rij = max{pi, qj}. Empirically, for typical values of processing times, we observed that this was the case when the packs had cardinality greater than 100. The matrix R of example 6.1, with the only exception of the two elements of value M, can be precisely obtained in this way from the vectors p = (0, 45, 10045, 1730, 60, 3018, 10045) and q = (0, 10045, 38, 38, 9060, 55, 48). It is usually the case that, for a lot i of part types of class ~0, Pi = ti~, and, for a lot j of part types of class c~, qj = tf. We solved all the instances of TSP generated as described in this section to exact optimality. It is conceivable that, depending on the size of the graph--that is, on the number of different part types to be produced--one might want to resort to a heuristic procedure. In this case we recommend the use of the insertion heuristic since this heuristic has a good performance for solving the large TSP, as reported by van Dal, van der Veen, and Sierksma (1993). As a final remark to this section, we want to point out the fact that the two-machine scheduling problem considered in this section is not theoretically equivalent to the TSP model presented in this same section. This means that even an exact optimal solution to the TSP does not necessarily provide an optimal solution to the original scheduling problem (although in practice this has been the case). The reason is that, while in the TSP the objective function is the sum of pairwise contributions, in the original scheduling problem the savings that may be obtained by scheduling B after A may depend not only on the characteristics of A and B but also on the state of the buffer before A or B are scheduled and this in turn depends on the lots already scheduled before A and B. As a result, the TSP approach described in this section is to be intended as a heuristic procedure. Once again, we want to stress the fact that in the real applications we faced, an optimal solution to the TSP did also provide an optimal solution to the scheduling problem.

6.2. Case 2: Each part type may be broken into two or more lots that can be separately processed In this case it is possible, and it may be convenient, to alternate the production of lots of different types. The choice of the heuristic that is going to be proposed, was motivated by the following considerations: • Substantial savings in the makespan are generally obtained only when the processing of a pack of class a is followed by one of class ~0; • The factory we were dealing with prefers to alternate the processing of only two part types at a time; • The factory prefers that lots pertaining to the same part type have the same number of parts.

SCHEDULINGALGORITHMSFOR A TWO-MACHINEFMS

223

It is important to notice, at this point, that whereas in the previous case (Subsection 6.1) the cardinality of each lot is a given known number, so that the only decision to make is in which order the various part types have to be produced, in the case considered in the present subsection, the main problem is how to divide the production of each part type into lots (or packs), and how many parts should be put in each pack. Evidently the TSP approach used in the previous case is not adequate to solve this problem. We suggest a heuristic procedure that obtains a schedule by recursively solving a problem of matching of maximum savings in a proper bipartite graph. The bipartite graph almost suggests itself and has already been used in the literature (see, for instance, Agnetis, Arbib, and Stecke, 1990, 1991). The matching heuristic, however, seems to be applied here for the first time. At any iteration, the graph G = (I11 U V2, J~) is built as follows. To every part type A of class ot (respectively, B of class c0) not yet fully scheduled in one of the previous iterations, there corresponds a node a in V1 (resp. b in V2). Given a E V1 and b E V2, the corresponding savings r(a, b) is computed as follows. Let Na and NB be the number of parts of A and B not yet previously scheduled and let ;CA be any number between 1 and Min{n*a, Na }. Analogously let XB be any number between 1 and Min {n'B, Ns }. For any XA and XB, let

u = Min

~

'

-~B

and let re~(XA, xB) be the total savings obtained by first consecutively processing u pairs of packs, one of type A (containing XA parts) the other of type B (containing XB parts), and then the two residual lots of A and B (containing NA -- uxa and NB -- ux8 parts, respectively) with respect to the production first of the entire part type A and then of the entire part type B. Finally, let r(A, B) = rAB(x], x~) = max rAB(XA, XB) xA,XB and

L xA

'

"

Using r(A, B) as a savings function, we look for the bipartite matching of maximum savings in G. For any pair of part types A and B that are coupled in the optimal matching, we schedule ~,* packs of A (each containing x,] parts) alternating them with ~* of B (each composed of x~ parts); In the next iteration part type.A (respectively, B) will be present if and only if Na - p Xn > 0 (respectively, NB -- u XB > 0), i.e., if and only if some parts of A (respectively, B) remain to be scheduled.

224

G. ANDREATTA, L. DESERTI, AND L.N. GIRALDO

This procedure is iterated until the residual part types all belong to the same class ot or c0, or until there are no more positive savings. When this happens, then we use the strategy described in case 1. 6.2.L Example ~2. Consider a production list consisting of five part types with the charac-

teristics reported in Table 4. Notice that the only difference with Example 6.1 is the number of parts of each type. The part types of class o~ are B, D, and E. Those of class c0 are A and C. The bipartite graph associated with this problem is G = (V1 U 112; .~), with V1 = {b, d, e}, V2 = {a, c}, and 271 = V1 × 112,where a (respectively, b, c, d, e) is the node associated with part type A (respectively, B, C, D, E). For each couple constituted by a part type A of class ~ and a part type B of class c0 we compute the quantities XA, Xn, ~ , r(A, B) which are reported in Table 5. The matching of maximum savings is composed of the two arcs (b, c) and (e, a). This means that, following the procedure just outlined, we schedule two alternating couples of packs, one of type B (containing 382 parts) and one of type C (containing 597 parts) and then a couple of packs, one of type E (containing 392 parts) and one of type A (containing 823 parts). At this point the following parts remain to be scheduled: 677 (= 1500 - 823) parts of type A, 36 (= 800 - 2" 382) parts of type B, 806 (= 2000 - 2" 597) parts of type C, 500 parts of type D, and 208 (= 600 - 392) parts of type E. Table 4. Example 6.2 (time in seconds).

Part Type

Production Requirements

Part Processing Time on M1

Part Processing Time on M2

Stack Capacity

n*

A B C D E

1,500 800 2,000 500 600

65 38 90 55 48

45 85 60 78 90

320 200 266 400 266

1,357 382 1,062 1,663 658

Table 5. Example 6.2: First auxiliary graph.

Arcs (u, v) (b, (b, (d, (d, (e, (e,

a) c) a) c) a) c)

Optimal Pack Cardinality x~

Optimal Pack Cardinality * xv

p*

Saving r(u, v)

182 382 442 442 392 392

427 597 508 338 823 548

3 2 1 1 1 1

24,347 33,810 9,340 9,330 23,441 23,424

225

SCHEDULING ALGORITHMS FOR A TWO-MACHINE FMS

The procedure is iterated. The bipartite graph has remained the same but the savings associated with the arcs have to be recomputed. The new data are presented in Table 6. The only arcs with a positive saving are the arcs (d, a) and (e, c), which obviously constitute the optimal matching. This means that we can now schedule a pack of 442 parts of type D followed by a pack of 508 parts of type A and then a pack of 208 parts of type E followed by a pack of 806 parts of type C. At this point the following parts remain to be scheduled: 169 parts of A, 36 parts of B, and 58 parts of D. We iterate the procedure. The bipartite graph now contains only three nodes and

V1 = {b, d} and V2 = {a}. The matching of maximum saving is constituted by the single arc (b, a), which means that we schedule a pack of 36 parts of type B followed by a pack of 169 parts of type A. At this point the fifty-eight parts remaining to be scheduled all belong to type D and, obviously, all the remaining lots (there is only one!) belong to the same class ~ so that the algorithm stops. Of course, it is convenient to schedule these fifty-eight parts of D just before the "couple" (D, A). The resulting schedule is reported in Table 7 and has a makespan of 373,632 seconds. It is interesting to notice that, using Johnson's rule, the makespan would have been 436,459 seconds (i.e., it would have been worse by 16.8 percent). Table 6. Example 6.2: Second auxiliary graph.

Arcs (u, v)

Optimal Pack Cardinality xu

Optimal Pack Cardinality xS

u*

Saving r(u, v)

(d, a) (e, c)

442 208

508 806

1 1

9,340 8,184

Table 7. Summary schedule for Example 6.2 (time in seconds). Part Type

Pack Cardinality

Pack Starting Processing Time on M1

Pack Starting Processing Time on M2

Idle Time on M1

Idle Time on M2

B C B C E A D D A E C B A

382 597 382 597 392 832 58 442 508 208 806 36 169

0 15,508 69,860 85,368 139,710 159,126 213,221 218,345 242,655 276,288 286,872 360,034 362,002

38 32,878 69,898 103,338 139,758 175,638 213,276 218,400 252,876 276,336 311,112 360,072 365,427

392 22 392 12 0 0 1,334 0 13 0 22 0 45

370 0 370 0 0 3 0 0 0 15,456 0 1,695 0

226

G. ANDREATTA, L. DESERTI, AND L.N. GIRALDO

Of course, there is no guarantee that our proposed schedule is optimal. A lower bound on the optimal makespan may be obtained by relaxing the constraint that the intermediate buffer has limited storage capacity. Without such constraint, the (infeasible) makespan would be 336,960 seconds (i.e., 9.8 percent better than our proposed feasibleschedule).

Acknowledgments The authors would like to thank Professor Kathryn Stecke and two anonymous referees for their very helpful comments and suggestions on an earlier version of the paper.

References Agnetis, Alessandro, Claudio Arbib, and Kathryn E. Stecke, "Optimal Two-Machine Scheduling in a Flexible Flow System," Proceedings of the Second International Conference on Computer Integrated Manufacturing, RPI, Troy, NY (1990). Agnetis, Alessandro, Claudio Arbib, and Kathryn E. Stecke, "Part Type Selection and Batch Sequencing in a Flexible Flow System," Working Paper 670, Graduate School of Business Administration, The University of Michigan, Ann Arbor, MI (1991). Deserti, Lucia and Lucia N. Giraldo, "FMS: A Classification of Recent Literature," in Francesco Archetti, Mario Lucertini, and Paolo Serafini (Eds.), Operations Research Models in Flexible Manufacturing Systems, pp. 289-305, CISM Courses and Lectures No. 306, Springer-Verlag, Wien (1989). Gilmore, P.C. and R.E. Gomory, "Sequencing a One-State Variable Machine: A Solvable Case of the Traveling Salesman Problem," Operations Research, Vol. 12, pp. 656-679 (1964). Hwang, S., "Part Selection Problems in Flexible Manufacturing Systems Planning Stage," in Kathryn E. Stecke and Rajan Suri (Eds.), Proceedings of the Second ORSA/TIMS Conference on Flexible Manufacturing Systems: Operations Research Models and Applications, Elsevier Science Publishers B.V., Amsterdam, pp. 297-309 (August 1986). Jha, Nand K. (Ed.), Handbook of Flexible Manufacturing Systems, Academic Press, San Diego, CA (1991). Johnson, S.M., "Optimal Two- and Three-Stage Production Schedules;' Naval Research Logistics Quarterly, Vol. 1, pp. 61-68 (1991). Kise, Hiroshi, Tadayoshi Shioyama, and Toshihide Ibaraki, "Automated Two-Machine Flowshop Scheduling: A Solvable Case," Institute oflndustrial Engineering Transactions, Vol. 23, No. 1, pp. 10-16 (1991). Kusiak, Andrew, Intelligent Manufacturing Systems, Prentice-Hall, Englewood Cliffs, NJ (1990). Mazzola, Joseph B. (Ed.), "Automated Manufacturing Systems;' Annals of Operations Research, Vol. 26, Baltzer, Basel (1990). Papadimitriou, Christos H. and Paris C. Kanellakis, "Flowshop Scheduling with Limited Temporary Storage," Journal of the ACM, Vol. 27, No. 3, pp. 533-549 (1980). Rajagopalan, S., "Formulations and Heuristic Solutions for Parts Grouping and Tool Loading in Flexible Manufacturing Systems," in Kathryn E. Stecke and Rajan Suri (Eds.), Proceedings of the Second ORSA/TIMS Conference on Flexible Manufacturing Systems: Operations Research Models and Applications, Elsevier Science Publishers B.V., Amsterdam, pp. 311-320 (1986). Stecke, Kathryn E., "Procedures to Determine Part Mix Ratios for Independent Demands in Flexible Manufacturing Systems," IEEE Transactions on Engineering Management, Vol. 39, No. 4, pp. 359-369 (1992). Stecke, Kathryn E. and I. Kim, "A Study of FMS Part Type Selection Approaches for Short-Term Production Planning," International Journal of Flexible Manufacturing Systems, Vol. 1, No. 1, pp. 7-29 (1988). Stecke, Kathryn E. and I. Kim, "Performance Evaluation for Systems of Pooled Machines of Unequal Sizes: Unbalancing versus Balancing" European Journal of Operational Research, Vol. 42, pp. 22-38 (1989). Stecke, Kathryn E. and I. Kim, "A Flexible Approach to Part Type Selection Using Part Mix Ratios in Flexible Flow Systems," International Journal of Production Research, Vol. 29, No. 1, pp. 53-75 (1991).

SCHEDULING ALGORITHMS FOR A TWO-MACHINE FMS

227

Stecke, Kathryn E. and Rajan Suri (Eds.), "Flexible Manufacturing Systems: Operations Research Models and Applications," Annals of Operations Research, Baltzer, Basel, Vol. 3 (1985). Stecke, Kathryn E. and Rajan Suri (Eds.), "Flexible Manufacturing Systems: Operations Research Models and Applications II," Annals of Operations Research, Baltzer, Basel, Vol. 15 (1988). van Dal, Ren~, Jack A.A. van der Veen, and Gerard Sierksma, "Small and Large T SP:-Two Polynomially Solvable Cases of the Traveling-Salesman Problem," European Journal of Operational Research, Vol. 69, pp. 107-120 (1993). Whitney, C.K. and T.S. Gaul, "Sequential Decision Procedures for Batching and Balancing in FMSs," Annals of Operations Research, Vol. 3, pp. 301-316 (1985).