- Email: [email protected]

lk

Indl,m4;r4ml

* n a i ~ PERGAMON

Computers & Industrial Engineering 37 (1999) 63-67

Scheduling a Manufacturing Plant Using Simulated Annealing and Simulation* A. P. R e y n o l d s a n d G. P. M c K e o w n School of Information Systems U E A N o r w i c h , N R 4 7TJ

Abstract A technique for scheduling a class of manufacturing plants is described. The technique uses a simulated annealing module to create partial schedules, which are then completed and evaluated by a simulation module. The simulation module is equipped with a number of rules which it uses to complete schedules. A mathematical specification is given defining the type of scheduling problem with which we have been concerned. The derivation of a mixed integer linear programming model from this specification is discussed. The complexity of such a model for practical instances justifies the use of heuristic approaches. Results from using our approach on a case study derived from a real-world problem are presented. © 1999 E l s e v i e r S c i e n c e Ltd. A l l r i g h t s r e s e r v e d . Keywords scheduling, simulated annealing, simulation, manufacturing plant. 1 Introduction In recent years, a number of researchers (Glover et al. 1996, Feo et al. 1996) have investigated the use of methods based on the integration of simulation and modem heuristic techniques, such as simulated annealing (SA) and tabu search, for solving optimization problems. Typically, such an approach uses SA or tabu search to guide the simulation. In effect, the simulation module evaluates the solutions generated by the heuristic. In this paper, we consider a generalization of this approach whereby the modem heuristic technique, in our case SA, does not generate complete solutions which are then simply evaluated using simulation. Instead, a partial solution is generated representing a subspaee of possible solutions rather than a single solution. The simulation module is equipped with a number of problem-specific rules through which it seeks to generate a complete solution during the simulation process. An immediate advantage of this more flexible approach is that we avoid the generation of large numbers of infeasible solutions. We note that a method based purely on simulation is, of course, an extreme instance of our general method. In this paper, we report on our experiences of using such a method for solving scheduling problems arising from real-world manufacturing plants. In the next section, we describe the type of plant scheduling problem with which we are concerned and discuss the difficulty of using a mathematical programming approach. Details of our method are then presented in section 3. Results from applying this approach to a case study based on a real-world problem are presented in section 4.

2 Plant Scheduling Problems Short term scheduling of a manufacturing plant involves determining how to operate the plant in order to meet the demands placed on it. The type of plant with which we are concerned is one which processes fluid products and contains a number of stages. Typically, a storage facility separates each successive pair of processing facilities. A storage facility may consist of a number of units, each of which can only contain one type of product at a time, or it may be a flexible facility which can contain any combination of products from the preceding processing stage at the same time. Both types of storage facility may occur in the same plant. In this paper, we illustrate the ideas of our method by considering one type of 3-stage plant (see figure 1). We assume that processors in the first section of such a plant use various raw materials to make a set of base products, B. These base products are used in the subsequent processing stage to produce a set offinalproducts, F. We refer to processors that make base products as making units. Processors in the set, M, of making units are connected in a plant-dependent way to a set of storage units, S. Units in S are themselves connected, again in a plant-dependent way, to another set of processors, P, where a variety of final products is produced. Processing units in both processing stages may produce only one type of product at a time. 0360-8352/99 - see front matter © 1999 Elsevier Science Ltd. All rights reserved. PII: S0360-8352(99)00024-8

64

Proceedings of the 24th International Conference on Computers and Industrial Engineering

Each processor ra E M (p E P) may be able to produce only a subset of the possible base (final) products. Although different processors in M (P) may be able to produce the same base (final) product, they may do so at different rates. *This research was sponsored by Unilever Research, Port Sunlight Laboratory.

Processing

Storage

Processing

Figure 1: An Example of the Layout of a 3-stage plant

It is assumed that each storage unit can contain only one type of base product at a time. For a given a product, any machine that can process that product has a maximum rate at which it can do so. Also, there are change-over times for switching between products for both processors and storage units. If T denotes the makespan for a schedule, i.e. the time taken for all jobs to be completed, the objective of the plant scheduling process is to minimize the makespan, T, over all feasible schedules. To gain insight into the practical difficulty of solving plant scheduling problems, we briefly present a mathematical model for the problem of scheduling a simple 3-stage plant, and discuss how a mixed integer-linear program could be derived from our model. All processing units are assumed to operate continuously. Plant-dependent data parameters are summarised in figure 2. All of these parameters are assumed to be non-negative real numbers apart from Fm1 and Fs2, which are non-negative integers, and 13y, which identifies a base product. Our plant scheduling problem is then to determine each of the time-dependent functions listed in figure 3 subject to the constraints given in figure 4.

