# Manufacturing Scheduling Using Colored Petri Nets and Reinforcement Learning
## 2 Literature Review  
### PNs and CPNs Combined with AI Techniques for Manufacturing Scheduling  
CPNs are a discrete-event graphical language used to construct models of distributed, concurrent systems, and discover their properties. PN and CPN models consist of places, transitions, and arcs (joining places and transitions). Transitions and arcs represent events that could cause state changes and their interactions, respectively. Tokens reside in PN places and their number controls the firing of transitions (i.e., system changes). The distribution of tokens on the places, i.e., the marking, represents the state of the system. However, for large complex systems, the size of the PN system model becomes too large to be tractable. CPNs overcome this limitation by the use of color tokens, i.e., tokens with attached data types, and by the use of hierarchical CPNs. Hierarchical CPNs are used to model complex systems by structurally decomposing system modules to submodules. CPN simulation modeling enables investigation of the system behavior by studying the various 'what-if' system scenarios. Time integration (deterministic or stochastic time) in the system model allows the investigation of simulation-based performance measures, such as delays and throughput, as well as modeling of real-time systems. While the graphical aspect of CPNs allows visualization of the modeled system, the mathematical aspect of CPNs allows the set-up of mathematical models governing the behavior of the systems [9] and verification of system properties by means of state space analysis methods. State space analysis identifies all possible reachable states and state changes of a system model, and visualizes the results as a directed graph where nodes represent system states, and arcs represent occurring events. It allows verification of behavioral properties of the system, such as boundedness, home properties, liveness, and fairness. State space exploration allows the automatic detection of all events in a system state, analysis of the cause-effect event relationship, as well as control of system behavior [15]. CPNs provide a modeling formalism that can support the decision-making process of logistics systems, i.e., systems with stochastic, asynchronous, and dynamic behavior [15; 16]. Manufacturing scheduling is an optimization process, considered as NP-hard problem. Reviews of PN/CPN applications in modeling of FMS and production scheduling have been presented (e.g., [13; 17]). Scheduling and control schemes based on combinations of AI techniques and PNs/CPNs aim to explore the advantages of both techniques. AI techniques used for PN based manufacturing scheduling include heuristic rule based methods, heuristic search algorithm methods, mathematical programming methods, expert systems and knowledge-based systems, and distributed AI methods based on MAS and HMS. In heuristic rule-based methods, PNs model the manufacturing system, whereas heuristic rules aim to resolve the scheduling conflicts. However, they were developed for specific classes of problems (e.g., [18; 19]). Exploration of state space methods, i.e., expansion of the reachability graph, in order to find an optimal solution is difficult due to the state space explosion problem even for small systems. Modeling approaches that have been introduced to handle the state space explosion include stochastic well-formed colored nets (SWNs) [20] and Markovian Agents [21]. SWNs were introduced together with a symbolic reachability graph construction algorithm that allows reduction of the Markov chain obtained by CPNs or other classical High-level PNs by exploiting the system symmetries. In [PERSON] et al. [21] an analytic modeling technique based on the use of Markovian Agents and Mean Field Analysis has been proposed that allows the effective modeling of concurrent Big Data applications.