Kết hợp các Vấn đề Lộ Trình và Phân Bố Bộ Nhớ trong các Mạng Đợi Chuỗi-Điểm

Springer Science and Business Media LLC - Tập 125 - Trang 47-68 - 2004
Sophia Daskalaki1, J. MacGregor Smith2
1Department of Engineering Sciences, University of Patras, Rio Patras, Greece
2Department of Mechanical and Industrial Engineering, University of Massachusetts, Amherst, USA

Tóm tắt

Trong bối cảnh một mạng đợi chuỗi-điểm với các máy chủ song phân có công suất hữu hạn, một phương pháp thiết kế hệ thống được trình bày để ước lượng gần đúng các vấn đề tối ưu về lộ trình và phân bổ không gian bộ nhớ trong mạng. Vấn đề lập trình phi tuyến stochastics đa mục tiêu trong các biến nguyên được mô tả và một quy trình tối ưu hóa lặp hai giai đoạn được trình bày, quy trình này liên kết các vấn đề lộ trình và phân bổ không gian bộ nhớ. Quy trình thuật toán kết hợp phương pháp Mở rộng, một phương pháp phân tách để tính toán các chỉ số hiệu suất trong các mạng đợi có công suất hữu hạn, cùng với quy trình tối ưu hóa không ràng buộc của Powell, quy trình này phân bổ các bộ nhớ và một quy trình tìm kiếm đa biến để xác định xác suất lộ trình. Hiệu quả và hiệu suất của phương pháp thiết kế hai giai đoạn được kiểm tra và đánh giá thông qua một loạt các thiết kế thực nghiệm kết hợp với mô phỏng các cấu trúc mạng.

Từ khóa

#Mạng đợi #tối ưu hóa #lập trình phi tuyến #lộ trình #phân bổ bộ nhớ

Tài liệu tham khảo