Mbrn

L~

L~p

F:

s$

Pf~ C~b/ra

c~,f'p fs

Maximum rate at which m 6 M can make b 6 B. Maximum possible rate of flow of b 6 B from ra 6 M to s 6 S. Maximum number of storage units that may be fed simultaneously by m E M. Maximum number of making units that can simultaneously feed s 6 S. Maximum amount of b 6 B that can be stored in s 6 S. Maximum possible rate of flow of b 6 B from s 6 S to p E P. Maximum number of final processors that may be fed simultaneously by s 6 S. Maximum number of storage units that can simultaneously feed p 6 P. Maximum possible rate at which f 6 F can be produced by p 6 P. Change-over time required to switch ra 6 M from making b 6 B to making b' 6 B. Change-over time required to switch s 6 S from storing b 6 B to storing b' 6 B. Change-over time required to switch p 6 P from producing f 6 F to producing f ' E F. The base product from which final product f 6 F is made. The fraction of f E F made up of its base product Figure 2: Plant-dependent Data

These constraints hold for all b, b' 6 B, m 6 M, s 6 S, p E P, f, f ' E F and for all t, t' > 0, as appropriate. Constraints (1)-(3) and (7), (8) are capacity constraints. Constraints (4)-(6) ensure that only one product is being processed (or stored) by any given unit at any given time. (9)-(11) are conservation constraints; in (10), S'bs(t) denotes

Proceedings of the 24th International Conference on Computers and Industrial Engineering

65

the rate at which the amount of b stored in s • S at time t is changing. Constraints (12)-(15) specify that the maximum numbers of simultaneous connections between successive stages of the plant must not be exceeded, while (16)-(18) are change-over constraints. Constraints (19) ensure that the demands, dr, for final products, f E F, are met. The

robin(t) Rate at which rn • M makes b • B at time t. l~,,n,(t) Rate of ttow ofb £ Bfrorom • M t o s • S at time t. Sbs(t) Amount of b • B storedin s • Sat time t. l'~,p(t) R a t e o f f l o w o f b • B f r o m s • S t o p • P a t t i m e t . ply(t) Rate at which f • F is produced by p • P at time t. Figure 3: Parameters to be Determined objective is to minimize the makespan, T, over all feasible schedules.

mb,n(t) ~_ Mbm

(1)

s~,(t) < sb,

(2)

psp(t) _

(3) (4)

Sbs(t) > 0 and b' # b :~ Sb,s(t) = 0 ply(t) > 0 and f' # f =~ pf,p(t) = 0

(5) (6)

t~,n,(t) £ L~,~,

(7)

t~,p(t) _ L~.~

(8)

E , ~ s l~m,(t) = rrts,~(t)

(9)

sls(t) = EmeM l~ms(t) - EpeP 12sbp(t) ff'PYv(t) = E s e s l~ssp(t) # { s • S : l~,~,(t) > O,b • B} <_F~ # { m • M : l~,~,(t) > 0,b • B} < f~ #{p • P : l~,v(t) > O,b • B} < F~ #{s • S : l~,p(t) > O,b ~ B} < f~ (mbm(t)>Oandmb,,~(t')>Oandt'>t)=~t'>_t+c~b,,~

(10) (11) (12) (13) (14) (15) (16)

