Stochastic design optimization of asynchronous flexible assembly systems. (English) Zbl 0711.90031
Summary: This paper presents the application of the stochastic quasigradient method (SQG) of Y. M. Ermoliev and A. Gaivoronski [“Stochastic quasigradient methods and their implementation”, Working Paper WP-84-55, IIASA, Laxenburg/Austria (1984)] to the performance optimization of asynchronous flexible assembly systems (AFAS). These systems are subject to blocking and starvation effects that make complete analytic performance modeling difficult. A hybrid algorithm is presented in this paper which uses a queueing network model to set the number of pallets in the system and then an SQG algorithm is used to set the buffer spacings to obtain optimal system throughput. Different forms of the SQG algorithm are examined and the specification of optimal buffer sizes and pallet numbers for a variety of assembly systems with ten stations are discussed. The combined Network-SQG method appears to perform well in obtaining a near optimal solution in this discrete optimization example, even though the SQG method was primarily designed for application to differentiable performance functionals. While a number of both theoretical and practical problems remain to be resolved, a heuristic version of the SQG method appears to be a reasonable technique for analyzing optimization problems for certain complex manufacturing systems.
MSC:
| 90B30 | Production models |
| 90C15 | Stochastic programming |
| 90-08 | Computational methods for problems pertaining to operations research and mathematical programming |
| 60K20 | Applications of Markov renewal processes (reliability, queueing networks, etc.) |
| 90B10 | Deterministic network models in operations research |
| 90B22 | Queues and service in operations research |
| 90C90 | Applications of mathematical programming |
Keywords:
stochastic quasigradient method; performance optimization; asynchronous flexible assembly systems; blocking; starvation effects; hybrid algorithm; queueing network; optimal buffer sizes; near optimal solutionReferences:
| [1] | D.R. Anderson and D.C. Moodie, Optimal buffer storage capacity in production lines, Int. J. Prod. Res. 7(1969)233. · doi:10.1080/00207546808929813 |
| [2] | K. Barten, A queueing simulator for determining optimum inventory levels in a sequential process, J. Ind. Eng. 13(1962)247. |
| [3] | J.R. Blum, Multidimensional stochastic approximation methods, Ann. Math. Statist. 25(1954)737. · Zbl 0056.38305 · doi:10.1214/aoms/1177728659 |
| [4] | G. Boothroyd, Poli, Corrado and L.E. Murch,Automatic Assembly (Marcel Dekker, N.Y. 1982). |
| [5] | J.A. Buzacott, Automatic transfer lines with buffer stocks, Int. J. Prod. Res. 5(1967)183. · doi:10.1080/00207546708929751 |
| [6] | J.A. Buzacott, The effect of station breakdowns and random processing times on the capacity of flow lines with in-process storage, AIIE Trans. 4(1972)308. |
| [7] | J.A. Buzacott and L.E. Hanifin, Models of automatic transfer lines with inventory banks – A review and comparison, AIIE Trans. 10(1978)197. |
| [8] | N. Captor, B. Miller, B.D. Ottinger, A.J. Riggs, L.M. Tomko and M.C. Culver, Adaptable-programmable assembly research technology transfer to industry, Final Report, NSF Grant ISP 78-18773 (1983). |
| [9] | A. Dvoretzky, On Stochastic Approximation, Proc. 3rd Berkeley Symp. on Mathematical Statistics and Probability, Vol. 1 (1956) pp. 39 55. · Zbl 0072.34701 |
| [10] | Y.M. Ermoliev and N.Z. Shor, Method of random search for two-stage problems of stochastic programming and its generalization, Cibernetika 1 (1968). |
| [11] | Y.M. Ermoliev, On the method of generalized stochastic gradients and quasi-Feyer sequences, Cibernetika 2 (1969). |
| [12] | Y.M. Ermoliev, Stochastic models and methods of optimization, Cibernetika 2 (1978). |
| [13] | Y.M. Ermoliev, Stochastic quasigradient methods and their application to system optimization, Stochastics 9(1983)1. · Zbl 0512.90079 |
| [14] | Y.M. Ermoliev and A. Gaivoronski, Stochastic quasigradient methods and their implementation, Working Paper WP-84-55, IIASA, Laxenburg, Austria (1984). |
| [15] | M.C. Freeman, The effects of breakdowns and interstage storage on production line capacity, J. Ind. Eng. 15(1964)194. |
| [16] | S.B. Gershwin and O. Berman, Analysis of transfer lines consisting of two unreliable machines with random processing times and a finite storage buffer, AIIE Trans. 13(1981)1. |
| [17] | S.B. Gershwin, An efficient decomposition method for the approximate evaluation of production lines with finite storage space, Report LIDS-P-1308, Laboratory for Information and Decision Systems, M.I.T. (1983). · Zbl 0551.90026 |
| [18] | P.W. Glynn, Optimization of stochastic systems, Proc. 1986 Winter Simulation Conference, to appear. · Zbl 0873.76069 |
| [19] | P.W. Glynn and J.L. Sanders, Monte Carlo optimization of stochastic systems: Two new approaches, Proc. 1986 ASME Comp. in Eng. Conf. (1986). |
| [20] | M. Groover, M. Weiss, R. Nagel and N. Odrey,Industrial Robots-Technology, Programming and Applications (McGraw Hill, New York, 1986). |
| [21] | A.M. Gupal and V.P. Norkin, Method of discontinuous optimization, Cibernetika 2 (1977). · Zbl 0349.90109 |
| [22] | J.M. Hatcher, The effect of internal storage on the production rate of a series of stages having exponential service times, AIIE Trans. 1(1969)150. |
| [23] | Y.C. Ho, M.A. Eyler and T.T. Chien, A gradient technique for general buffer storage design in production line, Proc. 1978 IEEE Conf. on Decision and Control, San Diego (1979). · Zbl 0427.90047 |
| [24] | Y.C. Ho, M.A. Eyler and T.T. Chien, A new approach to determine parameter sensitivities of transfer lines, Mgmt. Sci. 29, 6(1983)700. · doi:10.1287/mnsc.29.6.700 |
| [25] | Y.C. Ho and X. Cao, Perturbation analysis and optimization of queueing networks, J. Optim. Theory Appl. 40, 4(1983). · Zbl 0496.90034 |
| [26] | G.C. Hunt, Sequential arrays of waiting lines, Oper. Res. 4(1956)674. · Zbl 0073.01602 · doi:10.1287/opre.4.6.674 |
| [27] | J.R. Jackson, Jobshop-like queueing systems, Mgmt. Sci. 10, 1(1963)131. · doi:10.1287/mnsc.10.1.131 |
| [28] | M. Kamath, R. Suri and J.L. Sanders, Analytical performance models for closed loop flexible assembly systems, Int. J. Flexible Manufacturing Systems 1, 1(1988), to appear. |
| [29] | M. Kamath and J.L. Sanders, Analysis of large asynchronous automatic assembly systems, Journal of Large Scale Systems (1987). · Zbl 0709.90557 |
| [30] | E. Kay, Buffer stocks in automatic transfer lines, Int. J. Prod. Res. 10(1972)155. · doi:10.1080/00207547208929916 |
| [31] | J. Kiefer and J. Wolfowitz, Stochastic estimation of the maximum of a regression function, Ann. Math. Stat. (1952) 462. · Zbl 0049.36601 |
| [32] | A.D. Knott, The effect of internal storage on the production rate of a series of stages having exponential service times, AIIE Trans. 2(1970)273. |
| [33] | E. Koenigsberg, Twenty-five years of cyclic queues and closed queueing networks: A review, J. Oper. Res. Soc. 33(1982)605. · Zbl 0484.90041 |
| [34] | C.M. Liu and J.L. Sanders, Stochastic optimization of flexible assembly systems, Proc. 2nd ORSA/TIMS Conf. on FMS (1986). |
| [35] | J.A. Masso and M.L. Smith, Interstage storage for three-stage lines subject to stochastic failures, AIIE Trans. 6(1974)354. |
| [36] | E.A. Nurmenski, Quasigradient method for solving nonlinear programming problems, Cibernetika 1 (1973). |
| [37] | K. Okamura and H. Yamashina, Analysis of effect of buffer storage capacity in transfer line systems, AIIE Trans. 9(1977)127. |
| [38] | K. Okamura and H. Yamashina, Analysis of in-process buffers for multi-stage transfer line systems, Int. J. Prod. Res. 21(1983)183. · doi:10.1080/00207548308942346 |
| [39] | B. Pittel, Closed exponential networks of queues with blocking, IBM Research Report No. 26548, Yorktown Heights, New York (1976). |
| [40] | B.T. Polyak, Convergence and convergence rate of iterative stochastic algorithms in general case, Automation and Remote Control 12 (1976). |
| [41] | N.P. Rao, Two-stage production systems with intermediate storage, AIIE Trans. 7(1975)414. |
| [42] | H. Robbins and S. Monro, A stochastic approximation method, Ann. Math. Stat. (1951)400. · Zbl 0054.05901 |
| [43] | T.J. Shenskin, Allocation of interstage along an automatic production line, AIIE Trans. 8(1976)146. |
| [44] | A.L. Soyster, J.W. Schmidt and M.W. Rohrer, Allocation of buffer capacities for a class of fixed cycle production lines, AIIE Trans. 11(1979)2. |
| [45] | R. Suri and X. Cao, The phantom customer and marked customer methods for optimization of closed queueing networks with blocking and general service times, ACM Performance Evaluation Review 12(19)243. |
| [46] | R. Suri and G.W. Diehl, A variable buffer-size model and its use in analyzing closed queueing networks with blocking, Mgmt. Sci. 32, 2(1983)206. · Zbl 0587.60091 |
| [47] | W. Whitt, Approximations to departure processes and queues in series, Naval Res. Logist. Quart. 31(1984)499. · Zbl 0563.60094 · doi:10.1002/nav.3800310402 |
| [48] | D.D. Yao and J.A. Buzacott, Queueing models for a flexible machining station, Part I: The diffusion approximation, Eur. J. Prod. Res. 19(1985)233. · Zbl 0553.90049 |
| [49] | R. Suri and Y.T. Leung, Single run optimization of a Siman model for closed loop flexible assembly systems, Proc. 1987 Winter Simulation Conf. (1987). |
| [50] | C.G. Cassandras and S.G. Strickland, An augument chain approach for on-line sensitivity analysis of Markov processes, Proc. 26th IEEE Conf. on Decision and Control (1987). |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