Altiok, T. (1982). “Approximate Analysis of Exponential Tandem Queues with Blocking.” European Journal of Operations Research 11, 390–398. Altiok, T. and S. Stidham. (1983). “The Allocation of Interstage Buffer Capacities in Production Lines.” IIE Transactions 15(4), 292–299. Altiok, T. and H.G. Perros. (1986). “Open Networks of Queues with Blocking: Split and Merge Configurations.” AIIE Transactions, 251-261. Baccelli, F. and S. Foss. (1995). “On the Saturation Rule for the Stability of Queues.” J. Applied Probability 32, 494–507. Basnet C. and J.H. Mize. (1994). “Scheduling and Control of Flexible Manufacturing Systems: A Critical Review.” International J. of Computer Integrated Manufacturing 7(6), 340–355. Bertsekas D. and R. Gallagher. (1987). Data Networks. Englewood Cliffs, NJ: Prentice-Hall. Boxma, O. and A. Konheim. (1981). “Approximate Analysis of Exponential Queuing Systems with Blocking.” Acta Informatica 15, 19–26. Buzacott, J. (1967). “Automatic Transfer Lines with Buffer Stocks.” Int. J. of Prod. Research 5(3), 183–200. Buzacott, J. (1971). “The Role of Inventory Banks in Flow-Line Production Systems.” Int. J. of Prod. Research 9(4), 425–436. Buzacott, J. and J.G. Shanthikumar. (1993). Stochastic Models of Manufacturing Systems. Englewood Cliffs, NJ: Prentice-Hall. Buzacott, J., J.G. Shanthikumar, and D.D. Yao. (1994). “Jackson Network Models of Manufacturing Systems.” In D.D. Yao (ed.), Stochastic Modeling and Analysis of Manufacturing Systems. New York: Springer, pp. 1–45. Cassandras, C. (1984). “A Hierarchical Routing Control Scheme for MHS.” In Proceedings of ORSA/TIMS Conference on FMS. Ann Arbor, USA: Univ. of Michigan, pp. 397–402. Chankong and Y.Y. Haimes. (1983). Multiobjective Decision Making: Theory and Methodology. NewYork: North-Holland. Daskalaki, S. (1988). “Static and Real Time Routing in Open Finite Queueing Networks.” Ph.D. Dissertation, Department of Industrial Engineering and Operations Research, University of Massachusetts, Amherst, MA. Daskalaki, S. and J. MacGregor Smith. (1986). “The Static Routing Problem in Open Finite Queueing Networks.” Paper presented at the ORSA/TIMS Meeting, Miami, FL, October 1986. Daskalaki, S. and J. MacGregor Smith. (1989). “Real Time Routing in Finite Queueing Networks.” In H.G. Perros and T. Altiok (eds.), Queueing Networks with Blocking. Amsterdam: North-Holland, pp. 313–324. Enginarlar, E., J. Li, S.M. Meerkov, and R.Q. Zhang. (2002). “Buffer Capacity for Accomodating Machine Downtime in Serial Production Lines.” Int. J. of Prod. Research 40(3), 601–624. Gavish, B. (1982). “Topological Design of Centralized Computer Networks: Formulations and Algorithms.” Networks 12(4), 355–377. Gavish, B. (1983). “Formulations and Algorithms for the Capacitated Minimal Directed Tree Problem.” J. ACM 30(1), 118–132. Gavish, B. (1986). “A General Model for Topological Design of Computer Networks.” In Proceedings of GLOBECOM '86. Gavish, B. and I. Neuman. (1986). “Capacity and Flow Assignments in Large Computer Networks.” In Proceedings of IEEE-INFOCOM '86, pp. 275-284. Gershwin, S.B. (1984). “An Efficient Decomposition Method for the Approximate Evaluation of Production Lines with Finite Storage Spacer.” In Sixth INRIA Conference Proceedings. Nice, France. Gershwin, S.B. (1986). “Modelling and Analysis of Assembly/Disassembly Networks.” In IEEE Proceedings Systems, Man, and Cybernetics Conference, October 1986. Gershwin, S.B. (1987). “An Efficient Decomposition Method for the Approximate Evaluation of Tandem Queues with Finite Storage Space and Blocking.” Operations Research 35, 291–305. Gershwin, S.B. and J.E. Schor. (2000). “Efficient Algorithms for Buffer Space Allocation.” Annals of Operations Research 93, 117–144. Gosavi, H. and J. MacGregor Smith. (1995). “Asymptotic Bounds of Throughput in Open Finite Queueing Networks.” Computers and Operations Research 22(10), 1057–1073. Gosavi, H. and J. MacGregor Smith. (1997). “An Algorithm for Sub-Optimal Routing in Series Parallel Queueing Networks.” Int. J. of Prod. Research 35(5), 1413–1430. Hillier, F.S. and R.W. Boling. (1967). “Finite Queues in Series Exponential or Erlang Service Times-A Numerical Approach.” Operations Research 15, 286–303. Houck, D.J. (1987). “Comparison of Policies for Routing Customers to Parallel Queueing Systems.” Operations Research 35(2), 306–310. Huang M.G., P.L. Chang, and Y.C. Chou. (2002). “Buffer Allocation in Flow-Shop-Type Production Systems with General Arrival and Service Patterns.” Computers & Operations Research 29(2), 103–121. Kelly, F.P. (1990). “Routing and Capacity Allocation in Networks with Trunk Reservations.” Mathematics of Operations Research 15(4), 771–793. Kerbache, L. and J. MacGregor Smith. (1987). “Asymptotic Behavior of the Expansion Method for Open Finite Queueing Networks.” Computers and Operations Research 15(2), 157–169. Koenigsberg, E. (1959). “Production Lines and Internal Storage-A Review.” Management Science 5, 419–433. Landers, R.G., B.K. Min, and Y. Koren. (2001). “Reconfigurable Machine Tools.” Annals of CIRP 50(1), 269–274. MacGregor Smith, J. and S. Daskalaki. (1988). “Buffer Space Allocation in Automated Assembly Lines.” Operations Research 36(2), 343–358. MacGregor Smith, J., S.B. Gershwin, and C.T. Papadopoulos (eds.). (2000). Performance Evaluation and Optimization of Production Lines. Annals of Operations Research, Vol. 93. Baltzer Science Publishers. Neufeld, E.M. and C.J. Colbourn. (1985). “The Most Reliable Series-Parallel Networks.” Networks 15, 27–32. Papadopoulos, H.T. and M.I. Vidalis. (2001). “A Heuristic Algorithm for the Buffer Allocation in Unreliable Unbalanced Production Lines.” Computers & Industrial Engineering 41, 261–277. Perros, H.G. (1994). Queueing Networks with Blocking. New York: Oxford University Press. Pollock, S., J.R. Birge, and J.M. Alden. (1985). “Approximation Analysis for Open Tandem Queues with Blocking: Exponential and General Service Distribution.” Technical Report 85-30, Department of Industrial & Operations Engineering, University of Michigan, Ann Arbor, MI 48109. Powell, M.J.D. (1964). “An Efficient Method for Finding the Minimum of a Function of Several Variables without Calculating Derivatives.” Computer Journal 7, 155–162. Singh, A. and J. MacGregor Smith. (1997). “Buffer Allocation for an Integer Nonlinear Network Design Problem.” Computers & Operations Research 24(5), 453–472. Spicer, P., Y. Koren, M. Shpitalni, and D. Yip-Hoi. (2002). “Design Principles for Machining System Configurations,” Annals of the CIRP51(1). Spinellis, D., C. Papadopoulos, and J.M. Smith. (2000). “Large Production Line Optimization Using Simulated Annealing.” International Journal of Production Research38(3). Takahashi, Y., H. Miyahara, and T. Hasegawa. (1980). “An Approximation Method for Open Restricted Queueing Networks.” Operations Research 28(3), Part I, 594–602. Yao, D. (1984). “A FMS NetworkModel with State-Dependent Routing.” In Proceedings of the ORSA/TIMS Meeting on FMS. Ann Arbor, USA: Univ. of Michigan.