(st, s(t) > 0 and Sb, s(t t) > 0 and t' > t) =:~ t' >_ t -4- c~b, s

(17)

(pip(t) > 0 and py,p(t') > 0 and t' > t) =~ t' > t + c~l, p.

(18)

Ep~p foTPlv(t) dt ~_ dl

(19)

Figure 4: Constraints for a Plant Scheduling Problem.

A related mixed integer-linear programming (MIP) model may be derived from the above specification by first discretizing time by defining T = { 1, 2 , . . . , t~, }, where t~, is an upper bound on the time of any practical schedule for the given plant. Continuous variables m~,n, Obs, ot Ffp, at tbms l u and lbs 2tp may then be defined in the obvious way. In addition, however, we introduce the following sets of 0-1 variables: X~,~, Yb~s, Z~s and W~v. X~,~ is 1 if b E B is produced by ra E M at time t, and 0 otherwise. Y~m~ is 1 if b E B is flowing between m E M and s E S at time t, and 0 otherwise. Z~s is 1 if b E B is stored in s E S at time t, and 0 otherwise. Finally, W~p is 1 if p E P is producing f E F at time t, and 0 otherwise. Using these variables it is now easy to derive a MIP model from our original specification. We omit the details but note that for practical problem instances the number of 0-1 variables will typically be very large. For example, if tu is 100 hours then, even with a time unit as large as 15 minutes, the number of 0-1 variables

66

Proceedings of the 24th International Conference on Computers and Industrial Engineering

will be 400(IB [IMllsl + IBIIMI + IBIISI + tFIIPI). Solving plant scheduling problems using integer programming techniques is thus far from trivial. This justifies the search for alternative approaches such as the one described in this paper.

3 A Method for Solving Plant Scheduling Problems Our method uses an SA module to generate partial schedules which are completed and evaluated using a simulation module. We refer to the partial schedules output by the SA module as SA schedules. One simple way in which an SA schedule might not be complete is that schedule data for one or more of the stages in a multi-stage plant are not specified by the SA schedule. For example, in a 3-stage plant, we have found it preferable to leave the scheduling of the storage section to the simulation module. There are three components to an SA schedule relating to job allocation, job ordering and job idle-times. The job allocation component specifes which machine(s) in the plant should perform each job and, if more than one machine is involved for a particular job, how that job should be split between these machines. It is represented by a set of numbers in [0, 1] for each product giving the fractions of the product assigned to the various machines. The job ordering component of an SA schedule specifies, for each machine, the order in which the jobs allocated to that machine should be performed. This is represented as a permutation of the jobs that might be done by that machine. Finally, the job idle-times component specifies lower bounds for the amounts of idle-time between jobs on a scheduled machine; this is represented by a list of non-negative,real numbers. Actual idle-times are determined by the simulation module subject to these lower bounds. Given the structure of an SA schedule, three neighbourhood operators are immediately apparent: changing job fractions, altering the job ordering and modifying idle-time lower bounds. At each iteration of the SA module, one of these three possible operators is chosen. The simulation module in our algorithm takes an SA schedule and performs a discrete event simulation to evaluate a completion of the SA schedule. Typical events in the simulation are: end-of-idle-time, end-of-change-over, endof-job-processing, storage-unit-out-of-productand storage-unit-full. The simulation module uses a variety of rules to complete the given partial schedule. For example, suppose that in the given SA schedule, a processor, m, has been assigned to produce some of a product, b, which must then be stored. If the SA schedule does not specify how the storage units are to be used, then the simulation module must use a rule to determine which storage unit should be fed b by m. In order to ensure that SA schedules are not completed in an infeasible manner, additional constraints may need to be constructed. Since these constraints must then be checked many times during each simulation, it is important to avoid including redundant constraints. For example, redundant constraints may arise whenever two non-consecutive stages in a plant are specified by the SA schedule but the intermediate stage(s) are not specified by the SA schedule.

4

Results In this section we illustrate the use of our method by presenting some results for a case study based on a real-world 3-stage manufacturing plant. For this example, IM[ = 2, IS[ = [P{ = 5, [B[ = 10 and IF[ = 28. The plant is fullyconnected, i.e. each rn E M is connected to each s E S and each s E S is connected to each p E P. Schedules with a makespan of 120 hours or less are regarded as satisfactory solutions for this problem. Our results are summarised in table 1. In practice, near-optimal solutions may be satisfactory. Indeed, a near-optimal solution may be preferred in practice to an optimal solution due to factors not incorporated into the model. From our experiments, an advantage of our approach is that it tends to generate a number of significantly different near-optimal solutions. This is important in a practical context since it increases the number of options available to management. The SA module used a random initial solution; a geometric cooling schedule with a multiplicative factor of 0.99 was used and the temperature was updated every 20 iterations..

Proceedings of the 24th International Conference on Computers and Industrial Engineering Best Solution (Hours) 113.75 113.75 113.75 113.75 129.79 113.75 113.75 113.75 113.75 113.75 113.75 113.75 113.75 113.75 113.75

Time to find solution under 120 hours (CPU sees) 86 46 57 15

67

Time to find optimum (CPU sees) 89 48 61 33

2 117 86 34 17 64 12 15 53 1

47 130 90 36 36 71 22 44 65 7

Table 1: Results for the case study

References Feo, T. A., Bard, J. F., & Holland, S. D. (1996). A GRASP for Scheduling Printed Wiring Board Assembly. liE Transactions, 28, pp. 155--65. Glover, E, Kelly, J. P., & Laguna, M. (1996). New Advances and Applications of Combining Simulation and Optimization. Technical report, Graduate School of Business, University of Colorado, Boulder, Colorado 803090419, USA.