## 4 Generation of Solutions for Nominal CPS  
The two problems presented in the previous section, FPN and RAP, aim to analyze the robustness of a solution of nominal CPS. In this section, we first present our approach to generate a solution to FPN. We will study RAP and analyze the robustness of the solution in the next section. As the classical reachability analysis methods suffer from state explosion problem, we will propose a different approach to representing and finding solutions based on spatial-temporal network (STN) models, which describe the movement of flow tasks in space and time. The steps to construct STN will be presented later and are intuitively done by capturing the flows of tasks from upstream to downstream spatially and temporally based on DTPN. The feasibility problem of nominal CPS aims to determine the feasibility to meet an order with \(J\) types of product demands by a deadline \(\theta\), which extends the problem for a single type of product demand addressed in [8]. The novelty of the proposed approach is to analyze the DTPN based on transformation of the model into spatial-temporal network (STN) models without relying on classical reachability analysis method for timed Petri nets. Such transformation enables compact representation of solutions and efficient search for solutions based on mathematical programming/optimization tools. The proposed method is obviously different from the ones that rely on abstraction of state space of timed Petri nets. To deal with an order with multiple types of product demands by a deadline, a spatial-temporal network \(STN_{j}(V_{j},A_{j})\) is constructed for each \(GJ_{j}\) by applying Algorithm 1, where \(j\in J=\{1,2,3,\ldots,J\}\), based on the demands of type \(j\) tasks, \(Q_{i}\), order deadline, \(\theta\), and the residual capacity. For each type of resource, the residual capacity in a period is defined as the number of unallocated resources. The main algorithm (Algorithm 2) iteratively invokes the algorithm to construct the STN, \(STN_{j}(V_{j},A_{j})\), for each type of task according to the residual capacity, allocates the tasks by solving the Feasibility Problem of Spatial-Temporal Network (FPSTN) (to be introduced later) and updates the residual capacity. The capacity on arcs of STN is bounded by the residual capacity of resources involved. For each STN, tasks can only be allocated according to the residual capacity of resources involved. The residual capacity for each period is calculated by deducting the number of allocated resources from the original capacity. The residual capacity is updated after allocating tasks to STN. The cost on arcs is specified according to the deadline. To optimize the schedule to meet the deadline, we set the cost for arcs connecting to the end node according to the periods. The cost for an arc corresponding to period \(t\) after the deadline \(\theta\) is simply set to \(t\). The cost for all the other arcs is set to zero. A spatial-temporal network \(STN_{j}(V_{j},A_{j})\) is constructed based on the task subnet \(GJ_{j}=(P_{j},T_{j},F_{j},m_{j0},\mu_{j})\) for each \(j\in J\). Note that the set of places in \(P_{j}\) can be decomposed into two disjoint subsets, \(P_{j1}\) and \(P_{j2}\), where \(P_{j1}\) represents the set of idle state places for parts in type \(j\) tasks and \(P_{j2}\) represents the set of busy state places of parts in type \(j\) tasks. That is, \(P_{j}=P_{j1}\cup P_{j2}\). Without loss of generality, it is assumed that the places in \(P_{j1}\) correspond to states in the production process from upstream to downstream. Suppose there are \(N_{j}\) operations in \(GJ_{j}\) and each operation is represented by one start transition and one end transition. Then there are \(2N_{j}\) transitions in \(P_{j}\).