# Two Effective Strategies to Support Cross-Organization Emergency Resource Allocation Optimization

Authors: Ying Gao; Cong Liu; Qingtian Zeng; Hua Duan
Journal: Mobile Information Systems
 (2021)

---

## Abstract

Cross-organization emergency resource allocation optimization problem is essential to guarantee a successful emergency disposal, and it has become a research focus of modern emergency management. Generally speaking, there are two possible types of resource allocation scenarios: (1) if the emergency resources are overallocated, on the one hand, parallel execution of independent emergency activities can be supported and the emergency disposal time is reduced; on the other hand, too many idle resources may cause low resource utilization rate, high scheduling overhead, and high cost; and (2) if emergency resources are underallocated, this may lead to resource conflicts and the need for some emergency activities to wait for others to complete, and finally the emergency disposal time may increase. Therefore, reasonable emergency resource allocation strategies are highly desired. To the best of our knowledge, there is no formal approach to support the cross-organization emergency resource allocation issue. To handle this problem, we propose a two-layered framework to facilitate the allocation of limited emergency resources to meet its time constraints with high efficiency. More specifically, a kind of Petri net extended with time, resource, and message information, denoted as CE-net, is presented to model cross-organization emergency response processes. Based on the obtained CE-net, the minimum resource requirements are obtained with corresponding algorithms. Then, Minimum Execution Time (MET) strategy and Minimum Resource Consumption (MRC) strategy with their corresponding estimated execution intervals are introduced to facilitate the stakeholder to determine which strategy is suitable according to the timing requirements. A cross-organization fire emergency case is applied to validate the proposed approaches throughout the whole paper.


---

## Body

## 1. Introduction

The allocation of distributed emergency resources has been a challenging issue in the cross-organization emergency management area. An emergency is defined as a situation that imposes immediate risk to life, property, and environment, which requires urgent disposal and intervention to prevent its worsening [1, 2]. These disposals are normally organized as a group of collaborated emergency response processes charged by an emergency command center and several subordinate emergency organizations that need to work together to accomplish the whole emergency mission [3].Generally speaking, cross-organization emergency response processes usually exhibit the following features (or requirements) that differentiate themselves from traditional business processes [1, 4–6]: (1) There are close relations between emergency activities and resources. During the execution of an emergency response process, large quantities of resources, for example, ambulances, fire trucks, medicines, tents, food, and clothing, are badly needed. On the one hand, if the emergency resources are overallocated, parallel execution of independent emergency activities can be enabled to reduce the execution time; however, too many idle resources may lead to low resource utilization rate, high scheduling overhead, and even high cost. On the other hand, if the emergency resources are underallocated, this may lead to resource conflicts and the need for some activities to wait for others to complete, and finally the execution time of the emergency response process may increase. Consequently, reasonable emergency resource allocation strategies are highly desired. (2) There are a lot of collaborations that need either messages sent by other organizations or resources shared among different organizations. Hence, effective collaboration modeling for this case is required. (3) Cross-organization emergency response processes are a real-time service where timeliness is critical to its mission success. Therefore, time performance evaluation and optimization strategies are needed.Modeling across-organization emergency response processes is a complicated and time-consuming work. In addition, optimized emergency resource allocation will benefit both successful emergency response process execution with high time performance and high resource utilization rate. Therefore, emergency resources should be optimized and allocated properly at least from the two following perspectives: (1) minimizing emergency resource requirement as much as possible to achieve a high resource utilization rate and (2) shortening emergency response time as much as possible to achieve its crucial timing constraints. Note that this problem is different from conventional workflow resource scheduling [7–12], which aims at minimizing the application’s runtime on a limited resource set. Differently, we try to propose effective strategies to support cross-organization emergency resource allocation optimization. To this end, we introduce a kind of Petri net [13–15] extended with time, resource, and message information, CE-net for short, to model cross-organization emergency response processes. Actually, the CE-net is an extension of our previous E-net model [1] to suit cross-organization scenario. Accurately, a time interval is used to predict the uncertain execution time of an emergency activity. In addition, emergency resources are divided as reusable and consumable ones; that is, the reusable resources can be reused by other emergency activities when released, while the consumable ones can be used only once and cannot be reused any more.The main contributions of this paper are summarized as follows: (1) a kind of Petri net extended with time, resource, and message information, CE-net for short, is proposed to model cross-organization emergency response processes; (2) a two-layered framework is proposed to support cross-organization emergency resource allocation; and (3) we present two effective resource allocation strategies, that is, the minimum execution time strategy and the minimum resource consumption strategy, to support the efficient emergency resource allocation decision-making based on the resource requirements analysis results.The remainder of this paper is structured as follows. Section2 discusses the related work. In Section 3, a cross-organization fire emergency response scenario is given as a case to validate our proposed approaches. Section 4 investigates the modeling approaches for cross-organization emergency response processes using CE-net. Then, minimum emergency resource requirements analysis is investigated based on the CE-net in Section 5. Section 6 introduces two effective resource allocation strategies to support the emergency resource allocation decision-making. Finally, Section 7 draws concluding remarks.


## 2. Related Work

In this section, we mainly review existing work related to (1) workflow resource allocation as well as emergency resource scheduling and (2) modeling of cross-organizational workflow and emergency response processes.


### 2.1. Workflow Resource Allocation and Emergency Resource Scheduling

Workflow scheduling is a well-known problem whose main objective is to minimize the completion time of a workflow using a given (or limited) set of resources. Deelman proposes one of the most popular algorithms, called Pegasus, to schedule workflows on distributed systems [7]. It is built on top of the list scheduling approach and considers both communication and computation cost. Based on experimental evaluation, it is demonstrated that Pegasus achieves relatively good performance for most cases. Besides the list scheduling approach, other techniques, such as DAG-based scheduling [8], greedy randomized adaptive search [9], and critical path first [10], have also been investigated. More recently, Byun proposes a new algorithm named BTS for estimating the minimum number of hosts that are needed to execute a workflow within a given deadline to bridge the gap between workflow management systems and resource provisioning systems [11, 12].As authoritative emergency management experts, Tufekci and Wallace [16] consider emergency management as a complex multiobjective optimization problem and utilizing limited resources compromisingly is the best way to be adopted. Following their thoughts, emergency resource allocation optimization has been studied by many researchers in the past decades. A dynamic optimization model is used to find the best assignment of available resources to operational areas by Fiedrichet et al. [17]. In [18], by considering multiple disaster places and multiple resource suppliers, an optimized algorithm is proposed to solve resource collision problem for large-scale public emergency response. In [19], the problem of allocating multiple emergency service resources to protect critical transportation infrastructures is studied. Different modeling approaches, including deterministic, stochastic programming and robust optimization, are used to model various risk preferences in decision-making under uncertain service availability and accessibility. To find an optimal solution for resource deployment and dispatching, Kondaveti and Ganz [20] introduce a decision support framework built on rapid information collection and resource tracking functionalities. The equipment control structure presented in [21] enables decentralized and collective decision-making for equipment prioritization and distribution in response to disasters. More recently, by considering time performance, Wang et al. [22] discuss a negotiation strategy and a compromised resources allocation model for emergency response. The negotiation strategy can facilitate requesters to find out the demanded resources efficiently. In addition, a mathematical model is presented to compute the earliest start time of emergency response on condition of continuous requirement for resources.


### 2.2. Modeling of Cross-Organizational Workflow and Emergency Response Processes

Van der Aalst first considers workflows distributed over a number of organizations in [23, 24], where two important questions are addressed: (1) the minimal requirements of interorganizational workflow and (2) how to decide if an interorganizational workflow, modeled with Petri nets, is consistent with an interaction structure specified through a message sequence. In [25], Liu et al. propose a kind of interactive Petri net to model the message channels between different process-oriented systems, and the compatibility preservation of an integrated system with message interaction is revealed. Differently, Schulz and Orlowska focus on three aspects to support the execution of cross-organizational workflows that have been modeled with a process-view approach in [26]: (1) communication between the entities, (2) their impact on an extended workflow engine, and (3) the design of cross-organizational workflow architecture. A Petri net-based state transition approach that binds states of private workflow tasks to their adjacent workflow view is introduced. Its concepts are demonstrated by a scenario involving two workflow management systems. Jiang et al. [27] describe a timed colored Petri net and process-view combined approach to construct cross-organizational workflows, and a three-layered framework is proposed to realize the interoperability of cross-organizational workflows.In [28], we investigate the application of process mining for workflow integration using a type of Petri nets extended with resource and message factors. A process integration-based approach is presented to obtain the model for a cross-organization workflow based on the model mined for each organization and the coordination patterns among different organizations. More recently, we formally define several collaboration patterns, including message interaction pattern, resource interaction pattern, task collaboration pattern, and service outsourcing pattern, in [29]. Modeling and analysis of a cross-department medical workflow are effectively supported, and the correctness is verified by building the reachability graph. To cope with the cross-organizational characteristics of emergency response, we conduct the formal modeling and analysis of cross-organizational emergency response system in [4]. This work first introduces the formal model of emergency activities and identifies five kinds of interactivity relations during the cross-organizational coordination process. Then, OTRM_Net, a kind of Petri nets extended with time, resource message, and organization information, is presented to model the emergency response processes. Also, we further study its timing performance, resource conflict detection, and the reduction or concealment of inner emergency activities. More recently, we propose a top-down approach for model construction and correctness verification of cross-organization emergency response processes in [3]. For the resource conflict and resolution issue during the execution of cross-organization emergency response process, a novel controller design method is given in [5]. In addition, the privacy issue during the modeling of cross-organization emergency response processes is handled by a package reduction-based privacy protection approach in [6].


### 2.3. Summary

Based on the above literature review, we can see that researches into (1) modeling and analysis of cross-organizational emergency response processes and (2) emergency resource allocation and optimization issue have drawn much public attention. However, the existing works have at least the following limitations: (1) emergency resources are not fully quantified (e.g., [2–6]); that is, emergency resource quantity is not investigated during the modeling and allocation process, which will inevitably lead to an inaccurate resource allocation; and (2) there is a lack of time description for emergency activities, based on which we can estimate the time performance of cross-organization emergency response processes when using a specific resource allocation strategy. To deal with these limitations, this work provides a two-layered framework to support optimized resource allocation for cross-organizational emergency response processes.


