Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Phương pháp ngẫu nhiên cho tối ưu hóa rời rạc và liên tục trong hệ thống sản xuất
Tóm tắt
Các thuật toán cho tối ưu hóa rời rạc và liên tục là một phần rất quan trọng trong hệ thống ra quyết định trong sản xuất. Hầu hết các vấn đề lập kế hoạch, lập lịch và bố trí đều yêu cầu các thuật toán này. Trong thực tế, nghiên cứu về các thuật toán hiệu quả gặp phải hai trở ngại chính. Một là, rất thường xuyên, các tiêu chí không thể được biểu đạt dưới dạng phân tích, vì vậy không thể sử dụng các phương pháp giải quyết lý thuyết hiện có. Hai là, hầu hết các vấn đề mà các tiêu chí có thể được biểu diễn dưới dạng phân tích là các vấn đề NP-khó khăn. Tình huống này có thể được đơn giản hóa bằng cách sử dụng mô phỏng. Nhưng việc sử dụng mô phỏng và các phương pháp tối ưu hóa cùng nhau thường cho ra một cực tiểu cục bộ. Phương pháp được đề xuất trong bài viết này dựa trên việc sử dụng một sửa đổi rời rạc của biến đổi ψ kết hợp với một số phương pháp heuristics cho tối ưu hóa cục bộ. Sự độc đáo của phương pháp này là khả năng tránh cực tiểu cục bộ, trong khi sử dụng các mô hình mô phỏng để tính toán giá trị của các tiêu chí. Một ví dụ về việc sử dụng phương pháp này được đưa ra: nó liên quan đến việc tối ưu hóa việc khởi động các linh kiện trong sản xuất trong các hệ thống loại job-shop. Phương pháp đề xuất được so sánh với một phương pháp heuristics được biết đến là rất tốt trong cùng một số lần mô phỏng. Kết quả của năm thử nghiệm với kích thước mô hình khác nhau cho thấy hiệu quả của phương pháp đề xuất.
Từ khóa
#tối ưu hóa #hệ thống sản xuất #thuật toán #mô phỏng #NP-khó khăn #heuristics #cực tiểu cục bộTài liệu tham khảo
Balagin, W. Dolgui, A. Kowaltehuk, G., Miasnikov, S., Ofitserov, D., Revotuk, M. Smiznov, A. and Starich, V. (1988) Zur simulation flexibler fertigungssysteme. Automatisierung-stehnik, 1, 8–12.
Barnes, J. W. and Laguna, M. (1993) A taboo search experience in production scheduling. Annals of Operations Research, 41, 141–156.
Barnichon, D., Caux C., Fleury, G. and Kellert, P. (1992) Sim-ulated annealing and discrete event simulation for schedul-ing, in Proceedings of the European Simulation Multi-conference, 1-3 June, York, UK, 162–166.
Bensoussan, A., Crouhy, M. and Proth, J.-M. (1983) Mathemat-ical Techniques in Production Planning, North Holland Publishing.
Boender, C. G. E., Rinnooy Kan, A. H. G., Stougie, L. and Timmez, G. T. (1982) A stochastic method for global optimization. Mathematical Programming 22(2), 125–140.
Chichinadze, V. K. (1969) The ψ-transform for solving linear and non-linear programming problems. Automatica, 5(3), 347–355.
Chichinadze, V. K. (1983) Solving Nonlinear and Nonconvex Optimization Problems, Nauka, Moscow (in Russian).
Dell'Amico, M. and Trubian, M. (1993) Applying taboo search to the job-shop scheduling problem. Annals of Operations Re-search, 41, 231–252.
Dolgui, A., Portmann, M. C. and Proth, J. M. (1996) A control model for assembly manufacturing systems, in Proceedings 17th IFIP TC7 Conference on Systems Modeling and Opti-mization, Prague, 10-14, July, 1995 Dolezal, J. and Fidler, J. (eds), Chapman & Hall, London, pp. 519–526.
Garey, M. R. and Johnson, D. S. (1979) Computers and Intrac-tability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, CA.
German, O. and Ofitserov, D. (1995) Problem Solving: Methods, Programming and Future Concepts, Elsevier, Amsterdam.
Kiran, A. S. and Smith, M. L. (1984a) Simulation studies in job shop scheduling-I: a survey. Computer and Industrial Engineering, 8, 87–93.
Kiran, A. S. and Smith, M. L. (1984b) Simulation studies in job shop scheduling-II: performance of priority rules. Computer and Industrial Engineering, 8, 95–105.
Kolen, A. W. J., Rinnooy Kan, A. H. G., Van Hoesel, C. P. M. and Wagelmans, A. P. M. (1994b) Sensitivity analysis of list scheduling heuristics. Discrete Applied Mathematics, 55(2), 145–162.
van Laarhoven, P. J. M., Aarts, E. H. L. and Lenstra, J. K. (1992) Job shop scheduling by simulated annealing. Operations Research, 40, 113–125.
Nemhauser, G. L., Rinnooy Kan, A. H. G. and Todd, M. J. (eds) (1994) Handbook in operations Research and Management Science 1: Optimization, North Holland.
Ofitserov, D. and Dolgui, A. (1996) Optimization of manufac-turing systems behavior, in Proceedings of the IMACS/IEEE Multiconference on Computational Engineering in Systems Applications, CESA'96, pp. 641–647.
Ofitserov, D. and Tanaev, V. S. (1988) Computer-aided produc-tion planning in the integrated control system of an auto-matic factory, in Algorithms Production Control and Scheduling, vol.1, Karlovy Vary, 131–136.
Proth, J. M. and Sauer, N. (1996) Sensibility analysis for job-shop scheduling, in Proceedings of the IMACS/IEEE Multicon-ference on Computational Engineering in Systems Applica-tions, CESA'96, pp. 208–211.
Schoen, F. (1991) Stochastic techniques for global optimization: a survey of recent advances. Journal of Global Optimization, 1, 207–228.
Siary P. (1994) La méthode du recuit simulé: théorie et applica-tions, Ordonnancement et entreprise: applications concreètes et outils pour le futur, LAAS-CNRS, pp. 47–67.
Silver, E. A. and Peterson, R. (1987) Decision Systems for Inven-tory Management and Production Planning, John Wiley and Sons.
Sysoev, V. (1993) Algorithms and Models for CAD/CAM in Electronics Industry, Voronezh, Russia (in Russian).
Tanaev, V. S., Gordon, V. S. and Shafransky, Y. M. (1994) Scheduling Theory. Single-Stage Systems, Kluwer Academic Publishers.
Tanaev, V. S., Sotskov, Y. N. and Strusevitch, V. A. (1994) Scheduling Theory. Multi-Stage Systems, Kluwer Academic Publishers.
Taha, X. A. (1982) Operations Research: an Introduction, Mac-Millan Publishing Co.
Torn, A. and Zilinskas, A. (1989) Global Optimization, Springer-Verlag.