Zastosowanie technik programowania z ograniczeniami do rozstrzygania konfliktów zasobowych w ESP

• Autorzy: Wójcik R. , Bocewicz G. , Banaszak Z.

Warianty tytułu

EN

CP - based approach to FMS's resource conflicts resolution

• Języki publikacji: PL

Abstrakty

PL

Przedmiotem badań są mechanizmy synchronizacji pracy wózków samojezdnych w elastycznych systemach produkcyjnych, mechanizmy warunkujące koordynację współbieżnie przebiegających procesów transportowych. Problem wyznaczania zasad koordynujących dostęp wózków do współdzielonych zasobów systemu (odcinków tras jezdnych) gwarantujących bezkolizyjny i bezblokadowy przebieg realizowanych procesów należy do klasy NP-trudnych. Problem ten sprowadza się do wyznaczania warunków wystarczających postaci pary (stan początkowy, zbiór reguł priorytetowania). Przyjęty regułowy sposób specyfikacji podsystemu transportowego, sprowadza go z kolei do odpowiedniego problemu decyzyjnego metody logiczno-algebraicznej. W pracy przedstawiono koncepcję wykorzystania technik programowania w logice z ograniczeniami CP/CLP do rozwiązania takiego problemu decyzyjnego poprzez wcześniejsze sprowadzenie go do postaci problemu spełniania ograniczeń PSO. W oparciu o proponowane podejście zrealizowany został przykład wyznaczania warunków wystarczających dla spełnienia ograniczeń, które gwarantują bezkolizyjną i bezblokadową pracę w systemie obsługi wózków samojezdnych.

EN

The subject matter of study are the automated guided vehicle (AGV) operation synchronization mechanisms in flexible manufacturing systems, enabling determination of the travel schedules via some preset traveling route intervals. In many practical cases transport operations are repetitive. For this type of systems the transport processes can be modeled as a system of cyclic concurrent processes sharing common resources with mutual exclusion. The collision-free, starvation-free and deadlock-free systems of cyclic processes are also periodic. In this paper the problem of determination of the rules coordinating access of the vehicles to the shared travel route intervals, ensuring the collisionfree and deadlock-free execution of the repetitive processes was reduced to determination of the sufficient conditions of the form of a pair (initial state, a set of priority rules). For a give transport subsystem specification with use of the rules the system's operation schedule determination is considered as a relevant decisive problem of the logic-algebraic method. In particular the problem of looking for a pair is defined in the form of the constraint satisfaction problem (CSP) and is solved with use of the programming techniques in logic with constraints.

Słowa kluczowe

PL

programowanie w logice z ograniczeniami; transport międzystanowiskowy; elastyczny system produkcyjny

EN

flexible manufacturing system

• Wydawca: Wydawnictwo Wrocławskiej Rady FSNT NOT
• Czasopismo: Inżynieria Maszyn
• Rocznik: 2006
• Tom: R. 11, z. 1
• Strony: 87--99
• Opis fizyczny: Bibliogr. 12 poz.

Twórcy

autor

Wójcik R.

autor

Bocewicz G.

autor

Banaszak Z.

• Wyższa Szkoła Informatyki i Zarządzania „COPERNICUS” we Wrocławiu,

Bibliografia

• [1] BANASZAK Z., ZAREMBA M., MUSZYŃSKI W., CP-based decision making for SME. Preprints of the 16th IFAC World Congress, 3 - 8 July, 2005, Prague, Czech Republic, Eds P. Horacek, M. Simandl, P.Zitek, DVD
• [2] BARTÁK R., Incomplete Depth-First Search Techniques: A Short Survey, Proceedings of the 6th Workshop on Constraint Programming for Decision and Control, Ed. Figwer J., 2004, pp. 7-14.
• [3] BUBNICKI Z., Wstęp do systemów ekspertowych, PWN, Warszawa 1990.
• [4] BUBNICKI Z., Procesy uczenia i metoda logiczno-algebraiczna w systemach z reprezentacją wiedzy, Analiza systemowa i zarządzanie, Inst. Badań Systemowych PAN wydanie: I, 1999.
• [5] INRIA MaxPlus Working Group, MaxPlus toolbox for Scilab. Available in the Internet: http://www.maxplus.org, n.d.
• [6] LAWLEY M.A., REVELIOTIS S.A., FERREIRA P.M., A correct and scalable deadlock avoidance policy for flexible manufacturing systems. IEEE Trans. on Robotics and Automation, Vol.14, No.5, 1998, pp.796-809.
• [7] LEE T., SONG J., Petri net modeling and scheduling of periodic job shops with blocking. Proc. of the Workshop on Manufacturing and Petri nets, Osaka, Japan, 25 June, 1996, pp.197-214.
• [8] MAJDZIK P., POLAK M., WÓJCIK R., BANASZAK Z., Effective prototyping of concurrent processes systems with multiple dispatching rules, Proceedings of the CS&P 2005: workshop. Ruciane-Nida, Polska, 2005, Warsaw, 2005.
• [9] POLAK M., MAJDZIK P., BANASZAK Z.A., WÓJCIK R., The performance evaluation tool for automated prototyping of concurrent cyclic processes. Fundamenta Informaticae, Vol.60, No.1-4, 2004, pp.269-289.
• [10] RAMAMRITHAM K., Allocation and scheduling of precedence-related periodic tasks. IEEE Trans. On Parallel and Distributed Systems, No 6, Vol.4, 1995, pp.412-420.
• [11] ZAREMBA M.B., JEDRZEJEK K., BANASZAK Z.A., Design of Steady State Behaviour of Concurrent Repetitive Processes: An Algebraic Approach. IEEE Trans. on Systems, Man, and Cybernetics Vol.28, Part A, No.2, March 1998, pp. 199-212.
• [12] WÓJCIK R., BOCEWICZ G., BANASZAK Z., Harmonogramowanie pracy wózków samojezdnych w warunkach ograniczonego dostępu do współdzielonych zasobów ESW (Model logiczno-algebraiczny). Krajowa Konferencja Robotyki Wrocław 2006.