(494f) Real-Time Scheduling of Batch Chemical Processes Via Multi-Agent Systems

Scheduling is a crucial decision-making in batch processes [1]. Optimization methods provide a systematic approach to the scheduling problem and the optimality of the solution is guaranteed [2, 3]. However, due to the combinatorial nature of the resulting mixed-integer programming (MIP) problems, the computational complexity is still a main challenge inspite of the significant advances in the optimization theories and algorithms as well as computational power in recent years. Due to these limitation, optimization methods are often applied to the short-term scheduling problem under a set of assumptions which are generally made to control the problem complexity even if they compromise the resulting schedule. For example, the number of time points is often confined to a small value to reduce the size of the problem while sacrificing the resolution in the time domain. Applications of the optimization-based methods to the large-scale, long-term, or real-time scheduling problems are rare.

To circumvent the computational complexity in the MIP based approach, various alternatives have been presented. One alternative that has received wide attention is multi-agent based modeling. A major difference between the agent-based approach and others is that it models a process from the bottom up and decisions in the system are distributed across many intelligent agents [4]. This feature equips the agent-based approach with the power of providing a fast and efficient solution which is applicable to real time rescheduling and thus respond to unanticipated events and uncertain processing times. As a promising alternative for scheduling problems, a number of agent-based techniques have been proposed (see examples [5-11]).

However, most agent-based techniques deal with the sequential scheduling problems while applications to the more complex network problems are scarce. In a general network representation, the task agent interacts with not only the equipment agent but also the state agent and the storage agent. The network representation also adds more constraints to the system which in turn require stronger interactions among agents. The complexity of the network structure imposes more difficulties on the implementation of the agent-based approach.

The goal of this work is to develop a real-time scheduling approach based on the multi-agent systems for general batch processes. A novel scheduling algorithm is developed that provides a good balance between computational efficiency and solution quality. Due to the bottom-up feature in the agent-based model, the developed scheduling method can quickly adapt to a changing environment. The high computational efficiency and good solution quality allow the method to be implemented online to rapidly respond to the uncertainties in the process, e.g. the rush order, the equipment breakdown and the batch failure.

We first propose an agent architecture based the general resource-task network (RTN) representation.  This allows the proposed approach to be applicable to a wide range of batch scheduling problems. Second, to improve the optimality of the solution returned by the agent based approach, we develop a simulation based scheduling algorithm via a two-level agent system as an alternative to a single level agent system. The simulation is conducted by an inner agent based system at the request of the outer agent system responsible for the schedule. As a result, an embedded agent based system is created. The inner agent system copies the current environment of the outer agent system when a scheduling decision needs to be made in the outer agent system. The simulation by the inner agent system returns the predicted objective function value for proposed decisions so that the outer agent system can make the final selection based on the predicted objective function value.

Comparison with the MIP approaches based on discrete time model model is performed through a real-world case study. The results show that agent-based approach can return good quality solution with significantly shorter computational time. Therefore, it can be applied to a long term scheduling problem and can also be more easily implemented online to reschedule the process under the uncertainties. Though the computational time is considerably less than the optimization based method, the solution quality is comparable to the optimal solution.

References:

[1]          C. A. Mendez, J. Cerda, I. E. Grossmann, I. Harjunkoski, and M. Fahl, "State-of-the-art review of optimization methods for short-term scheduling of batch processes," Computers & Chemical Engineering, vol. 30, pp. 913-946, May 2006.

[2]        E. Kondili, C. C. Pantelides, and R. W. H. Sargent, "A general algorithm for short-term scheduling of batch operations—I. MILP formulation," Computers & Chemical Engineering, vol. 17, pp. 211-227, Feb 1993.

[3]        C. C. Pantelides, "Unified frameworks for optimal process planning and scheduling," in Foundations of computer-aided process operations, ed New York: Cache publications, 1994, pp. 253-274.

[4]        W. M. Shen, L. H. Wang, and Q. Hao, "Agent-based distributed manufacturing process planning and scheduling: A state-of-the-art survey," Ieee Transactions on Systems Man and Cybernetics Part C-Applications and Reviews, vol. 36, pp. 563-577, Jul 2006.

[5]        P. I. Cowling, D. Ouelhadj, and S. Petrovic, "A multi-agent architecture for dynamic scheduling of steel hot rolling," Journal of Intelligent Manufacturing, vol. 14, pp. 457-470, Oct 2003.

[6]        P. Gu, S. Balasubramanian, and D. H. Norrie, "Bidding-based process planning and scheduling in a multi-agent system," Computers & Industrial Engineering, vol. 32, pp. 477-496, Apr 1997.

[7]        T. N. Wong, C. W. Leung, K. L. Mak, and R. Y. K. Fung, "Dynamic shopfloor scheduling in multi-agent manufacturing systems," Expert Systems with Applications, vol. 31, pp. 486-494, Oct 2006.

[8]        A. Aldea, R. Banares-Alcantara, L. Jimenez, A. Moreno, J. Martinez, and D. Riano, "The scope of application of multi-agent systems in the process industry: three case studies," Expert Systems with Applications, vol. 26, pp. 39-47, Jan 2004.

[9]        A. Yang, B. Braunschweig, E. S. Fraga, Z. Guessoum, W. Marquardt, O. Nadjemi, D. Paen, D. Pinol, P. Roux, S. Sama, M. Serra, and I. Stalker, "A multi-agent system to facilitate component-based process modeling and design," Computers & Chemical Engineering, vol. 32, pp. 2290-2305, Oct 2008.

[10]      M. Metzger and G. Polakow, "A Survey on Applications of Agent Technology in Industrial Process Control," Ieee Transactions on Industrial Informatics, vol. 7, pp. 570-581, Nov 2011.

[11]      N. Julka, R. Srinivasan, and I. Karimi, "Agent-based supply chain management-1: framework," Computers & Chemical Engineering, vol. 26, pp. 1755-1769, Dec 2002.