http://www.spinellis.gr/pubs/conf/1999-DSI-exPLOre/html/explore.html
This is an HTML rendering of a working paper draft that led to a publication. The publication should always be cited in preference to this draft using the following reference:

• Diomidis Spinellis and Chrissoleon T. Papadopoulos. ExPLOre: A modular architecture for production line optimisation. In Dimitris K. Despotis and Constantin Zopounidis, editors, Proceedings of the 5th International Conference of the Decision Sciences Institute, DSI '99, pages 1446–1449. Decision Sciences Institute, July 1999.

Citation(s): 5 (selected).

This document is also available in PDF format.

The document's metadata is available in BibTeX format.

Find the publication on Google Scholar

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Diomidis Spinellis Publications

EXPLORE: A MODULAR ARCHITECTURE FOR
PRODUCTION LINE OPTIMISATION

Diomidis Spinellis
University of the Aegean
Department of Information and Communication Systems
Samos, Greece
e-mail: dspin@aegean.gr

Chrissoleon T. Papadopoulos
University of the Aegean
Department of Business Administration
Chios, Greece
e-mail: hpap@aegean.gr

Abstract

The general design problem in serial production lines concerns the allocation of resources such as the number of servers, their service rates, and buffers given production-specific constraints, associated costs, and revenue projections. We describe the design of exPLOre: a modular, object-oriented production line optimization decision support system. An abstract optimization module can be instantiated using a variety of stochastic optimization methods such as simulated annealing and genetic algorithms. Its search space is constrained by a constraint checker while its search direction is guided by a cost analyser which combines the output of a throughput evaluator with the business model. The throughput evaluator can be instantiated using Markovian, generalised queueing network methods, or a decomposition algorithm.

1 Introduction

Serial production lines form the heart of many manufacturing systems. Their optimal design is subject to specific constraints, associated costs, and revenue projections. Much of the research in this field concerns the design of these manufacturing systems when there is considerable inherent variability in the processing times at the various stations, a common situation with human operators/assemblers. The general design problem in serial production lines is concerned with the allocation of resources such as the number of servers, their service rates, and buffers at each of the servers. These problems are called, respectively, the server allocation, the workload allocation, and the buffer allocation problems. The problem mentioned above is a nonlinear stochastic problem. One of its features which makes it very challenging to solve is that no known closed-form expression for estimating the throughputs of the lines exists. This characteristic makes it very difficult to control the design variables as a function of the variation in the objective function.

For a systematic classification of the relevant works on the stochastic modeling of these and other types of manufacturing systems (e.g., transfer lines, flexible manufacturing systems (FMS) and flexible assembly systems (FAS)), the interested reader is referred to a review paper by Papadopoulos and Heavey [13] and some recently published books, such as Askin and Standridge [2], Buzacott and Shanthikumar [3], Gershwin [7], Papadopoulos et al. [14], Viswanadham and Narahari [16], and Altiok [1].

The difficulties of the problem have led us into the deployment of an arsenal of different methods for determining the optimal design of the production line. These methods involve both the estimation of line throughput and the calculation of the optimal line design variables. In this paper we describe the design of exPLOre: a modular production line optimization decision support system. Up to now we have used the system for solving the buffer allocation problem in production lines with well over 100 stations in series [15], and for investigating the allocation buffers, servers, and service rates in production lines with up to 60 stations in series.

The rest of this paper is organised as follows: in section 2 we present the mathematical model of the production line, in section 3 we describe the exPLOre architecture, in section 4 we present the exPLOre prototype implementation and some initial results, while section 5 concludes the paper with a description of our future plans.

2 The Production Line Model

  The production line decision model we used is based on the optimal allocation of its constituent resources namely: the number of servers, their service rates, and buffers at each of the servers. The effect of the number of servers and the service rates on the production throughput and cost is obvious: an increased number of servers or service rate can be readily associated with a given cost and will increase the line throughput by a specific measure. The effect of the production line buffer allocation in terms of throughput and cost is more subtle. The main purpose of buffers in production or flow lines is to give each stage of a system some degree of independence from the rest of the system. If buffers were non-existent then the only way two connected workcenters could operate would be in perfect synchronization; an utopian situation. If there were no buffers between two workcenters at least one of two situations would occur: ``blocking'' of the first station or ``starving'' of the second station. Blocking of the first station occurs when the first station finishes processing its stock and releases it before the second station completes the material it is working on and the buffer of the second station is full. Starving occurs when the second station completes its work yet there are no parts in its buffer because the first workcenter is either busy or else has no work. In either of the situations the system throughput is below the expected.

