Subasta combinatoria para la programación dinámica en sistemas de fabricación distribuidos

  1. José Alberto Araúzo 1
  2. Ricardo del Olmo 2
  3. Juan José Laviós 2
  1. 1 Departamento de Organización de Empresas y CIM. Escuela de Ingenierías Industriales. Universidad de Valladolid
  2. 2 Departamento de Ingeniería Civil. Escuela Politécnica Superior. Universidad de Burgos
Revista:
Dirección y organización: Revista de dirección, organización y administración de empresas

ISSN: 1132-175X

Año de publicación: 2013

Número: 51

Páginas: 55-64

Tipo: Artículo

DOI: 10.37610/DYO.V0I51.438 DIALNET GOOGLE SCHOLAR lock_openAcceso abierto editor

Otras publicaciones en: Dirección y organización: Revista de dirección, organización y administración de empresas

Resumen

The traditional static scheduling methods, based on hierarchical and centralized architectures, are not flexible enough to self-adapt to the dynamism and complexity of today’s manufacturing systems. For this reason, new proposals to improve the scheduling and control of agile manufacturing systems constantly appear. The auction based allocation methods as well as the software paradigm of multiagent systems, which offers new techniques to face complex unsolved problems, can help to find promising solutions in manufacturing systems. Traditionally, scheduling problems have been solved offline by a centralized decision-maker that use a global optimisation model. We propose to include in the system several decision-makers modelled as agents instead. We consider two kinds of agents: order agents and machines agents. Each order agent represents a product that is characterized by its operations, precedence relationships and due date. The goal of each order agent is to find machines that can perform the required operations and hence completing successfully the order. Each production order creates its own schedule (local schedule). An auction mechanism ensures that local schedules are nearly compatible (several orders don’t use the same machine at the same moment) and globally efficient. Every agent in the system can communicate with other agents through the exchange of messages. The interaction mechanism is ruled by means of a combinatorial auction where a theoretical basis is provided for structuring message sequencing, bid evaluation, and price updating. Our research contributes to the auction technique in manufacturing scheduling and control in two basic aspects: (1) we apply the auction mechanism for a routing flexible environment (an operation can be performed in several machines with a differing efficiency), (2) we propose an implementation that can schedule online, updating real-time information: planning horizon, changes in orders, changes in machine availability and capabilities. We include explicitly the option of reallocate resources in real time when a new order arrives to the system. In order to test the features of this approach we display some computational results. Preliminary results show efficient performance in dynamic scenarios, but there are still many matters to investigate. Future works will be devoted to test the proposed approach on more case studies or even on real cases. We can add complexity to the structure of the system, and we must improve some aspects of the auction mechanism such as convergence and stability.