## 2.1. Workflow Resource Allocation and Emergency Resource Scheduling

Workflow scheduling is a well-known problem whose main objective is to minimize the completion time of a workflow using a given (or limited) set of resources. Deelman proposes one of the most popular algorithms, called Pegasus, to schedule workflows on distributed systems [7]. It is built on top of the list scheduling approach and considers both communication and computation cost. Based on experimental evaluation, it is demonstrated that Pegasus achieves relatively good performance for most cases. Besides the list scheduling approach, other techniques, such as DAG-based scheduling [8], greedy randomized adaptive search [9], and critical path first [10], have also been investigated. More recently, Byun proposes a new algorithm named BTS for estimating the minimum number of hosts that are needed to execute a workflow within a given deadline to bridge the gap between workflow management systems and resource provisioning systems [11, 12].As authoritative emergency management experts, Tufekci and Wallace [16] consider emergency management as a complex multiobjective optimization problem and utilizing limited resources compromisingly is the best way to be adopted. Following their thoughts, emergency resource allocation optimization has been studied by many researchers in the past decades. A dynamic optimization model is used to find the best assignment of available resources to operational areas by Fiedrichet et al. [17]. In [18], by considering multiple disaster places and multiple resource suppliers, an optimized algorithm is proposed to solve resource collision problem for large-scale public emergency response. In [19], the problem of allocating multiple emergency service resources to protect critical transportation infrastructures is studied. Different modeling approaches, including deterministic, stochastic programming and robust optimization, are used to model various risk preferences in decision-making under uncertain service availability and accessibility. To find an optimal solution for resource deployment and dispatching, Kondaveti and Ganz [20] introduce a decision support framework built on rapid information collection and resource tracking functionalities. The equipment control structure presented in [21] enables decentralized and collective decision-making for equipment prioritization and distribution in response to disasters. More recently, by considering time performance, Wang et al. [22] discuss a negotiation strategy and a compromised resources allocation model for emergency response. The negotiation strategy can facilitate requesters to find out the demanded resources efficiently. In addition, a mathematical model is presented to compute the earliest start time of emergency response on condition of continuous requirement for resources.


## 2.2. Modeling of Cross-Organizational Workflow and Emergency Response Processes

Van der Aalst first considers workflows distributed over a number of organizations in [23, 24], where two important questions are addressed: (1) the minimal requirements of interorganizational workflow and (2) how to decide if an interorganizational workflow, modeled with Petri nets, is consistent with an interaction structure specified through a message sequence. In [25], Liu et al. propose a kind of interactive Petri net to model the message channels between different process-oriented systems, and the compatibility preservation of an integrated system with message interaction is revealed. Differently, Schulz and Orlowska focus on three aspects to support the execution of cross-organizational workflows that have been modeled with a process-view approach in [26]: (1) communication between the entities, (2) their impact on an extended workflow engine, and (3) the design of cross-organizational workflow architecture. A Petri net-based state transition approach that binds states of private workflow tasks to their adjacent workflow view is introduced. Its concepts are demonstrated by a scenario involving two workflow management systems. Jiang et al. [27] describe a timed colored Petri net and process-view combined approach to construct cross-organizational workflows, and a three-layered framework is proposed to realize the interoperability of cross-organizational workflows.In [28], we investigate the application of process mining for workflow integration using a type of Petri nets extended with resource and message factors. A process integration-based approach is presented to obtain the model for a cross-organization workflow based on the model mined for each organization and the coordination patterns among different organizations. More recently, we formally define several collaboration patterns, including message interaction pattern, resource interaction pattern, task collaboration pattern, and service outsourcing pattern, in [29]. Modeling and analysis of a cross-department medical workflow are effectively supported, and the correctness is verified by building the reachability graph. To cope with the cross-organizational characteristics of emergency response, we conduct the formal modeling and analysis of cross-organizational emergency response system in [4]. This work first introduces the formal model of emergency activities and identifies five kinds of interactivity relations during the cross-organizational coordination process. Then, OTRM_Net, a kind of Petri nets extended with time, resource message, and organization information, is presented to model the emergency response processes. Also, we further study its timing performance, resource conflict detection, and the reduction or concealment of inner emergency activities. More recently, we propose a top-down approach for model construction and correctness verification of cross-organization emergency response processes in [3]. For the resource conflict and resolution issue during the execution of cross-organization emergency response process, a novel controller design method is given in [5]. In addition, the privacy issue during the modeling of cross-organization emergency response processes is handled by a package reduction-based privacy protection approach in [6].


## 2.3. Summary

Based on the above literature review, we can see that researches into (1) modeling and analysis of cross-organizational emergency response processes and (2) emergency resource allocation and optimization issue have drawn much public attention. However, the existing works have at least the following limitations: (1) emergency resources are not fully quantified (e.g., [2–6]); that is, emergency resource quantity is not investigated during the modeling and allocation process, which will inevitably lead to an inaccurate resource allocation; and (2) there is a lack of time description for emergency activities, based on which we can estimate the time performance of cross-organization emergency response processes when using a specific resource allocation strategy. To deal with these limitations, this work provides a two-layered framework to support optimized resource allocation for cross-organizational emergency response processes.


## 3. A Two-Layered Framework to Support Emergency Resource Allocation

In this section, we introduce a cross-organization fire emergency scenario that will be used as an illustrating example for the paper. Then, we propose our emergency resource allocation mechanism.


### 3.1. A Cross-Organization Fire Emergency Scenario

In this paper, a fire emergency scenario in [3] is adopted as a typical scenario. It involves the following organizations: police station, emergency command center (ECC), explosive ordnance disposal (EOD) team, fire brigade, and hospital. Some of the critical missions in this scenario are rescue of victims and disposal of the moving fire. This scenario includes the following steps:(1)
The police station first receives the fire emergency call and then reports the emergency information to ECC.(2)
The police rushes to the emergency site to perform its detailed disposal missions and then reports the site conditions to ECC.(3)
After receiving the emergency information, ECC first establishes a temporary emergency command group and then makes and issues emergency plans to its collaborative organizations, that is, medical rescue instruction to a hospital, search EOD instruction to an EOD team, and fire rescue instruction to the fire brigade.(4)
The EOD team rushes to the site upon receiving the search EOD instruction from ECC and conducts its specific disposal activities according to its emergency handling requirements and finally reports the EOD search results to ECC.(5)
The fire brigade rushes to the site upon receiving the fire rescue instruction from ECC and conducts its specific disposal activities according to its emergency handling requirements and finally reports the fire rescue results to ECC.(6)
The hospital personnel rush to the site upon receiving the medical rescue instruction from ECC and conduct their specific disposal activities according to their emergency handling requirements and finally report the medical rescue results to ECC.(7)
After receiving all the feedback information from the hospital, EOD team, and fire brigade, ECC makes emergency summary and evaluation and finally does the file archive.(8)
ECC arranges the media coverage for the whole emergency response, and, finally, ECC, fire brigade, and hospital do the media coverage together.


### 3.2. Cross-Organization Emergency Resource Allocation Mechanism

To support the effective emergency resource allocation of cross-organization emergency response processes, a two-layered framework is presented as shown in Figure1.Figure 1
A two-layered framework to support emergency resource allocation.


#### 3.2.1. Layer 1

Each emergency organization establishes its respective emergency response process based on the emergency requirements. Then, each emergency organization submits its emergency response process to the ECC for further integration and evaluation. Next, the ECC integrates the response process received from its subordinate emergency organizations.


#### 3.2.2. Layer 2

The ECC first conducts the emergency resource requirement analysis in terms of minimum consumable resource requirement, minimum reusable resource requirement, and reliable reusable resource requirement. According the resource requirement analysis results, two strategies, that is, minimum execution time strategy and minimum resource consumption strategy, are obtained to guide the resource allocation. In this way, stakeholders can determine which strategy is more suitable according to the amount of available resources and expected finishing time.The scope of this paper is to provide decision-making information to support emergency resource allocation in a cross-organization scenario. In this case, emergency resources are like the public transportation vehicles, public communication devices, emergency personnels, and so forth.


## 3.1. A Cross-Organization Fire Emergency Scenario

In this paper, a fire emergency scenario in [3] is adopted as a typical scenario. It involves the following organizations: police station, emergency command center (ECC), explosive ordnance disposal (EOD) team, fire brigade, and hospital. Some of the critical missions in this scenario are rescue of victims and disposal of the moving fire. This scenario includes the following steps:(1)
The police station first receives the fire emergency call and then reports the emergency information to ECC.(2)
The police rushes to the emergency site to perform its detailed disposal missions and then reports the site conditions to ECC.(3)
After receiving the emergency information, ECC first establishes a temporary emergency command group and then makes and issues emergency plans to its collaborative organizations, that is, medical rescue instruction to a hospital, search EOD instruction to an EOD team, and fire rescue instruction to the fire brigade.(4)
The EOD team rushes to the site upon receiving the search EOD instruction from ECC and conducts its specific disposal activities according to its emergency handling requirements and finally reports the EOD search results to ECC.(5)
The fire brigade rushes to the site upon receiving the fire rescue instruction from ECC and conducts its specific disposal activities according to its emergency handling requirements and finally reports the fire rescue results to ECC.(6)
The hospital personnel rush to the site upon receiving the medical rescue instruction from ECC and conduct their specific disposal activities according to their emergency handling requirements and finally report the medical rescue results to ECC.(7)
After receiving all the feedback information from the hospital, EOD team, and fire brigade, ECC makes emergency summary and evaluation and finally does the file archive.(8)
ECC arranges the media coverage for the whole emergency response, and, finally, ECC, fire brigade, and hospital do the media coverage together.


## 3.2. Cross-Organization Emergency Resource Allocation Mechanism

To support the effective emergency resource allocation of cross-organization emergency response processes, a two-layered framework is presented as shown in Figure1.Figure 1
A two-layered framework to support emergency resource allocation.


### 3.2.1. Layer 1

Each emergency organization establishes its respective emergency response process based on the emergency requirements. Then, each emergency organization submits its emergency response process to the ECC for further integration and evaluation. Next, the ECC integrates the response process received from its subordinate emergency organizations.


### 3.2.2. Layer 2