One other situation for loss of capacity is the breakdown of a workcenter in the line. If there are no buffers all the stations of the system have to shut down either because of starving or blocking. If there are buffers between the stations the remaining stations can keep operating for some time. In allocating buffers the number of buffers is not only dependent upon the processing parameters of the production line but also upon the positions of stations within the line. Another feature of buffers is that buffers cease to be effective after some quantity. Beyond a threshold quantity of buffers the increase in the overall output of the line is overridden by the costs associated with buffers.

Although buffers are an essential part of any production line with finite capacities, there are costs associated with buffers. One of the important costs of buffers is the effect on flow time. Flow time is the time required to move a piece through the system process from entry to completion of the last stage. Customers accumulate indirect costs proportional to the time spent in the system. An increase results in high flow time to processing time ratios and thus reduced output. Another area of cost is the cost due to occupation of space. Larger quantities of buffers mean more space is occupied for waiting which otherwise could be used for processing equipment or faster movement of material handling equipment. Handling the unit into and out of the in-process inventory banks also adds to the costs.

From this description one can see that determining the quantity of buffers for each station in order to create perfect balance between the costs and benefits associated with buffers is a challenging task. Based on a given setting of the resources described above we can calculate two objective measures of the line's operation: the average throughput and the average work in progress (WIP). Taking into account the average revenue per item, its associated variable production cost and holding cost, and the costs of deploying the resources we described above we can obtain an objective measure of the line's economic performance.

Thus the production line under investigation can be modeled using the following basic objective function:

$maxZ=\; X\; (R-V)\; -\; h\; L\; -\; C$_B ∑_i=2^K B_i - ∑_i=1^K C_Sis_i - ∑_i=1^K C_Ri

where

• $X$ is the average throughput of the line,
• $R$ is the average revenue per item,
• $V$ is the average variable production cost,
• $h$ is the average holding cost per item,
• $L$ is the average total number of units in the production line at steady state (this is the average WIP),
• $B$_i is the buffer capacity allocated at buffer location $i$,
• $C$_Si is the cost of a server at location $i$,
• $s$_i is the number of servers per workstation $i$, and
• $C$_Ri is the cost of obtaining a given service rate at workstation location $i$.

3 The exPLOre Architecture

  The exPLOre architecture is used for building customized, flexible, and efficient production line optimization decision support systems. The modularity of the system allows the utilization of different evaluative function and optimization methods as well as the parametric expression of the production line constraints and the business model. This flexibility is needed so that the system's user can choose the appropriate algorithms for solving the problem at hand. The guiding tradeoffs between the different modules concern their relative efficiency, accuracy, and applicability. As an example it is possible to obtain an exact buffer configuration for a small production line using full enumeration and the decomposition method. On the other hand in order to obtain a buffer and server number allocation for a large production line one would choose simulated annealing as the optimization method because the full enumeration of all configurations would take a prohibitive long time to complete, and the expansion method as the evaluative function because the decomposition method does not deal with parallel servers.

 

Figure 1:

The exPLOre architecture is graphically depicted in Figure 1. The architecture's driver is an abstract optimization module. This can be instantiated using a variety of optimization methods such as simulated annealing, genetic algorithms, or even the exhaustive enumeration of the search space. The search space of the optimiser is constrained by the output of the constraint checker which, based on a production model expressed in a declarative domain-specific language, acts as an ``oracle'' determining the allowed line configurations. The search direction of the optimiser is guided by the cost analyser which combines the output of the throughput evaluator with variables from the business model to determine the objective merit of a given line configuration. The business model specifies the business benefit of a given line throughput as well as the business costs associated with the resources that are used to obtain that level of throughput. The abstract throughput evaluator can be instantiated using Markovian, generalised queueing network methods, or a decomposition algorithm.

4 Prototype Implementation

  In order to test the viability of the exPLOre architecture we have implemented a number of concrete modules for the optimizer and the throughput evaluator. Based on those modules we were able to obtain optimal production line configurations for both small and large production lines within acceptable execution time constraints. The modules we have implemented so far are the following:

Full Enumeration Optimizer

Determines the optimal line configuration by an exhaustive enumeration of all possible configurations. Viable only for small production lines, servers, and buffer space. Useful for cross-checking the results of other optimization methods. A variant of this optimizer uses a reduced enumeration procedure by skipping non-viable buffer allocation configurations.

Simulated Annealing Optimizer

Determines a near-optimal configuration using the simulated annealing [4,12] stochastic algorithm. Can handle large configurations in bounded execution time. Its search parameters may need expert problem-specific tuning.

Genetic Algorithm Optimizer

Determines a near-optimal configuration using genetic algorithms [8,10]. This optimizer can also handle large configurations in bounded execution time. It typically executes faster than the simulated annealing optimizer, producing however less optimal configurations.

Exact Evaluator

An exact numerical algorithm [9] is used in conjunction with a traditional Markovian state model. It provides an exact measure of the line throughput at the expense of prohibitively large execution times. Our implementation only handles lines with variable buffer allocations. Mostly useful for small lines with a limited number of buffers, or for verifying the operation of the other evaluators.