Referencias bibliográficas

  • ARAÚZO, J.A., DE BENITO, J.J, y DEL OLMO, R. (2003). «El control de planta: una aproximación basada en agentes». Actas del V Congreso de Ingeniería de Organización.
  • ARAÚZO, J.A., PAJARES, J., LÓPEZ-PAREDES, A. y PAVÓN, J. (2009). «Agent-based modeling and simulation of multi-project scheduling». Proceedings of the Multi-Agent Logics, Languages, and Organizations Federated Workshops (MALLOW 2009).
  • BABICEANU, R.F., CHEN, F.F., STURGES R.H. (2004). «Framework for the control of automated material handling systems using the holonic manufacturing approach». International Journal of Production Research, 42(17), pp. 3551-3564.
  • BAPTISTE, P., FLAMINI, M. y SOURD, F. (2008). «Lagrangian bounds for just-in-time job-shop scheduling». Computers and Operations Research, 35(3), pp. 906-915.
  • CRAMTON, P., SHOHAM, Y. y STEINBERG, R. (2006). Combinatorial auctions. Cambridge: MIT Press.
  • GIFFER, B. y THOMPSON, G. L. (1960). «Algorithms for solving production-scheduling problems». Operations Research, 8(4), pp. 487-503.
  • HOITOMT, D.J., LUH, P.B. y PATTIPATI, K.R., (1993). «A practical approach to job-shop scheduling problems». IEEE Transactions on Robotics and Automation, 9(1), pp. 1-13.
  • HSIEH, F.S. (2008). «Holarchy formation and optimization in holonic manufacturing systems with contract net». Automatica, 44(4), pp. 959-970.
  • JEONG, I. y YIM, S.B. (2009). «A job shop distributed scheduling based on Lagrangian relaxation to minimise total completion time». International Journal of Production Research, 47(24), pp. 6783-6805.
  • KISHORE, R., ZHANG, H. y RAMESH, R. (2006). «Enterprise integration using the agent paradigm: foundations of multi-agent-based integrative business information systems». Decision Support Systems, 42, pp. 48-78.
  • KRISHNA, V. (2009). Auction theory (2 ed.). San Diego: Academic Press.
  • LEE, Y.H., KUMARA, S.R.T. y CHATTERJEE, K. (2003). «Mul- tiagent based dynamic resource scheduling for distributed multiple projects using a market mechanism». Journal of Intelligent Manufacturing, 14(5), pp. 471-484.
  • LEITÃO, P., RESTIVO, F., (2008). «A holonic approach to dynamic manufacturing scheduling». Robotics and Computer-Integrated Manufacturing, 24(5), pp. 625-634.
  • LIU C.Y. (2000) «Scheduling flexible flow shops with sequence-dependent setup effects». IEEE Transactions on Robotics and Automation, 16(4), pp. 408- 419.
  • LIU, N., ABDELRAHMAN, M.A. y RAMASWAMY, S. (2007). «A complete multiagent framework for robust and adaptable dynamic job shop scheduling». IEEE Transactions on Systems, Man and Cybernetics, Part C: Applications and Reviews, 37(5), pp. 904-916.
  • MARÍK, V., VRBA, P. y LEITÃO, P. (eds.) (2011). Holonic and multi-agent systems for manufacturing. Berlin: Springer.
  • MOYAUX, T., CHAIB-DRAA, B. y D’AMOURS, S. (2006). «Supply chain management and multiagent systems: An overview». En B. Chalb-draa y J. Müller (eds.), Multiagent based Supply Chain Management, pp. 1-27. Berlin: Springer.
  • OUNNAR, F., PUJO, P. (2012). «Pull control for job shop: holonic manufacturing system approach using multicriteria decision-making». Journal of Intelligent Manufacturing, 23(1), pp. 141-153.
  • RAJABINASAB, A. y MANSOUR, S. (2010). «Dynamic flexible job shop scheduling with alternative process plans: an agent-based approach». The International Journal of Advanced Manufacturing Technology, 54(9-12), pp. 1091- 1107.
  • ROULET-DUBONNET, O. e YSTGAARD, P. (2011). «An application of the holonic manufacturing system to a flexible assembly cell». Lecture Notes in Computer Science, 6867, pp. 29-38.
  • TANG, L., XUAN, H. y LIU, J. (2007). «Hybrid backward and forward dynamic programming based Lagrangian relaxation for single machine scheduling». Computers and Operations Research, 34(9), pp. 2625-2636.
  • THARUMARAJAH, A. (2003). «From fractals and bionics to holonics». En S.M. Deen (ed.), Agent-Based Manufacturing: Advances in the Holonic Approach, pp. 11-30. Berlin: Springer.
  • TIWARI, M.K. y ALLADA, V. (2004). «Solving the machineloading problem in a flexible manufacturing system using a combinatorial auction-based approach». International Journal of Production Research, 42(9), pp. 1879-1893.
  • WELMAN, M.P., WALSH, W.E., WURMAN, P.R. y MACKIEMASON, J.K. (2001). «Auction protocols for decentralized scheduling». Games and Economic Behaviour, 35, pp. 271-303.
  • WONGA, T.N., LEUNGA, C.W., MAKA, K.L. y FUNGB, R.Y.K. (2006). «Dynamic shopfloor scheduling in multiagent manufacturing systems». Expert Systems with Applications, 31(3), pp. 486-494.
  • WOOLDRIDGE, M. (2009). An introduction to multi-agent systems. Chichester : Wiley.
Fuente de los datos: Dialnet