The ECC first conducts the emergency resource requirement analysis in terms of minimum consumable resource requirement, minimum reusable resource requirement, and reliable reusable resource requirement. According the resource requirement analysis results, two strategies, that is, minimum execution time strategy and minimum resource consumption strategy, are obtained to guide the resource allocation. In this way, stakeholders can determine which strategy is more suitable according to the amount of available resources and expected finishing time.The scope of this paper is to provide decision-making information to support emergency resource allocation in a cross-organization scenario. In this case, emergency resources are like the public transportation vehicles, public communication devices, emergency personnels, and so forth.


## 3.2.1. Layer 1

Each emergency organization establishes its respective emergency response process based on the emergency requirements. Then, each emergency organization submits its emergency response process to the ECC for further integration and evaluation. Next, the ECC integrates the response process received from its subordinate emergency organizations.


## 3.2.2. Layer 2

The ECC first conducts the emergency resource requirement analysis in terms of minimum consumable resource requirement, minimum reusable resource requirement, and reliable reusable resource requirement. According the resource requirement analysis results, two strategies, that is, minimum execution time strategy and minimum resource consumption strategy, are obtained to guide the resource allocation. In this way, stakeholders can determine which strategy is more suitable according to the amount of available resources and expected finishing time.The scope of this paper is to provide decision-making information to support emergency resource allocation in a cross-organization scenario. In this case, emergency resources are like the public transportation vehicles, public communication devices, emergency personnels, and so forth.


## 4. CE-Net-Based Modeling of Cross-Organization Emergency Response Processes

In this section, we propose the formal definition of a Petri net-based model for the cross-organization emergency response processes, named CE-net, which is an extension of our previous E-net [1]. The CE-net is different from our previous models, such as RM_WF_Net in [29] and OTRM_Net in [4], as it emphasizes (1) the uncertainty execution time of emergency activities and (2) effective resource allocation strategy of cross-organization emergency response processes.


### 4.1. CE-Net

