(426c) Hybrid Method Integrating Agent-Based Modeling and Heuristic Tree Search for Scheduling of Complex Batch Processes

Scheduling is a critical layer of decision hierarchy in process manufacturing, having a significant impact on process productivity [1-3]. Though a wide spectrum of batch scheduling methods have been presented, solving an industrial scheduling problem still encounters some challenges due to the complexity of a real-world batch process [1, 4]. The goal of this work is to propose an efficient and effective scheduling method which combines advantages from conventional mixed-integer programming (MIP) methods and agent-based modeling (ABM) methods.

MIP methods can take advantage of the state-of-the-art mathematical programming solvers and guarantee the solution optimality in theory. However, these exact methods suffer from computational complexity. Apart from very simple instances, most scheduling problems, which are among the hardest combinatorial optimization problems, are strongly NP-hard [5-7]. The computational time required to find the optimal schedule can increase exponentially with the problem size, hindering the application to complex problems.

To overcome the computational complexity, ABM methods have been developed. These methods use intelligent agents [8, 9] to model a manufacturing process, and then construct a schedule by simulating the agent-based model. Because decision making is distributed among individual agents, ABM methods can easily cope with a large-scale complex problem [10]. The main advantage of the ABM methods is the computational efficiency, even for a nonlinear scheduling problem [11]. However, the ABM methods suffer from the poor schedule performance because the distributed agent decisions are myopic based on local information.

Both conventional MIP methods and ABM methods have difficulties in solving a complex industrial-size scheduling problem. To solve a complex problem as efficiently as the ABM methods while guaranteeing a high-quality solution comparable to that of the MIP methods, we propose a novel hybrid method integrating agent-based modeling and heuristic tree search. ABM describes the batch process and constructs a feasible schedule under various constraints. To overcome myopic decisions of agents, the agent-based simulation is embedded into a heuristic search algorithm. The heuristic algorithm partially explores the solution space generated by the agent-based simulation. Because global information of the objective function value is used in the search algorithm, the schedule performance is improved. The proposed method shares the advantages from both ABM and MIP, achieving a better balance between the solution efficiency and the schedule performance. As a polynomial-time algorithm, the hybrid method is applicable to large-scale complex industrial scheduling problems. Its performance is demonstrated by comparing with ABM and MIP in two case studies, including a complex one from The Dow Chemical Company.

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 15 2006.

[2]        C. A. Floudas and X. X. Lin, "Continuous-time versus discrete-time approaches for scheduling of chemical processes: a review," Computers & Chemical Engineering, vol. 28, pp. 2109-2129, Oct 2004.

[3]        D. Yue and F. You, " Planning and Scheduling of Flexible Process Networks under Uncertainty with Stochastic Inventory: MINLP Models and Algorithm," AIChE Journal, vol. 59, pp. 1511-1532, May 2013.

[4]        J. M. Wassick, A. Agarwal, N. Akiya, J. Ferrio, S. Bury, and F. Q. You, "Addressing the operational challenges in the development, manufacture, and supply of advanced materials and performance products," Computers & Chemical Engineering, vol. 47, pp. 157-169, Dec 2012.

[5]        D. Ouelhadj and S. Petrovic, "A survey of dynamic scheduling in manufacturing systems," Journal of Scheduling, vol. 12, pp. 417-431, Aug 2009.

[6]        J. D. Ullman, "NP-complete scheduling problems," Journal of Computer and System Sciences, vol. 10, pp. 384-393, 1975.

[7]        M. L. Pinedo, Scheduling: theory, algorithms, and systems: Springer, 2012.

[8]        C. M. Macal and M. J. North, "Tutorial on agent-based modelling and simulation," Journal of Simulation, vol. 4, pp. 151-162, 2010.

[9]        P. Leitao, "Agent-based distributed manufacturing control: A state-of-the-art survey," Engineering Applications of Artificial Intelligence, vol. 22, pp. 979-991, Oct 2009.

[10]     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.

[11]      Y. Chu, J. M. Wassick, and F. You, "Efficient scheduling method of complex batch processes with general network structure via agent-based modeling," AIChE Journal, Accepted, DOI: 10.1002/aic.14101, 2013.