# Manufacturing Scheduling Using Colored Petri Nets and Reinforcement Learning
## 1 Introduction  
Flexibility, cost reduction, production efficiency, improved inventory control, and ability to respond to fluctuations in demand are among the drivers for innovative automated solutions to all members of a supply chain. Manufacturing scheduling is the optimization process of assigning a limited number of resources within a temporal horizon to a set of manufacturing processes of a plan subject to a set of constraints [1]. Computation time to obtain a global optimum increases exponentially with problem size, as such scheduling is generally considered NP-hard (non-polynomial hard) [1; 2; 3], whereas integrated process planning, scheduling and control, and dynamic response to emergence increase the complexity of manufacturing scheduling. New generation real-time control systems allow optimal performance under different conditions for flexible, autonomous, and adaptive manufacturing systems, generally called intelligent manufacturing systems, such as multi-agent systems (MAS) and Holonic Manufacturing Systems (HMS) [2]. The application of agent technologies in manufacturing supports distributed control and execution, and provides robustness, reconfigurability, and re-usability. The new generation of manufacturing control systems may exhibit self-organization and emergent behavior in order to respond to environmental changes [2]. Learning is a key method used for this purpose in agent-based manufacturing systems [4]. Various definitions for the term \"agent\" exist. In Wooldridge [5], \"an agent is a computer system that is situated in some environment and that is capable of autonomous action in this environment in order to meet its design objectives\". The most important properties of an agent for manufacturing systems are autonomy, intelligence, adaptation, and co-operation [2]. An agent can increase its intelligence through learning. Reinforcement learning (RL) is a procedure for an agent to learn to act optimally to achieve its goals through interaction with its environment. For scheduling, the learningtask is to produce a scheduling action that will lead to minimize (or maximize) the related performance measure. A widely used RL algorithm is Q-learning [6; 7]. Petri Nets (PNs) and Colored Petri Nets (CPNs) are a discrete-event graphical and mathematical modeling tool applicable to systems characterized as being concurrent, asynchronous, distributed, parallel, nondeterministic, and/or stochastic [8; 9]. As such, they have been used extensively for modeling, scheduling, and control of Flexible Manufacturing Systems (FMS). Their main features for this purpose can be described as a powerful modeling ability to describe concurrent, synchronous, conflict, and casual behavior; logic properties (such as boundedness, liveness) and control logic code generated directly from PNs [10]; and the performance evaluation of the system [10; 11], including the ability to represent many states concisely, as well as to model precedence relations, deadlocks, conflicts, and resource constraints [12; 13]. CPNs can represent parts with attributes as well as temporal activities (Timed Colored Petri Nets, CTPNs). CPN is a discrete-event modeling tool combining PNs with the functional programming language Standard ML [14]. As a graphical-oriented high-level language, it is used for the modeling and validation of systems in which concurrency, communication, and synchronization play a major role. This is why it finds many applications in the area of distributed artificial intelligence (AI) where agents come from. Combinations of PNs- and AI-search based techniques have found applications to manufacturing scheduling, where PNs model the system and a heuristics based search through the reachability graph finds an optimal or near-optimal solution. However, these methods are not as efficient for large, complex manufacturing systems in changing environments. Moreover, CPNs are more suitable for modeling complex manufacturing systems. In this paper a CTPN-based manufacturing scheduling method is presented.