# FMS Scheduling under Availability Constraint with Supervisor Based on Timed Petri Nets
## 1 Introduction  
Flexible Manufacturing Systems (FMS) are widely used since they are swiftly adjustable to different production constraints, which improves their ability to cover different job types without major influence on the production plan [1; 2]. Usually, FMS are subjected to failures caused by their resources' degradation process, which has a direct impact on the production planning. To satisfy demand, an efficient production plan under the availability constraint has to be established leading to the identification of the optimal processing time or makespan [3; 4]. Therefore, despite the risk of increasing deadlocks, both availability and limited resource constraints are considered when FMS scheduling is optimized. Several methods dealing with FMS scheduling have been proposed [5; 6; 7; 8] where the problem NP-hardness was the major challenge encountered [9]. In FMS scheduling, the most important task is to determine the sequence of production. This is related to the production supervision system for which all scheduling constraints must be considered as stated previously [10; 11]. In the literature, several proposed controllers are based on Petri Net (PN) tools [12; 13; 14; 15]. [PERSON] et al. [10] used theory of regions to synthetize the PN controller, which is a set of control places added to the initial PN model. [PERSON] et al. [16] applied Generalized Stochastic Petri Nets (GSPN) modules to derive a model for the workstation controller. For PN analysis, several methods can be founded such as enumerative methods, which are adapted to FMS scheduling [8]. In fact, to solve the scheduling problem using enumerative methods, the reachability graph is entirely or partly explored to retrieve the optimal path [14]. Therefore, the optimal path connecting the initial and final markings corresponds to the optimal firing sequence of PN transitions. Several heuristic methods are developed in order to partly explore the reachabilitygraph and find an optimal or suboptimal production plan. In this perspective, [PERSON] and [PERSON] [17] present a Timed Petri Net (TPN) modeling for scheduling problems and propose a heuristic algorithm A\({}^{*}\)[18; 19; 20] as the resolution approach. This approach is based on generating and explorating of a limited part of the reachability graph. These models were recently improved by [PERSON] et al. [21]. The authors proposed to use an algorithm for the single and multiple lot size scheduling problem and prove the solving heuristic procedure proposed by [PERSON] and [PERSON] [22]. The main inconvenience of enumerative methods is the significant number of reachable markings. Consequently, recent studies introduced new methods such as heuristic search algorithms and artificial intelligence methods in PN modeling for scheduling problems [23; 24]. For instance, [PERSON] et al. [25] introduced a genetic algorithm [26; 27] to solve the sequencing problems relative to Petri net modeling. However, the latter method is limited to FMS with up to five machines. [PERSON] et al. [28] came up with a colored Petri net to model the resource allocation and the operation schedule of a special FMS class. The authors combined a genetic algorithm with a specific dispatching rule (the Shortest Imminent Operation time (SIO)) to get simultaneously the suboptimal resource allocation and the event-driven schedule of the colored Petri net. They were able to provide results with three different scenarios with up to ten machines. The current study is motivated by the complexity of the enumerative methods' increasing number leading to state explosion issues. Therefore, the main contribution of this paper is to derive a mathematical model based on TPN properties to efficiently solve the FMS scheduling. To achieve this, a decomposition methodology of TPN is proposed, where the initial model is decomposed into a set of Timed Marked Graphs (TMGs) considered as a subclass of TPN. Several decomposition methods for Petri net variants have been developed [29]. [PERSON] et al.