Our work is based on Petri nets (or WF-net). Some of the essential terminologies and notations are reviewed following [13–15, 23, 24, 30–37].LetZ = {0, 1, 2, …} and Zn = {1, 2, …, n}, where n is a positive integer, and let R be the set of nonnegative real numbers.Definition 1.
(see [13]). A Petri net is a 4-tuple Σ = (P, T, F, M0), where (1) P = {p1, p2, …, pm} is a finite set of places; (2) T = {t1, t2, …, tn} is a finite set of transitions; (3) F ⊆ (P × T) ∪ (T × P) is a finite set of arcs (flow relation); (4) M0: P ⟶ Z is the initial marking; and (5) P ∩ T = ∅ and P ∪ T ≠ ∅.
For allx ∈ P ∪ T, the set •x = {y| y ∈ P ∪ T ∧ (y, x) ∈ F} is the preset of x, and x• = {y| y ∈ P ∪ T ∧ (x, y) ∈ F} is the postset of x. p is marked by M if M(p) > 0. A transition t ∈ T is enabled under M, if and only if, ∀p ∈ •t: M(p) > 0, denoted as M[t > . If M[t > holds, t may fire, resulting in a new marking M’, denoted as M[t > M’, such that M′(p) = M(p) − 1 if, ∀p ∈ •t \ t•, M′(p) = M(p) + 1 if ∀p ∈ t• \ •t, and otherwise M′(p) = M(p). An initial marking is denoted by M0 and R(M0) is defined as the set of all reachable marking sets of Σ, where ∀Mi ∈ R(M0) such that M0[δ > M.Definition 2.
(see [13]). A weighted Petri net is a 5-tuple ΣW = (P, T, F, M0, W), where (1) Σ = (P, T, F, M0) is a Petri net and (2) W: F ⟶ Zn is a weight function that maps an arc to a positive integer.Definition 3.
(see [23]). A Petri net Σ = (P, T, F, M0) is a WF-net if (1) there is one source place ps ∈ P such that •ps = ∅; (2) there is one sink place pe ∈ P such that pe• = ∅; (3) each node x ∈ P ∪ T is on a path from ps to pe; and (4) ∀p ∈ P, M0(p) = 1 if p = ps, and otherwise M0(p) = 0.
In a WF-net, the transition setT is used to represent the normal activities, the place set P is used to represent logic connection relation of activities, and source place and sink place especially represent the start and end of the process. Based on the classical WF-net, we propose CE-net by extending it with uncertain execution time, resource, and message information to suit the cross-organization emergency response process modeling demand. It differs from our previous RM_WF_Net in [29] as it involves the emergency activity execution interval.Definition 4.
A 5-tuple ΣCE = (P, T, F, α, β, W, M0) is a CE-net if(1)
P = PL ∪ PM ∪ PR, where PL ∩ PR = ∅, PR ∩ PM = ∅, PL ∩ PM = ∅, PL represents the logic place set, PM represents the message place set, and PR represents the resource place set in a ΣCE, and PR = PRR ∪ PCR, where PRR is the reusable resource place set and is the consumable resource place set;(2)
T is the transition set of a CE-net, and it represents an emergency activity set;(3)
F = FL ∪ FM ∪ FR, where(3.1)
FL = (PL × T) ∪ (T × PL) represents the logical structure of a ΣCE;(3.2)
FM = (PM × T) ∪ (T × PM) represents the required and sent messages of a ΣCE;(3.3)
FR = (PR × T) ∪ (T × PR) represents the required and released resources of a ΣCE;(4)
α: T ∪ PR ⟶ R. ∀t ∈ T ∪ PR, α(t) ≥ 0 is the minimum time to execute (or prepare) an emergency activity (or resource) t;(5)
β: T ∪ PR ⟶ R. ∀t ∈ T ∪ PR, β(t) ≥ 0 is the maximum time to execute (or prepare) an emergency activity (or resource) t, such that α(t) ≤ β(t);(6)
W: F ⟶ Zn is the weighted function, such that, ∀f ∈ F, W(f) = 1 if f ∈ FL ∪ FM, W(f) = #req(r, t) if (f ∈ (PRR ∪ PCR) × T) ∧ (f = (r, t)), and W(f) = #sent(t, r) if (f ∈ T × PRR) ∧ (f = (t, r)). #req(t, r) represents the required amount of resource r to execute activity t, and #sent(t, r) represents the sent amount of resource r when activity t finishes (only reusable resources have this flow); (7) ∀p ∈ P, M0(p) = 1 if p ∈ PL ∧ •p = ∅, M0(p) = #num(p) if p ∈ PR, and otherwise M0(p) = 0. #num(p) represents the initial available amount of resource p.
The firing rule of a CE-net is the same as that of a traditional Petri net. Given a markingM, ∀t ∈ T, t is enabled under M if, ∀p ∈ •t, M(p) ≥ 1, where p ∈ PL ∪ PM ∪ PR. Firing an enabled t removes a token from each place in •t and deposits one to each place in t•. All properties, such as reachability and boundedness, can be defined similarly. The main differences between an CE-net and a Petri net are the following: (1) the CE-net is a special type of Petri net extended with message place set (PM) and resource place set (PR); (2) a transition in CE-net is associated with two time functions to represent its minimum and maximum execution time; and (3) a weighted function is introduced to represent the amount of required or sent resources when an emergency activity starts or ends.


### 4.2. Modeling of Cross-Organization Emergency Response Processes Using CE-Net

Modeling of cross-organization emergency response processes involves the following steps: (1) modeling emergency activities with CE-net; (2) modeling control structure with CE-net; and (3) integration of control structure model with those activity models.In a CE-net, an emergency activity model is shown in Figure2, where pready is the ready place, pend is the end place, PresourceReq and PresourceSent are resource places which mean the required and sent resources, pmessageReq and pmessageSent are required and sent message places, and α(t) and β(t) are the minimum execution time and maximum execution time, respectively. To distinguish the logic, resource, and message places properly, a logic place is drawn with a normal circle, a message place is drawn as a circle with dashed line, and a resource place is drawn as a two concentric circles with full line.Figure 2
CE-net model of an emergency activity.It is worth noting that the control structure of a CE-net, denoted as (PL, T, FL, M0|L), is a standard WF-net, where M0|L is the projection of M0 on PL. Therefore, its basic control structures, including sequence structure, concurrent structure, choice structure, and loop structure, can be modeled in the same way as that demonstrated in [29]. According to the emergency response descriptions in Section 3, emergency activity information, including activity ID, activity name, required resources/messages, sent resources/messages, of the Police state, ECC, EOD team, fire brigade, and hospital, is shown in Tables 1–3, respectively.Table 1
Emergency activity information.
Activity IDMinimum execution timeMaximum execution timeRequired messagesSent messagesRequired resourcesSent resourcesOrganizationsPreactivitiest124∅∅∅∅{Police station}∅t235∅{pm1}{pr2}{pr2}{Police station}{t1}t347∅∅{pr1}{pr1}{Police station}{t2}t4510∅∅{pr32, pr52}{pr32}{Police station}{t3}t5612∅∅{pr32, pr52}{pr32}{Police station}{t3}t6814∅∅{pr32, pr52}{pr32}{Police station}{t3}t758∅{pm2}∅∅{Police station}{t4, t5, t6}t8610∅∅∅∅{Police station}{t7}t923{pm1}∅∅∅{ECC}∅t1035{pm2}{pm3, pm4, pm5}{pr2}{pr2}{ECC}{t9}t1158{pm6, pm7}∅∅∅{ECC}{t10}t12815∅∅∅∅{ECC}{t11}t1324∅∅∅∅{ECC}{t12}t1435∅∅{pr32, pr4}{pr32, pr4}{ECC, fire brigade, hospital}{t13}t1548{pm3}∅∅∅{EOD team}∅t161416∅∅∅∅{EOD team}{t15}t1745∅{pm6}{pr2}{pr2}{EOD team}{t16}t1846{pm4}∅{pr1}{pr1}{Fire brigade}{∅}t19812∅∅∅∅{Fire brigade}{t18}t2068∅∅∅∅{Fire brigade}{t19}t2168∅∅∅∅{Fire brigade}{t19}t2223∅{pm7}{pr2}{pr2}{Fire brigade}{t20, t21}t2335{pm5}∅{pr1}{pr1}{Hospital}{∅}t2446∅∅∅∅{Hospital}{t23}t25812∅∅∅∅{Hospital}{t24}t2668∅∅∅∅{Hospital}{t24}t2746∅∅∅∅{Hospital}{t25, t26}t2823∅{pm8}{pr2}{pr2}{Hospital}{t27}Table 2
Emergency activity and message information.
Activity/messageMeaningt1Alarm receiptt2Report emergency informationt3Rush to the site (police)t4Deal with the scenet5Evacuationt6Rescue the woundedt7Alarm receiptt8Search the suspectt9Establish temporary emergency centert10Make and issue emergency planst11Emergency summary and evaluationt12File archivet13Arranges media coveraget14Do media coverage (together)t15Rush to the site (EOD team)t16Search the EODt17Report the EOD search resultst18Rush to the site (fire bridges)t19Fight the firet20Recovery the sitet21Conduct mitigation operationst22Report the fire rescuet23Rush to the site (hospital)t24Shunt the woundedt25Treat the severely injured peoplet26Treat the slightly injured peoplet27Environmental quality detectiont28Report the medical rescuepm1Emergency informationpm2Site conditionspm3Medical rescue instructionpm4Fire rescue instructionpm5Search EOD instructionpm6EOD search resultspm7Fire rescue resultspm8Medical rescue resultsTable 3
Emergency resource information.
Resource IDMeaningPropertyPr1Public transportation vehicleReusablePr2Public communication deviceReusablePr3Emergency personnelReusablePr4Media personnel and equipmentReusablePr5Smoke masksConsumableIt is worth mentioning that we use multisets to represent the required resource set and the sent resource set of an emergency activity.M(R) is the set of all multisets over a set R. For some multiset m ∈ M(R), m(r) denotes the number of times element r ∈ R appears in m. For example, m = {a2, b3} is a multiset over {a, b}. It represents that element a appears two times and element b appears three times in m. The ordering of elements is irrelevant for multiset.Using the detailed modeling approaches in [29], a CE-net is obtained as shown in Figure 3, which represents the overall execution process of the cross-organization fire emergency response processes in Section 3.Figure 3
CE-net of cross-organization fire emergency response processes.It is worth noting that there are five resource places that correspond to five kind resources. For graphic simplicity, some resources may have more than one resource place.


## 4.1. CE-Net

Our work is based on Petri nets (or WF-net). Some of the essential terminologies and notations are reviewed following [13–15, 23, 24, 30–37].LetZ = {0, 1, 2, …} and Zn = {1, 2, …, n}, where n is a positive integer, and let R be the set of nonnegative real numbers.Definition 1.
(see [13]). A Petri net is a 4-tuple Σ = (P, T, F, M0), where (1) P = {p1, p2, …, pm} is a finite set of places; (2) T = {t1, t2, …, tn} is a finite set of transitions; (3) F ⊆ (P × T) ∪ (T × P) is a finite set of arcs (flow relation); (4) M0: P ⟶ Z is the initial marking; and (5) P ∩ T = ∅ and P ∪ T ≠ ∅.
For allx ∈ P ∪ T, the set •x = {y| y ∈ P ∪ T ∧ (y, x) ∈ F} is the preset of x, and x• = {y| y ∈ P ∪ T ∧ (x, y) ∈ F} is the postset of x. p is marked by M if M(p) > 0. A transition t ∈ T is enabled under M, if and only if, ∀p ∈ •t: M(p) > 0, denoted as M[t > . If M[t > holds, t may fire, resulting in a new marking M’, denoted as M[t > M’, such that M′(p) = M(p) − 1 if, ∀p ∈ •t \ t•, M′(p) = M(p) + 1 if ∀p ∈ t• \ •t, and otherwise M′(p) = M(p). An initial marking is denoted by M0 and R(M0) is defined as the set of all reachable marking sets of Σ, where ∀Mi ∈ R(M0) such that M0[δ > M.Definition 2.
(see [13]). A weighted Petri net is a 5-tuple ΣW = (P, T, F, M0, W), where (1) Σ = (P, T, F, M0) is a Petri net and (2) W: F ⟶ Zn is a weight function that maps an arc to a positive integer.Definition 3.
(see [23]). A Petri net Σ = (P, T, F, M0) is a WF-net if (1) there is one source place ps ∈ P such that •ps = ∅; (2) there is one sink place pe ∈ P such that pe• = ∅; (3) each node x ∈ P ∪ T is on a path from ps to pe; and (4) ∀p ∈ P, M0(p) = 1 if p = ps, and otherwise M0(p) = 0.
In a WF-net, the transition setT is used to represent the normal activities, the place set P is used to represent logic connection relation of activities, and source place and sink place especially represent the start and end of the process. Based on the classical WF-net, we propose CE-net by extending it with uncertain execution time, resource, and message information to suit the cross-organization emergency response process modeling demand. It differs from our previous RM_WF_Net in [29] as it involves the emergency activity execution interval.Definition 4.
A 5-tuple ΣCE = (P, T, F, α, β, W, M0) is a CE-net if(1)
P = PL ∪ PM ∪ PR, where PL ∩ PR = ∅, PR ∩ PM = ∅, PL ∩ PM = ∅, PL represents the logic place set, PM represents the message place set, and PR represents the resource place set in a ΣCE, and PR = PRR ∪ PCR, where PRR is the reusable resource place set and is the consumable resource place set;(2)
T is the transition set of a CE-net, and it represents an emergency activity set;(3)
F = FL ∪ FM ∪ FR, where(3.1)
FL = (PL × T) ∪ (T × PL) represents the logical structure of a ΣCE;(3.2)
FM = (PM × T) ∪ (T × PM) represents the required and sent messages of a ΣCE;(3.3)
FR = (PR × T) ∪ (T × PR) represents the required and released resources of a ΣCE;(4)
α: T ∪ PR ⟶ R. ∀t ∈ T ∪ PR, α(t) ≥ 0 is the minimum time to execute (or prepare) an emergency activity (or resource) t;(5)
β: T ∪ PR ⟶ R. ∀t ∈ T ∪ PR, β(t) ≥ 0 is the maximum time to execute (or prepare) an emergency activity (or resource) t, such that α(t) ≤ β(t);(6)
W: F ⟶ Zn is the weighted function, such that, ∀f ∈ F, W(f) = 1 if f ∈ FL ∪ FM, W(f) = #req(r, t) if (f ∈ (PRR ∪ PCR) × T) ∧ (f = (r, t)), and W(f) = #sent(t, r) if (f ∈ T × PRR) ∧ (f = (t, r)). #req(t, r) represents the required amount of resource r to execute activity t, and #sent(t, r) represents the sent amount of resource r when activity t finishes (only reusable resources have this flow); (7) ∀p ∈ P, M0(p) = 1 if p ∈ PL ∧ •p = ∅, M0(p) = #num(p) if p ∈ PR, and otherwise M0(p) = 0. #num(p) represents the initial available amount of resource p.
The firing rule of a CE-net is the same as that of a traditional Petri net. Given a markingM, ∀t ∈ T, t is enabled under M if, ∀p ∈ •t, M(p) ≥ 1, where p ∈ PL ∪ PM ∪ PR. Firing an enabled t removes a token from each place in •t and deposits one to each place in t•. All properties, such as reachability and boundedness, can be defined similarly. The main differences between an CE-net and a Petri net are the following: (1) the CE-net is a special type of Petri net extended with message place set (PM) and resource place set (PR); (2) a transition in CE-net is associated with two time functions to represent its minimum and maximum execution time; and (3) a weighted function is introduced to represent the amount of required or sent resources when an emergency activity starts or ends.


## 4.2. Modeling of Cross-Organization Emergency Response Processes Using CE-Net

Modeling of cross-organization emergency response processes involves the following steps: (1) modeling emergency activities with CE-net; (2) modeling control structure with CE-net; and (3) integration of control structure model with those activity models.In a CE-net, an emergency activity model is shown in Figure2, where pready is the ready place, pend is the end place, PresourceReq and PresourceSent are resource places which mean the required and sent resources, pmessageReq and pmessageSent are required and sent message places, and α(t) and β(t) are the minimum execution time and maximum execution time, respectively. To distinguish the logic, resource, and message places properly, a logic place is drawn with a normal circle, a message place is drawn as a circle with dashed line, and a resource place is drawn as a two concentric circles with full line.Figure 2
CE-net model of an emergency activity.It is worth noting that the control structure of a CE-net, denoted as (PL, T, FL, M0|L), is a standard WF-net, where M0|L is the projection of M0 on PL. Therefore, its basic control structures, including sequence structure, concurrent structure, choice structure, and loop structure, can be modeled in the same way as that demonstrated in [29]. According to the emergency response descriptions in Section 3, emergency activity information, including activity ID, activity name, required resources/messages, sent resources/messages, of the Police state, ECC, EOD team, fire brigade, and hospital, is shown in Tables 1–3, respectively.Table 1
Emergency activity information.
Activity IDMinimum execution timeMaximum execution timeRequired messagesSent messagesRequired resourcesSent resourcesOrganizationsPreactivitiest124∅∅∅∅{Police station}∅t235∅{pm1}{pr2}{pr2}{Police station}{t1}t347∅∅{pr1}{pr1}{Police station}{t2}t4510∅∅{pr32, pr52}{pr32}{Police station}{t3}t5612∅∅{pr32, pr52}{pr32}{Police station}{t3}t6814∅∅{pr32, pr52}{pr32}{Police station}{t3}t758∅{pm2}∅∅{Police station}{t4, t5, t6}t8610∅∅∅∅{Police station}{t7}t923{pm1}∅∅∅{ECC}∅t1035{pm2}{pm3, pm4, pm5}{pr2}{pr2}{ECC}{t9}t1158{pm6, pm7}∅∅∅{ECC}{t10}t12815∅∅∅∅{ECC}{t11}t1324∅∅∅∅{ECC}{t12}t1435∅∅{pr32, pr4}{pr32, pr4}{ECC, fire brigade, hospital}{t13}t1548{pm3}∅∅∅{EOD team}∅t161416∅∅∅∅{EOD team}{t15}t1745∅{pm6}{pr2}{pr2}{EOD team}{t16}t1846{pm4}∅{pr1}{pr1}{Fire brigade}{∅}t19812∅∅∅∅{Fire brigade}{t18}t2068∅∅∅∅{Fire brigade}{t19}t2168∅∅∅∅{Fire brigade}{t19}t2223∅{pm7}{pr2}{pr2}{Fire brigade}{t20, t21}t2335{pm5}∅{pr1}{pr1}{Hospital}{∅}t2446∅∅∅∅{Hospital}{t23}t25812∅∅∅∅{Hospital}{t24}t2668∅∅∅∅{Hospital}{t24}t2746∅∅∅∅{Hospital}{t25, t26}t2823∅{pm8}{pr2}{pr2}{Hospital}{t27}Table 2
Emergency activity and message information.
Activity/messageMeaningt1Alarm receiptt2Report emergency informationt3Rush to the site (police)t4Deal with the scenet5Evacuationt6Rescue the woundedt7Alarm receiptt8Search the suspectt9Establish temporary emergency centert10Make and issue emergency planst11Emergency summary and evaluationt12File archivet13Arranges media coveraget14Do media coverage (together)t15Rush to the site (EOD team)t16Search the EODt17Report the EOD search resultst18Rush to the site (fire bridges)t19Fight the firet20Recovery the sitet21Conduct mitigation operationst22Report the fire rescuet23Rush to the site (hospital)t24Shunt the woundedt25Treat the severely injured peoplet26Treat the slightly injured peoplet27Environmental quality detectiont28Report the medical rescuepm1Emergency informationpm2Site conditionspm3Medical rescue instructionpm4Fire rescue instructionpm5Search EOD instructionpm6EOD search resultspm7Fire rescue resultspm8Medical rescue resultsTable 3
Emergency resource information.
Resource IDMeaningPropertyPr1Public transportation vehicleReusablePr2Public communication deviceReusablePr3Emergency personnelReusablePr4Media personnel and equipmentReusablePr5Smoke masksConsumableIt is worth mentioning that we use multisets to represent the required resource set and the sent resource set of an emergency activity.M(R) is the set of all multisets over a set R. For some multiset m ∈ M(R), m(r) denotes the number of times element r ∈ R appears in m. For example, m = {a2, b3} is a multiset over {a, b}. It represents that element a appears two times and element b appears three times in m. The ordering of elements is irrelevant for multiset.Using the detailed modeling approaches in [29], a CE-net is obtained as shown in Figure 3, which represents the overall execution process of the cross-organization fire emergency response processes in Section 3.Figure 3
CE-net of cross-organization fire emergency response processes.It is worth noting that there are five resource places that correspond to five kind resources. For graphic simplicity, some resources may have more than one resource place.


## 5. Reduction Rules of CE-Net

Based on the modeling approaches in last subsection, a CE-net can be constructed. Unfortunately, the CE-net may contain an excessive number of places and transitions, which will lead to an inefficient analysis and troublesome understanding. Hence, two reduction rules are introduced to reduce the model scale while maintaining the structure, time, resource, and message invariant.


### 5.1. Rule 4.1

Given a CE-net ΣEC = (P, T, F, α, β, W, M0), if ti, tj ∈ T are two sequential activities such that ti• = •tj, •ti ∩ PR = ∅, ti• ∩ (PR ∪ PM) = ∅, •tj ∩ (PR ∪ PM) = ∅, and tj• ∩ PR = ∅, and their timing constraints are [α(ti), β(ti)] and [α(tj), β(tj)], respectively. Then, transitions ti and tj can be merged to a new one, denoted as tij, such that •tij = •ti, tij• = tj•, α(tij) = α(ti) + α(tj), and β(tij) = β(ti) + β(tj).Rule 1 shows the reduction rule for sequential activities that do not require any messages and resources, and an example of Rule 4.1 is shown in Figure4, where ti and tj are merged to tij.Figure 4
Reduction example of rule 1.


### 5.2. Rule 4.2

Given a CE-net ΣEC = (P, T, F, α, β, W, M0), if ti, tj ∈ T are two concurrent activities such that •ti ∩ (PR ∪ PM) = ∅, ti• ∩ (PR ∪ PM) = ∅, •tj ∩ (PR ∪ PM) = ∅, and tj• ∩ (PR ∪ PM) = ∅, and their timing constraints are [α(ti), β(ti)] and [α(tj), β(tj)], respectively. Then, transitions ti and tj can be merged to a new transition, denoted as tij, such that α(tij) = max{α(ti), α(tj)} and β(tij) = max{β(ti), β(tj)}.Rule 2 shows the reduction for two concurrent activities that do not require any messages and resources, and an example of Rule 4.2 is illustrated in Figure5, where ti and tj are replaced by tij.Figure 5
Reduction example of rule 2.We have the following explanations for reduction rules: (1) we only introduce the atomic reduction rules, and some advanced composite rules can be realized on top of these basic ones; (2) we only introduce rules that suit the sequence and concurrent structures, while choice and loop structures are not considered because their reduction results are usually not deterministic and can cause property changes compared with the original model; and (3) the firing rule of a transition obtained by reduction is the same as that of a traditional one; that is, the firing rule of a reduced CE-net is the same as that of a Petri net.In the following, we show how to use our reduction rules to reduce the CE-net in Figure3. t11−12−13 is obtained by merging transitions t11, t12, and t13 using reduction Rule 4.1 such that α(t11−12−13) = α(t11) + α(t12) + α(t13) = 5 + 8 + 2 = 15 and β(t11−12−13) = β(t11) + β(t12) + β(t13) = 8 + 15 + 4 = 27. t19−20−21 is obtained by (1) merging transitions t20 and t21 using reduction Rule 4.2 to obtain t20−21 such that α(t20−21) = max{α(t20), α(t21)} = max{6, 6} = 6, and β(t20−21) = max{β(t20), β(t21)} = max{8, 8} = 8 and (2) merging transitions t19 and t20−21 with reduction Rule 4.1 such that α(t19−20−21) = α(t19) + α(t20−21) = 8 + 6 = 14 and β(t19−20−21) = β(t19) + β(t20−21) = 12 + 8 = 20. t24−25−26−27−28 is obtained by (1) merging transitions t25 and t26 using reduction Rule 4.2 to obtain t25−26 such that α(t25−26) = max{α(t25), α(t26)} = max{8, 6} = 8, and β(t25−26) = max{β(t25), β(t26)} = max{12, 8} = 12 and (2) merging transitions t24, t25−26, t27, and t28 to obtain t24−25−26−27−28 with reduction Rule 4.1 such that α(t24−25−26−27) = α(t24) + α(t25−26) + α(t27) + α(t28) = 4 + 8 + 4 + 2 = 18 and β(t24−25−26−27) = β(t24) + β(t25−26) + β(t27) + β(t28) = 6 + 12 + 6 + 3 = 27.The CE-net of the cross-organization fire emergency response processes after reduction is shown in Figure6. To give a comparison, Table 4 gives the number of transitions, message places, and resource places of the CE-net before and after reduction. Based on the comparison, we can clearly see that (1) its scale (in terms of the number of transitions and logic places) is much smaller and (2) the collaboration elements (resources and messages) stay invariant.Figure 6
Reduced CE-net of the cross-organization fire emergency response process.Table 4
Scale comparison of the CE-net before and after reduction.
ItemBefore reductionAfter reductionNumber of transitions2820Message places88Resource places55


## 5.1. Rule 4.1

Given a CE-net ΣEC = (P, T, F, α, β, W, M0), if ti, tj ∈ T are two sequential activities such that ti• = •tj, •ti ∩ PR = ∅, ti• ∩ (PR ∪ PM) = ∅, •tj ∩ (PR ∪ PM) = ∅, and tj• ∩ PR = ∅, and their timing constraints are [α(ti), β(ti)] and [α(tj), β(tj)], respectively. Then, transitions ti and tj can be merged to a new one, denoted as tij, such that •tij = •ti, tij• = tj•, α(tij) = α(ti) + α(tj), and β(tij) = β(ti) + β(tj).Rule 1 shows the reduction rule for sequential activities that do not require any messages and resources, and an example of Rule 4.1 is shown in Figure4, where ti and tj are merged to tij.Figure 4
Reduction example of rule 1.


## 5.2. Rule 4.2

Given a CE-net ΣEC = (P, T, F, α, β, W, M0), if ti, tj ∈ T are two concurrent activities such that •ti ∩ (PR ∪ PM) = ∅, ti• ∩ (PR ∪ PM) = ∅, •tj ∩ (PR ∪ PM) = ∅, and tj• ∩ (PR ∪ PM) = ∅, and their timing constraints are [α(ti), β(ti)] and [α(tj), β(tj)], respectively. Then, transitions ti and tj can be merged to a new transition, denoted as tij, such that α(tij) = max{α(ti), α(tj)} and β(tij) = max{β(ti), β(tj)}.Rule 2 shows the reduction for two concurrent activities that do not require any messages and resources, and an example of Rule 4.2 is illustrated in Figure5, where ti and tj are replaced by tij.Figure 5
Reduction example of rule 2.We have the following explanations for reduction rules: (1) we only introduce the atomic reduction rules, and some advanced composite rules can be realized on top of these basic ones; (2) we only introduce rules that suit the sequence and concurrent structures, while choice and loop structures are not considered because their reduction results are usually not deterministic and can cause property changes compared with the original model; and (3) the firing rule of a transition obtained by reduction is the same as that of a traditional one; that is, the firing rule of a reduced CE-net is the same as that of a Petri net.In the following, we show how to use our reduction rules to reduce the CE-net in Figure3. t11−12−13 is obtained by merging transitions t11, t12, and t13 using reduction Rule 4.1 such that α(t11−12−13) = α(t11) + α(t12) + α(t13) = 5 + 8 + 2 = 15 and β(t11−12−13) = β(t11) + β(t12) + β(t13) = 8 + 15 + 4 = 27. t19−20−21 is obtained by (1) merging transitions t20 and t21 using reduction Rule 4.2 to obtain t20−21 such that α(t20−21) = max{α(t20), α(t21)} = max{6, 6} = 6, and β(t20−21) = max{β(t20), β(t21)} = max{8, 8} = 8 and (2) merging transitions t19 and t20−21 with reduction Rule 4.1 such that α(t19−20−21) = α(t19) + α(t20−21) = 8 + 6 = 14 and β(t19−20−21) = β(t19) + β(t20−21) = 12 + 8 = 20. t24−25−26−27−28 is obtained by (1) merging transitions t25 and t26 using reduction Rule 4.2 to obtain t25−26 such that α(t25−26) = max{α(t25), α(t26)} = max{8, 6} = 8, and β(t25−26) = max{β(t25), β(t26)} = max{12, 8} = 12 and (2) merging transitions t24, t25−26, t27, and t28 to obtain t24−25−26−27−28 with reduction Rule 4.1 such that α(t24−25−26−27) = α(t24) + α(t25−26) + α(t27) + α(t28) = 4 + 8 + 4 + 2 = 18 and β(t24−25−26−27) = β(t24) + β(t25−26) + β(t27) + β(t28) = 6 + 12 + 6 + 3 = 27.The CE-net of the cross-organization fire emergency response processes after reduction is shown in Figure6. To give a comparison, Table 4 gives the number of transitions, message places, and resource places of the CE-net before and after reduction. Based on the comparison, we can clearly see that (1) its scale (in terms of the number of transitions and logic places) is much smaller and (2) the collaboration elements (resources and messages) stay invariant.Figure 6
Reduced CE-net of the cross-organization fire emergency response process.Table 4
Scale comparison of the CE-net before and after reduction.
ItemBefore reductionAfter reductionNumber of transitions2820Message places88Resource places55


## 6. CE-Net-Based Minimum Resource Requirement Analysis

In this section, we discuss the minimum resource requirements of cross-organization emergency response processes based on the CE-net. During this procedure, we analyze reusable and consumable resources separately. For simplicity, we first redefine two vector operators, “<” and “≥.” LetX = <x1, x2, …, xn> and Y = <y1, y2, …, xn> be two n-dimension vectors. If, ∀X.xi ≥ Y.yi, for 1 ≤ i ≤ n, we have X ≥ Y. If ∃X.xi < Y.yi, for 1 ≤ i ≤ n, we have X < Y. Assume that the available consumable resource vector and available reusable resource vector of cross-organization emergency response processes are denoted as RAC and RAR, respectively.


### 6.1. Minimum Consumable Resource Requirement

The minimum consumable resource vector is denoted asRMC = <q(r1), q(r2), …, q(rn) >, where (1) ri (i = 1, 2, …, n) refers to a kind of consumable resource and it is modeled as a resource place pri in PCR and (2) q(ri) represents the number of ri. VMC can be computed by taking as input a CE-net based on the following algorithm.The complexity of Algorithm1 is Ο(|PCR| × |T|), where |PCR| is the number of consumable resource types and |T| is the number of emergency activities. For real-life emergency resource management, the cross-organization emergency response processes will break down because of shortage of consumable resources if RAC < RMC.Algorithm 1: Calculate the minimum consumable resource vector RMC.
Input: ΣCE = (P, T, F, α, β, W, M0).Output: RMC.(1)
/∗Step 1: initialization∗/(2)
Step 1: sum ⟵ 0,RMC ⟵ 0.(3)
/∗Step 2: to obtain the minimum consumable resource vector∗/(4)
Step 2:FOR ∀pri ∈ PCRDO(5)
FOR ∀ti ∈ TDO(6)
sum ⟵ sum +W(pri, ti);(7)
END DO(8)
q(RMC.ri) ⟵ sum;(9)
sum ⟵ 0;(10)
END DO(11)
Step 3: OutputRMC.


### 6.2. Minimum Reusable Resource Requirement

The minimum reusable resource vector is denoted asRMR = <q(r1), q(r2), …, q(rm) >, where (1) ri (i = 1, 2, …, n) refers to a kind of reusable resource and it is modeled as a resource place pri in PRR and (2) q(ri) represents the number of ri. Algorithm 2 shows how to compute VMR by taking as input a CE-net.Algorithm 2: Calculate the minimum reusable resource vector RMR.
Input: ΣCE = (P, T, F, α, β, W, M0).Output: RMR.(1)
/∗Step 1: initialization∗/(2)
Step 1:RMR ⟵ 0;(3)
/∗Step 2: to obtain the minimum reusable resource vector∗/(4)
Step 2:FOR ∀pri ∈ PRRDO(5)
FOR ∀ti ∈ TDO(6)
IFW(pri, ti) > q(RMR.ri) THEN(7)
q(RMR.ri) ⟵ W(pri, ti);(8)
END IF(9)
END DO(10)
END DO(11)
Step 3: OutputRMR.The complexity of Algorithm2 is Ο(|PRR| × |T|), where |PRR| is the number of reusable resource types and |T| is the number of activities. For real-life emergency resource management, the cross-organization emergency response processes will break down because of shortage of reusable resources if RAR < RMR.


### 6.3. Reliable Reusable Resource Requirement

Even though we haveRAR ≥ RMR, resource conflicts may still exist during the execution of cross-organization emergency response processes because of resource dependency and limited available resources. This kind of conflicts may delay the execution time of the emergency process. Therefore, the reliable reusable resource vector of a CE-net, denoted as RRR = <q(r1), q(r2),…, q(rm)>, is introduced, where ri (i = 1, 2, …, n) refers to a kind of reusable resource and is represented as a resource place pri in PRR. Algorithm 3 shows how to compute RRR by taking as input a CE-net.Algorithm 3: Calculate the reliable reusable resource vector RRR.
Input: ΣCE = (P, T, F, α, β, W, M0), DependencySet and RMR.Output: RRR.(1)
/∗Step 1: initialization∗/(2)
Step 1: sum ⟵ 0,VRR ⟵ VMR;(3)
/∗Step 2: to obtain the reliable reusable resource vector∗/(4)
Step 2:FOR ∀pri ∈ PRRDO(5)
FOR ∀(ti, tj) ∈ DependencySet DO(6)
sum ⟵W(pri, ti) + W(pri, tj);(7)
IF sum > q(RRR.ri) THEN(8)
q(RRR.ri) ⟵ sum;(9)
END IF(10)
sum ⟵ 0;(11)
END DO(12)
END DO(13)
Step 3: OutputRRR.The complexity of Algorithm3 is Ο(|PRR| × |T|), where |PRR| is the number of reusable resource types and |T| is the number of emergency activities. If RAR ≥ RRR, there is no resource conflict during process execution; that is, potential resource conflicts are avoided as sufficient resources are provided to support parallel execution of activities in resource dependency.Theorem 1.
The proposed approaches to analyze resource requirements of cross-organization emergency response processes on the basis of CE-net have Ο(m × n) time complexity, where m is the number of resource types and n is the number of emergency activities.Proof.
To analyze the resource requirement, three kinds of resource metrics, that is, the minimum consumable resource vector, the minimum reusable resource vector, and there liable reusable resource vector, are needed. Their calculation algorithms are implemented in Algorithms1–3, the complexity of which is no bigger than Ο(m × n), where m is the number of resource types and n is the number of emergency activities. Therefore, the proposed method to analyze the resource requirement has its Ο(m × n) time complexity.
Taking the cross-organization fire emergency response processes as an example, we haveRMC = <6>, RMR = <1, 1, 2, 1>, and RRR = <3, 2, 6, 1> by executing Algorithms 1–3.


## 6.1. Minimum Consumable Resource Requirement

The minimum consumable resource vector is denoted asRMC = <q(r1), q(r2), …, q(rn) >, where (1) ri (i = 1, 2, …, n) refers to a kind of consumable resource and it is modeled as a resource place pri in PCR and (2) q(ri) represents the number of ri. VMC can be computed by taking as input a CE-net based on the following algorithm.The complexity of Algorithm1 is Ο(|PCR| × |T|), where |PCR| is the number of consumable resource types and |T| is the number of emergency activities. For real-life emergency resource management, the cross-organization emergency response processes will break down because of shortage of consumable resources if RAC < RMC.Algorithm 1: Calculate the minimum consumable resource vector RMC.
Input: ΣCE = (P, T, F, α, β, W, M0).Output: RMC.(1)
/∗Step 1: initialization∗/(2)
Step 1: sum ⟵ 0,RMC ⟵ 0.(3)
/∗Step 2: to obtain the minimum consumable resource vector∗/(4)
Step 2:FOR ∀pri ∈ PCRDO(5)
FOR ∀ti ∈ TDO(6)
sum ⟵ sum +W(pri, ti);(7)
END DO(8)
q(RMC.ri) ⟵ sum;(9)
sum ⟵ 0;(10)
END DO(11)
Step 3: OutputRMC.


## 6.2. Minimum Reusable Resource Requirement

The minimum reusable resource vector is denoted asRMR = <q(r1), q(r2), …, q(rm) >, where (1) ri (i = 1, 2, …, n) refers to a kind of reusable resource and it is modeled as a resource place pri in PRR and (2) q(ri) represents the number of ri. Algorithm 2 shows how to compute VMR by taking as input a CE-net.Algorithm 2: Calculate the minimum reusable resource vector RMR.
Input: ΣCE = (P, T, F, α, β, W, M0).Output: RMR.(1)
/∗Step 1: initialization∗/(2)
Step 1:RMR ⟵ 0;(3)
/∗Step 2: to obtain the minimum reusable resource vector∗/(4)
Step 2:FOR ∀pri ∈ PRRDO(5)
FOR ∀ti ∈ TDO(6)
IFW(pri, ti) > q(RMR.ri) THEN(7)
q(RMR.ri) ⟵ W(pri, ti);(8)
END IF(9)
END DO(10)
END DO(11)
Step 3: OutputRMR.The complexity of Algorithm2 is Ο(|PRR| × |T|), where |PRR| is the number of reusable resource types and |T| is the number of activities. For real-life emergency resource management, the cross-organization emergency response processes will break down because of shortage of reusable resources if RAR < RMR.


## 6.3. Reliable Reusable Resource Requirement

Even though we haveRAR ≥ RMR, resource conflicts may still exist during the execution of cross-organization emergency response processes because of resource dependency and limited available resources. This kind of conflicts may delay the execution time of the emergency process. Therefore, the reliable reusable resource vector of a CE-net, denoted as RRR = <q(r1), q(r2),…, q(rm)>, is introduced, where ri (i = 1, 2, …, n) refers to a kind of reusable resource and is represented as a resource place pri in PRR. Algorithm 3 shows how to compute RRR by taking as input a CE-net.Algorithm 3: Calculate the reliable reusable resource vector RRR.
Input: ΣCE = (P, T, F, α, β, W, M0), DependencySet and RMR.Output: RRR.(1)
/∗Step 1: initialization∗/(2)
Step 1: sum ⟵ 0,VRR ⟵ VMR;(3)
/∗Step 2: to obtain the reliable reusable resource vector∗/(4)
Step 2:FOR ∀pri ∈ PRRDO(5)
FOR ∀(ti, tj) ∈ DependencySet DO(6)
sum ⟵W(pri, ti) + W(pri, tj);(7)
IF sum > q(RRR.ri) THEN(8)
q(RRR.ri) ⟵ sum;(9)
END IF(10)
sum ⟵ 0;(11)
END DO(12)
END DO(13)
Step 3: OutputRRR.The complexity of Algorithm3 is Ο(|PRR| × |T|), where |PRR| is the number of reusable resource types and |T| is the number of emergency activities. If RAR ≥ RRR, there is no resource conflict during process execution; that is, potential resource conflicts are avoided as sufficient resources are provided to support parallel execution of activities in resource dependency.Theorem 1.
The proposed approaches to analyze resource requirements of cross-organization emergency response processes on the basis of CE-net have Ο(m × n) time complexity, where m is the number of resource types and n is the number of emergency activities.Proof.
To analyze the resource requirement, three kinds of resource metrics, that is, the minimum consumable resource vector, the minimum reusable resource vector, and there liable reusable resource vector, are needed. Their calculation algorithms are implemented in Algorithms1–3, the complexity of which is no bigger than Ο(m × n), where m is the number of resource types and n is the number of emergency activities. Therefore, the proposed method to analyze the resource requirement has its Ο(m × n) time complexity.
Taking the cross-organization fire emergency response processes as an example, we haveRMC = <6>, RMR = <1, 1, 2, 1>, and RRR = <3, 2, 6, 1> by executing Algorithms 1–3.


## 7. Two Effective Resource Allocation Strategies

In this section, we propose two optimized resource allocation strategies, that is, the minimum execution time strategy and the minimum resource consumption strategy. The former pursues time efficiency of cross-organization emergency response processes, and the latter focuses on high resource utilization rate. For each strategy, we estimate its corresponding time performance, based on which the stakeholder can determine which strategy is suitable according to the timing constraints. Before rendering the detailed strategies, we first introduce the time performance estimation and resource conflict detection approaches.


### 7.1. Time Performance Estimation and Potential Resource Conflict Detection

In a cross-organization emergency response processes scenario, an emergency activity starts to be executed only (1) after the termination of all its preactivities, (2) after receiving the required messages sent by other organizations, and (3) under the condition that all of its required resources are available and sufficient. In this subsection, the minimum execution time of a cross-organization emergency response process can be obtained.Without considering resource factor, if each emergency activity is completed in its minimum execution time, the earliest time to start activityt, denoted by Te1(t), is as follows:(1)Te1t=0,t••=∅,maxTe1t′+αt′|t′∈t••,otherwise.Without considering resource factor, if each activity is completed in its maximum execution time, the earliest time to start activityt, denoted byTe2(t), is as follows:(2)Te2t=0,t••=∅,maxTe2t′+βt′|t′∈t••,otherwise.The minimum execution time of a cross-organization emergency response process can be found if no resource conflict occurs. However, resource conflicts are inevitable during the execution of a cross-organization emergency response process. Therefore, resource conflict checking approach is investigated here.In the following discussion, we useTstart(t) and Tend(t) to represent the real start and end time of an emergency activity t. We have two types of resources, reusable and consumable ones. The former one becomes available and can be reused after being released, while the latter is consumed during execution and cannot be reused. For this reason, resource conflict mentioned in our work is essentially caused by the reusable resources. If a conflict is caused by consumable resources, the only way to solve it is to add more such type resources.Definition 5.
∀ti, tj ∈ T(ti ≠ tj), ti and tj have resource dependency, denoted as ti Θ tj, if •(ti) ∩ •(tj) ⊆ PR.
According to Definition5, an algorithm to obtain the resource dependency in a cross-organization emergency response process is presented as follows.
In Algorithm4, the complexity of Step 2 is Ο(|T|2). Therefore, the complexity of Algorithm 3 is Ο(|T|2). By executing Algorithm 4, the resource dependency set of the emergency response process scenario is obtained: DependencySet = {(t2, t10), (t4, t5), (t4, t6), (t5, t6), (t18, t23), (t17, t22)}. Here, if two activities have resource dependency; that is, they share same emergency resources. However, this does not necessarily mean that resource conflicts will occur between them. Only when these two activities need to be executed simultaneously will resource conflicts take place. In the following, the resource conflict between two emergency activities is formulized.Algorithm 4: Detecting resource dependency.
Input: ΣCE = (P, T; F, α, β, W, M0)Output: DependencySet = {(ti, tj)|ti Θ tj}.(1)
/∗Step 1: initialization∗/(2)
Step 1: DependencySet ⟵ ∅;(3)
/∗Step 2: to detect resource dependency among emergency tasks∗/(4)
Step 2:FOR ∀ti, tj ∈ T (ti ≠ tj) DO(5)
IF •(ti) ∩ •(tj) ⊆ PRTHEN(6)
DependencySet ⟵ DependencySet ∪ {(ti, tj)};(7)
END IF(8)
END DO(9)
Step 3: Output DependencySet.Definition 6.
∀ti, tj ∈ T(ti ≠ tj), ti and tj are in potential resource conflict, denoted as ti ⊗ tj, if (1) ti Θ tj and (2) [Tstart(ti), Tend(ti)] and [Tstart(tj), Tend(tj)] are overlapping.
Definition6 defines the potential resource conflicts, based on which we present an algorithm to check resource conflicts.
In Algorithm5, because Ο(|ConflictSet|) ≤ Ο(|T|), the complexity of Step 2 is Ο(|T|). Hence, Algorithm 5 has its computational complexity Ο(|T|). By executing Algorithm 5, we can obtain that ConflictSet = {(t4, t5), (t4, t6), (t5, t6), (t18, t23), (t17, t22)}. However, even if t4 and t5 are in potential conflicts, t4 requires 2 public communication devices, and t5 also requires 2 public communication devices and if the total number of available investigators in this case is less than 4, conflict occurs because of the competition for public communication devices. If the total number of available investigators is more than 4, t4 and t5 will no longer be in conflict. Based on the aforementioned analysis, we can see that whether a cross-organization emergency response process can be accomplished in its ideal execution time depends on the total quantity of available resources. In this way, effective resource allocation strategies are needed to support its successful execution.Algorithm 5: Checking resource conflicts.
Input: ΣCE = (P, T; F, α, β, W, M0) and DependencySet.Output: ConflictSet = {(ti, tj)|ti ⊗ tj}.(1)
/∗Step 1: initialization∗/(2)
Step 1: ConflictSet ⟵ DependencySet,Te1(t) ⟵ 0, Te2(t) ⟵ 0, Tl1(t) ⟵ 0, Tl2(t) ⟵ 0;(3)
/∗Step 2: to detect if time interval of tasks with resource dependency overlaps∗/(4)
Step 2:IF ConflictSet ≠ ∅ THEN(5)
For ∀(ti, tj) ∈ ConflictSet DO(6)
CalculateTe1(ti), Te2(ti), Te1(tj), Te2(tj);(7)
IF [Te1(ti), Te2(ti) + β(Ti)] ∩ [Te1(tj), Te2(tj) + β(tj)] ≠ ∅ THEN(8)
GOTO Step3;(9)
ConflictSet ⟵ ConflictSet − {(ti, tj)};(10)
END DO(11)
END IF(12)
Step 3: Output ConflictSet.


### 7.2. Minimum Execution Time Strategy

A cross-organization emergency response process is a real-time service, where timeliness is critical to its mission success. Thus, to maintain a cross-organization emergency response process finish in a high time performance, parallel executions of independent emergency activities are needed to reduce the whole execution time. In the last subsection, ideal execution duration is analyzed for this scenario. To achieve this goal, the consumable and reusable resource vectors,VAC and VAR, should be allocated as VAC ≥ VMC and VAR ≥ VRR. In this resource allocation condition, consumable resources can meet the minimum requirement and reusable resources are sufficient enough to support parallel executions and avoid potential resource conflicts. Therefore, the whole process can be finished in its minimum execution interval.Definition 7.
For a time interval Interval = [Tl, TU], it is defined as the minimum execution duration of a ΣEC = (P, T, F, α, β, W, M0) if Tl = max{Te1(ti) + α(ti)|ti ∈ T} and Tu = max{Te2(ti) + β(ti)|ti ∈ T}.
According to the above-mentioned formulas (1) and (2), Te1(p) and Te2(p) of each activity in Figure 6 can be obtained and are shown in Table 5. From Table 5, we can obtain the ideal execution time for the cross-organization fire emergency response process, that is, if no resource conflict occurs, the minimum execution interval is [64, 107], where Tl = Te1(t14) + α(t14) = 61 + 3 = 64 time units and Tu = Te2(t14) + β(t14) = 102 + 5 = 107 time units.Table 5
Te1(p) and Te2(p) of each Task in Figure 6.
Activityt1t2t3t4t5t6t7t8t9t10Te1(t)0259991722522Te2(t)0491616163038938Activityt11−12−13t14t15t16t17t18t19−20−21t22t23t24−25−26−27−28Te1(t)46612529232529432528Te2(t)751024352674349694348


### 7.3. Minimum Resource Consumption Strategy

To finish an emergency response process with the smallest resource consumption, the optimized consumable and reusable resource vectors,VAC and VAR, should be allocated as VAC ≥ VMC and VAR ≥ VMR. In this resource allocation condition, both consumable and reusable resources can meet their minimum requirements. Therefore, the whole process can be finished with the smallest resource consumption. However, resource conflicts may exist during the process execution. Thus, some activities in conflict may be postponed because of waiting for reusable emergency resources which are exclusively occupied by others. As a result, time performance of the emergency response process is affected. Next, Algorithm 6 is proposed to estimate the execution duration for this case.Algorithm 6:Calculate the execution duration.
Input: ΣCE = (P, T; F, α, β, W, M0), ConflictSet, Interval.Output: M_Interval = [Ml, MU](1)
/∗Step 1: initialization∗/(2)
Step 1:Ml ⟵ Tl, MU ⟵ TU;(3)
/∗Step 2: to obtain the maximum execution time∗/(4)
Step 2:FOR ∀(ti, tj) ∈ ConflictSet DO(5)
Ml ⟵ Ml + min{α(ti), α(tj)};(6)
MU ⟵ MU + min{β(ti), β(tj)};(7)
END DO(8)
Step 3: OutputM_Interval.The complexity of Algorithm6 is Ο(|T|), where |T| is the number of emergency activities. By executing Algorithm 6 by taking the timing information of the cross-organization emergency response process as an example, we can obtain that its execution duration is [64, 107] using minimum resource consumption strategy.


## 7.1. Time Performance Estimation and Potential Resource Conflict Detection

In a cross-organization emergency response processes scenario, an emergency activity starts to be executed only (1) after the termination of all its preactivities, (2) after receiving the required messages sent by other organizations, and (3) under the condition that all of its required resources are available and sufficient. In this subsection, the minimum execution time of a cross-organization emergency response process can be obtained.Without considering resource factor, if each emergency activity is completed in its minimum execution time, the earliest time to start activityt, denoted by Te1(t), is as follows:(1)Te1t=0,t••=∅,maxTe1t′+αt′|t′∈t••,otherwise.Without considering resource factor, if each activity is completed in its maximum execution time, the earliest time to start activityt, denoted byTe2(t), is as follows:(2)Te2t=0,t••=∅,maxTe2t′+βt′|t′∈t••,otherwise.The minimum execution time of a cross-organization emergency response process can be found if no resource conflict occurs. However, resource conflicts are inevitable during the execution of a cross-organization emergency response process. Therefore, resource conflict checking approach is investigated here.In the following discussion, we useTstart(t) and Tend(t) to represent the real start and end time of an emergency activity t. We have two types of resources, reusable and consumable ones. The former one becomes available and can be reused after being released, while the latter is consumed during execution and cannot be reused. For this reason, resource conflict mentioned in our work is essentially caused by the reusable resources. If a conflict is caused by consumable resources, the only way to solve it is to add more such type resources.Definition 5.
∀ti, tj ∈ T(ti ≠ tj), ti and tj have resource dependency, denoted as ti Θ tj, if •(ti) ∩ •(tj) ⊆ PR.
According to Definition5, an algorithm to obtain the resource dependency in a cross-organization emergency response process is presented as follows.
In Algorithm4, the complexity of Step 2 is Ο(|T|2). Therefore, the complexity of Algorithm 3 is Ο(|T|2). By executing Algorithm 4, the resource dependency set of the emergency response process scenario is obtained: DependencySet = {(t2, t10), (t4, t5), (t4, t6), (t5, t6), (t18, t23), (t17, t22)}. Here, if two activities have resource dependency; that is, they share same emergency resources. However, this does not necessarily mean that resource conflicts will occur between them. Only when these two activities need to be executed simultaneously will resource conflicts take place. In the following, the resource conflict between two emergency activities is formulized.Algorithm 4: Detecting resource dependency.
Input: ΣCE = (P, T; F, α, β, W, M0)Output: DependencySet = {(ti, tj)|ti Θ tj}.(1)
/∗Step 1: initialization∗/(2)
Step 1: DependencySet ⟵ ∅;(3)
/∗Step 2: to detect resource dependency among emergency tasks∗/(4)
Step 2:FOR ∀ti, tj ∈ T (ti ≠ tj) DO(5)
IF •(ti) ∩ •(tj) ⊆ PRTHEN(6)
DependencySet ⟵ DependencySet ∪ {(ti, tj)};(7)
END IF(8)
END DO(9)
Step 3: Output DependencySet.Definition 6.
∀ti, tj ∈ T(ti ≠ tj), ti and tj are in potential resource conflict, denoted as ti ⊗ tj, if (1) ti Θ tj and (2) [Tstart(ti), Tend(ti)] and [Tstart(tj), Tend(tj)] are overlapping.
Definition6 defines the potential resource conflicts, based on which we present an algorithm to check resource conflicts.
In Algorithm5, because Ο(|ConflictSet|) ≤ Ο(|T|), the complexity of Step 2 is Ο(|T|). Hence, Algorithm 5 has its computational complexity Ο(|T|). By executing Algorithm 5, we can obtain that ConflictSet = {(t4, t5), (t4, t6), (t5, t6), (t18, t23), (t17, t22)}. However, even if t4 and t5 are in potential conflicts, t4 requires 2 public communication devices, and t5 also requires 2 public communication devices and if the total number of available investigators in this case is less than 4, conflict occurs because of the competition for public communication devices. If the total number of available investigators is more than 4, t4 and t5 will no longer be in conflict. Based on the aforementioned analysis, we can see that whether a cross-organization emergency response process can be accomplished in its ideal execution time depends on the total quantity of available resources. In this way, effective resource allocation strategies are needed to support its successful execution.Algorithm 5: Checking resource conflicts.
Input: ΣCE = (P, T; F, α, β, W, M0) and DependencySet.Output: ConflictSet = {(ti, tj)|ti ⊗ tj}.(1)
/∗Step 1: initialization∗/(2)
Step 1: ConflictSet ⟵ DependencySet,Te1(t) ⟵ 0, Te2(t) ⟵ 0, Tl1(t) ⟵ 0, Tl2(t) ⟵ 0;(3)
/∗Step 2: to detect if time interval of tasks with resource dependency overlaps∗/(4)
Step 2:IF ConflictSet ≠ ∅ THEN(5)
For ∀(ti, tj) ∈ ConflictSet DO(6)
CalculateTe1(ti), Te2(ti), Te1(tj), Te2(tj);(7)
IF [Te1(ti), Te2(ti) + β(Ti)] ∩ [Te1(tj), Te2(tj) + β(tj)] ≠ ∅ THEN(8)
GOTO Step3;(9)
ConflictSet ⟵ ConflictSet − {(ti, tj)};(10)
END DO(11)
END IF(12)
Step 3: Output ConflictSet.


## 7.2. Minimum Execution Time Strategy

A cross-organization emergency response process is a real-time service, where timeliness is critical to its mission success. Thus, to maintain a cross-organization emergency response process finish in a high time performance, parallel executions of independent emergency activities are needed to reduce the whole execution time. In the last subsection, ideal execution duration is analyzed for this scenario. To achieve this goal, the consumable and reusable resource vectors,VAC and VAR, should be allocated as VAC ≥ VMC and VAR ≥ VRR. In this resource allocation condition, consumable resources can meet the minimum requirement and reusable resources are sufficient enough to support parallel executions and avoid potential resource conflicts. Therefore, the whole process can be finished in its minimum execution interval.Definition 7.
For a time interval Interval = [Tl, TU], it is defined as the minimum execution duration of a ΣEC = (P, T, F, α, β, W, M0) if Tl = max{Te1(ti) + α(ti)|ti ∈ T} and Tu = max{Te2(ti) + β(ti)|ti ∈ T}.
According to the above-mentioned formulas (1) and (2), Te1(p) and Te2(p) of each activity in Figure 6 can be obtained and are shown in Table 5. From Table 5, we can obtain the ideal execution time for the cross-organization fire emergency response process, that is, if no resource conflict occurs, the minimum execution interval is [64, 107], where Tl = Te1(t14) + α(t14) = 61 + 3 = 64 time units and Tu = Te2(t14) + β(t14) = 102 + 5 = 107 time units.Table 5
Te1(p) and Te2(p) of each Task in Figure 6.
Activityt1t2t3t4t5t6t7t8t9t10Te1(t)0259991722522Te2(t)0491616163038938Activityt11−12−13t14t15t16t17t18t19−20−21t22t23t24−25−26−27−28Te1(t)46612529232529432528Te2(t)751024352674349694348


## 7.3. Minimum Resource Consumption Strategy

To finish an emergency response process with the smallest resource consumption, the optimized consumable and reusable resource vectors,VAC and VAR, should be allocated as VAC ≥ VMC and VAR ≥ VMR. In this resource allocation condition, both consumable and reusable resources can meet their minimum requirements. Therefore, the whole process can be finished with the smallest resource consumption. However, resource conflicts may exist during the process execution. Thus, some activities in conflict may be postponed because of waiting for reusable emergency resources which are exclusively occupied by others. As a result, time performance of the emergency response process is affected. Next, Algorithm 6 is proposed to estimate the execution duration for this case.Algorithm 6:Calculate the execution duration.
Input: ΣCE = (P, T; F, α, β, W, M0), ConflictSet, Interval.Output: M_Interval = [Ml, MU](1)
/∗Step 1: initialization∗/(2)
Step 1:Ml ⟵ Tl, MU ⟵ TU;(3)
/∗Step 2: to obtain the maximum execution time∗/(4)
Step 2:FOR ∀(ti, tj) ∈ ConflictSet DO(5)
Ml ⟵ Ml + min{α(ti), α(tj)};(6)
MU ⟵ MU + min{β(ti), β(tj)};(7)
END DO(8)
Step 3: OutputM_Interval.The complexity of Algorithm6 is Ο(|T|), where |T| is the number of emergency activities. By executing Algorithm 6 by taking the timing information of the cross-organization emergency response process as an example, we can obtain that its execution duration is [64, 107] using minimum resource consumption strategy.


## 8. Conclusion

Efficient emergency resource allocation decision support is of vital importance for cross-organization emergency management. To some extent, this will influence emergency resource utility rate and the whole emergency mission success. In the work, we first propose CE-net to model a cross-organization emergency response process, based on which emergency resource allocation decision-making strategies, including minimum execution time strategy and minimum resource consumption strategy, are presented. According to the available emergency resources and emergency time constraint, certain strategy is selected by the emergency manager according to their specific requirements. It is proved that the minimum execution time strategy can ensure the global emergency response process execution without resource conflict or block, and therefore the performance is optimal.The minimum resource consumption strategy can guarantee the whole emergency to be finished with the least emergency consumption, and, in this way, the resource related cost is reduced. However, there may exist some resource conflicts during real-life emergency process execution when we choose the latter. To resolve these conflicts and maintain a success execution, efficient resource conflict resolution strategies are needed. Therefore, resource conflict resolution strategies with corresponding controller design approaches will be our future work. In addition, it would be interesting to discover such emergency response process models from historic emergency response logs by using process discovery techniques and advanced learning algorithms to realize data-driven emergency decision-making [38].



---

*Source: 7965935-2021-01-04.xml*