Decomposition Method Evaluator

A throughput evaluator based on the decomposition method [6,5]. Compared with the exact evaluator it provides an efficient and relatively accurate approximation of the line throughput. Our implementation can not handle parallel servers and variable service rates.

Expansion Method Evaluator

The Expansion Method is a robust and effective approximation technique developed by Kerbache and Smith [11]. This method is characterized as a combination of Repeated Trials and Node-by-node Decomposition solution procedures. In contrast to our decomposition method evaluator this evaluator can handle arbitrary line topologies with parallel server and variable service rates. Its evaluative accuracy and efficiency are however worse than the decomposition method evaluator.

Based on the above modules we obtained near-optimal line configurations for a number of different buffer, server, and service rate allocation problems for both large and small production lines. As a representative example in Figure 2 the computed throughput of simulated annealing is compared with complete enumerations using the exact and the decomposition evaluative methods for 9 station line configurations while Figure 3 illustrates the time needed to obtain different combinations of buffer (q) allocation, server allocation (w), and service rate allocation (s) using the simulated annealing optimizer in conjunction with the expansion method throughput evaluator.

 

Figure 2:

 

Figure 3:

5 Conclusions

  ExPLOre was built from the bottom up as a workbench for experimenting with production line optimization algorithms and methodologies. It currently provides a rich set of algorithms for evaluating production line configurations. The architecture's modularity and the plug-compatibility of the optimizer and throughput evaluator module instances has allowed us to concentrate our work on an objective comparison of the relative merits and deficiencies of the various algorithms. Placing methodologies which were up to now studied in isolation under the same roof has provided us in some cases with surprisingly differing results in terms of accuracy and efficiency for similar line configurations. Thus part of our new work entails the reexamination and tuning of the respective methods using exPLOre as an algorithm evaluation tool. In addition, the modularity of exPLOre has prompted us to examine further optimization and evaluation algorithms as candidates for inclusion. We are currently working on fine-tuning the exPLOre optimizer based on genetic algorithms. Finally, a further direction of our research concerns the publication of the exPLOre module port specifications and the provision of a friendly user-interface in order to create a publicly available version as a standard production line optimization algorithm workbench.

References

1

T. Altiok.
Performance Analysis of Manufacturing Systems.
Springer-Verlag, New York, 1997.

2

R. G. Askin and C. R. Standridge.
Modeling and Analysis of Manufacturing Systems.
John Wiley, New York, 1993.

3

J. A. Buzacott and J. G. Shanthikumar.
Stochastic Models of Manufacturing Systems.
Prentice Hall, New Jersey, 1993.

4

V. Cerny.
Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm.
Journal of Optimization Theory and Applications, 45:41-51, 1985.

5

Y. Dallery and Y. Frein.
On decomposition methods for tandem queueing networks with blocking.
Operations Research, 41(2):386-399, 1993.

6

S. B. Gershwin.
An efficient decomposition method for the approximate evaluation of tandem queues with finite storage space and blocking.
Operations Research, 35(2):291-305, 1987.

7

S. B. Gershwin.
Manufacturing Systems Engineering.
Prentice Hall, New Jersey, 1994.

8

David E. Goldberg.
Genetic Algorithms: In Search of Optimization & Machine Learning.
Addison-Wesley, 1989.

9

C. Heavey, H. T. Papadopoulos, and J. Browne.
The throughput rate of multistation unreliable production lines.
European Journal of Operational Research, 68:69-89, 1993.

10

Charles L. Karr.
Genetic algorithms for modelling, design, and process control.
In CIKM '93. Proceedings of the second international conference on Information and knowledge management, pages 233-238. ACM, 1993.

11

L. Kerbache and J. MacGregor Smith.
The generalized expansion method for open finite queueing networks.
The European Journal of Operations Research, 32:448-461, 1987.

12

P. J. M. Van Laarhoven and E. H. L. Aarts.
Simulated Annealing: Theory and Applications.
D. Reidel, Dordrecht, The Nethelands, 1987.

13

H. T. Papadopoulos and C. Heavey.
Queueing theory in manufacturing systems analysis and design: A classification of models for production and transfer lines.
European Journal of Operational Research, 92:1-27, 1996.

14

H. T. Papadopoulos, C. Heavey, and J. Browne.
Queueing Theory in Manufacturing Systems Analysis and Design.
Chapman and Hall, London, 1993.

15

Diomidis Spinellis and Chrissoleon T. Papadopoulos.
A simulated annealing approach for buffer allocation in reliable production lines.
Annals of Operations Research, 1999.
To appear.

16

N. Viswanadham and Y. Narahari.
Performance Modeling of Automated Manufacturing Systems.
Prentice Hall, New Jersey, 1992.