Modern industrial systems (no matter, global, regional, national, transnational etc.) are complicated, distributed, strongly interconnected networks of local facilities, producing, transporting and utilizing various products and resources. That’s why, – first of all, of the mentioned strong interconnectivity and associated with it multiple chain effects, – these systems are often vulnerable to natural disasters in such a way, that the one only facility destruction may cause consequences far beyond area or place this facility is located. So one of the most actual, important and at the same time difficult problems of the modern system analysis is development of the widely available mathematical toolkits, models and computer technologies, which would be able to provide the decision makers from the government and corporate stuffs with comprehensive and precise prognostic information about such consequences – first of all, would be system, affected by natural disaster impact (NDI), vulnerable or sustainable to it.
Industrial system (IS) in general case contains technological base (various industrial complexes and devices) producing (manufacturing) various objects (cars, computers, buildings etc.) and utilizing various resources (materials, microchips etc.), necessary for this process (Fig. 1a). Natural disaster destroys some segments of the technological and resource bases, that’s why amounts of objects produced are decreasing (Fig. 1b).
By this we may formulate criterion for IS robustness/vulnerability assessment (Fig. 2).
If amounts of objects, produced by IS before and after natural disaster impact, are equal, then IS is sustainable to the NDI; otherwise it is vulnerable to the impact. In the last case there is also one more important “reverse” problem: what part of the work may be executed by vulnerable IS, which facilities are affected by NDI?
Let us consider formulated problems in more details.
As was said higher, IS include industrial (manufacturing) devices (complexes). Each such device may be represented as a “black box” B with m inputs and one output (Fig. 3). Every i-th input is marked by a_{i} – name of object (item, resource) type, – and n_{i} – amount (volume, quantity) of this object. So n_{1} objects (of type) a_{1}, …, n_{m} objects (of type) a_{m} are required for one object (of type) a manufacturing.
IS as a whole may be represented by k such “black boxes” B_{1}, …, B_{k} interconnected by the “logistical ring” L, providing transport of objects, manufactured by devices, from their outputs to inputs of another devices, thus forming integrated manufacturing process (Fig. 4).
This process, however, is driven by orders, which sources are external systems or persons, consuming objects, produced by IS. Each order q in general case defines types and quantities of objects, which would be manufactured (n̄_{1} objects of type ā_{1}, …, n̄_{l} objects of type ā_{l} at Fig. 4). From the other side, IS itself consumes resources, which are represented at Fig. 4 as set I containing n_{l}_{1} objects (of type) a_{l}_{1}, …, n_{l}_{p} objects (of type) a_{l}_{p}. By this, IS along with order also may be considered as “black box”, i.e. device producing object q after being applied to initial resources set I. Any impact on IS eliminates some initial resources and devices entering this system, thus reducing its producing capability.
Let us underline, that there are no static interconnections between devices B_{1}, …, B_{k}, and structure, representing IS in the described manner, is not graph, usually considered as a canonical form of such systems description and modelling (Burkart, 1997; Mills and Dabrowski, 2006; Hespanha et al., 2007; Levin et al., 2009; Dabrowski and Hunt, 2011; Mills et al., 2012; Carreras et al., 2005; Mills et al., 2011; Lade and Gross, 2012; Scheffer, 2009; Sheffer et al., 2009; Dabrowski et al., 2011; D’Andrea and Dullerud, 2003; Dullerud and Paganini, 2005; Goh and Yang, 2002; Horn and Johnson, 1991; Jadbabiae et al., 2003; Klavins et al., 2006; Mesbahi and Egerstedt, 2010; Mills and Dabrowski, 2008; Olfati-Saber et al., 2007; Stewart, W 1994). Here every order completion provides its own tree, including manufacturing operations and transfers of their results among devices, incorporated to this process. Moreover, there may be a lot of variants of each order completion, by reason IS may contain devices manufacturing similar objects in different alternative ways. So, every order completion process generates, in fact, each own cooperation, or contracts set, providing necessary items manufacturing.
Described formalization is basic for direct and reverse problems, verbally formulated higher, primary consideration. But it is not sufficient for strict mathematical description and, further, necessary algorithms design. There would be some constructive mathematical toolkit providing solutions of mentioned problems. But multiple attempts of well-known general-purpose tools, based on vector-matrix calculus, graphs theory, Markovian chains, Petri nets etc. (Burkart, 1997; Mills and Dabrowski, 2006; Hespanha et al., 2007; Levin et al., 2009; Dabrowski and Hunt, 2011; Mills et al., 2012; Carreras et al., 2005; Mills et al., 2011; Lade and Gross, 2012; Scheffer, 2009; Sheffer et al., 2009; Dabrowski et al., 2011; D’Andrea and Dullerud, 2003; Dullerud and Paganini, 2005; Goh and Yang, 2002; Horn and Johnson, 1991; Jadbabiae et al., 2003; Klavins et al., 2006; Mesbahi and Egerstedt, 2010; Mills and Dabrowski, 2008; Olfati-Saber et al., 2007; Stewart, W 1994), application in the described area were not successful by reasons of problem’s dimension, difficulties of IS manufacturing process precise representation and computational complexity. This lead us to the new approach, which is, by our opinion, more flexible and simple in application to the large-scale IS representation, analysis and synthesis, as well as more efficient from the computational complexity point of view, especially in high-parallel computing environments. This new approach is strongly based on the recursive multisets (MS) theory (Sheremet, 2010, 2011) – more precisely, multiset grammars (MG), – that’s why is called “multigrammatical”. Multiset grammars, namely, one of their possible dialects, – constraint multiset grammars (CMG) – were at first proposed in (Marriott, 1994; Marriott and Meyer 1997; Marriott, 1996) as a tool for recognition of visual objects with complex structure. CMG may be also considered as one of the problem-oriented constraints logical programming languages (Marriott and Stucky, 1998; Apt, 2003; Fruhkwirth and Abdennadher, 2003).
Authors’ main contribution to this area are so called unitary multiset metagrammars (UMMG) (Sheremet, 2010, 2011; Sheremet and Zhukov, 2016), which are specific knowledge representation model, providing deep integration and convergence of classical optimization theory and modern knowledge engineering. As shown in (Sheremet, 2010, 2011; Sheremet and Zhukov, 2016), various subsets (subclasses) of UMMG provide efficient solution of various problems from system analysis and classical optimization areas.
Problem considered in this paper was announced in (Sheremet, 2016), and it is solved mainly by applying one of the simplest classes of UMMG family – unitary multiset grammars (UMG). Also general form multigrammars are applied to the mentioned reverse problem study.
We consider main results of UMG/MG application to the problem verbally formulated higher in a following way. Section 2 is dedicated to basic notions and definitions. Main elements of the approach (technological base, resource base, impact on industrial system) multiset/multigrammatical representation as well as IS sustainability (vulnerability) conditions are described in the Section 3, while Section 4 is dedicated to the NDI representation and mentioned conditions transformation to the corresponding form. Reverse problem concerning recognition of the abilities of the vulnerable IS is considered in Section 5. Inplementation issues are discussed in short in Section 6. Further directions of the development of multigrammatical approach practical applications are described at the conclusion.
According to (Calude et al., 2001; Petrovskiy, 2003; Banatre and Le Metoyer, 1993; Singh et al., 2007; Red’ko et al., 2015), multiset is set of so called multiobjects of the form n • a, that means there are n identical objects (of type) a, and that is written as
where ν is multiset name, n_{1} • a_{1}, …, n_{m} • a_{m} are multiobjects entering ν, and integer numbers n_{1}, …, n_{m} are called multiplicities of a_{1}, …, a_{m} objects, all of which are different. (1) means that there are n_{1} objects (of type) a_{1}, …, n_{m} objects (of type) a_{m} in multiset ν.
Unitary multiset grammar (UMG) is couple S = < a_{0}, R >, where a_{0} is title object, and R is scheme – set of the so called unitary rules (UR) of the form
where a object is called head and list n_{1} • a_{1}, …, n_{m} • a_{m} – body of the UR.
UMG were designed specially for the representation of hierarchical systems and objects, so the most valuable in the considered problem area is so called structural interpretation of the unitary rules. According to the structural interpretation, UR (2) means that object a consists of n_{1} objects a_{1}, …, n_{m} objects a_{m}.
Example 1. Let S = < car, R >, where R contains two URs:
car → 1 • frame, 1 • engine, 4 • door, 4 • wheel.
engine → 1 • motor, 1 • accumulator, 1 • transmission.
As seen, car consists from one frame, one engine, four doors and four wheels. Engine, in turn, contains motor, accumulator as well as transmission.▪
Technological interpretation of unitary rules is extension of the structural one in such a way that UR
represents not only structural components (spare parts) of the object a, which are multiobjects n_{1} • a_{1}, …, n_{m} • a_{m}, but also resources, necessary for assemblying object a from these components, and being multiobjects n′_{1} • b_{1}, …, n′_{k} • b_{k}.
Example 2. Let S = < car, R >, where R contains one UR:
car → 1 • frame, 1 • engine, 4 • door, 4 • wheel,
400 • kW, 300 • USD, 10 • mnt – asm – line.
Here first four multiobjects of the UR body are the same, as in the first UR in the example 1, while the last three multiobjects define amounts of electrical energy (400 kilowatt), money (300 dollars) and time (10 minutes of the assemblying line operation), which are necessary for assemblying car from its spare parts (frame, engine, 4 doors, 4 wheels).▪
Unitary multiset grammars define systems (devices, processes etc.) in the easily understood top-down manner, and result of UMG application is set of multisets, each containing multiobjects with multiplicities defining total amounts of specific elementary (non-decomposed) objects having place in the system (device) or utilized while its manufacturing. Degree of decomposition is regulated by the analyst applying this tool while problem solving.
To define formally UMG semantics, i.e. process of generation of set of multisets V_{S} represented by UMG S, we shall use some operations and relations on multisets (Sheremet, 2010, 2011; Petrovskiy, 2003). Lower +, – and * are symbols of multisets addition, subtraction and multiplication operations correspondingly, which are defined as follows:
Here symbols +, – and × denote usual arithmetic operations. In (4) we assume, that object a absence in multiset ν is equivalent to it’s zero-value multiplicity.
Lower we shall designate by β(ν) set of all objects having place in multiset ν (it is called multiset basis):
Symbol "⊆" denotes multisets inclusion relation, and, if ν′ ⊆ ν, then ν′ is called submultiset of ν. Formally
if
Also we shall use multisets intersection operation denoted by bold symbol “∩” and defined as follows:
As in (4), a ∉ ν and 0 • a ∈ ν are equivalent.
By A_{s} we shall designate set of all objects having place in UMG S = < a_{0}, R >, while by A̅_{s} – set of all terminal objects having place in S, i.e. objects which are not heads of unitary rules r ∈ R and present only in URs bodies. As seen,
Multiset ν ∈ V_{s} is called terminal multiset (TMS), if there is no one UR in the scheme R, which may be applied to ν, i.e. it contains only terminal objects. Set of terminal multisets (STMS) V̅_{s} ⊆ V_{s} is subset of V:
Strict mathematical definition of the UMG application, i.e. set of multisets generation process, which we shall use here, is as follows (Sheremet, 2010, 2011; Sheremet and Zhukov, 2016):
where UR a →n_{1} • a_{1}, …, n_{m} • a_{m} for unambiguity is represented in angle brackets, i.e. as < a →n_{1} • a_{1}, …, n_{m} • a_{m} >.
As seen, multisets generation is implemented by application to set of MS V_{(i)}, created at previous i steps, all unitary rules r ∈ R. In turn, every such UR is applied to all multisets ν ∈ V_{(i)} by special function π of two arguments, first being ν, and second – UR r in the form a →n_{1} • a_{1}, …, n_{m} • a_{m}. If ν contains multiobject n • a, it is replaced by multiset n*{n_{1} • a_{1}, …, n_{m} • a_{m}} (this, of course, is followed by summarizing multiplicities of identical objects in the MS sum). Otherwise result is empty multiset. The described iterative process in general case is infinite, and set of multisets, defined by UMG S = < a_{0}, R >, is it’s fixed point V_{(∞)}, while set of terminal multisets, defined by S, is subset of V_{S}, defined by (17).
Let us note, that from computational complexity point of view (14) may be transformed to
where ∃∈ means selection of any one multiobject n • a from multiset ν. That provides sharp reduction of generation computational complexity (Sheremet, 2010, 2011).
Here we shall consider only so called finitary UMG, which generate finite STMS (Sheremet, 2010, 2011).
UMG S = < a_{0}, R > is finitary, when there exists i such, that V_{(i+1)} = V_{(i)}, and if so, V_{(i)} = V_{S}. Problem of UMG finitarity recognition is algorithmically decidable (Sheremet, 2010, 2011).
Let us continue multigrammatical formalization of basic notions concerning the main subject of the paper.
Industrial system may be represented now by UMG S = < tb, R >, where tb (acronym from “technological base”) is title object, and R is set of unitary rules in technological interpretation. Order completed by industrial system may be represented by multiset $q=\{{n}_{1}^{q}\cdot {a}_{1}^{q},\dots \dots ,{n}_{l}^{q}\cdot {a}_{l}^{q}\}$ , and, evidently, resources amount, necessary for order q completion, is set of terminal multisets generated by UMG
i.e. V̅_{Sq} (for simplicity we shall use V̅_{q} instead of V̅_{Sq} lower). Because of possibility of multiple ways of some objects manufacturing, i.e. so called internal alternativity of S_{q} (Sheremet, 2010, 2011), there may be more than one TMS in V̅_{q}.
Example 3. Let S be the same, as in the previous example, and q = {3 • car }, i.e. IS must manufacture 3 cars. Then
S_{q} = < tbq, {< tbq → 3 • car >, < car →1 • frame, 1 • engine, 4 • wheel, 4 • chair,
400 • kW, 300 • USD, 10 • mnt –asm –line >} >,
(here UR are written in the angle brackets for unambiguity) and, as seen,
V̅_{s}_{q} = {{3 • frame, 3 • engine, 12 • wheel, 12 • chair, 1200 • kW, 900 • USD, 30 • mnt – asm – line }}. ▪
Resource base of industrial system may be represented by multiset, which multiobjects define amounts of objects, being available for technological base. Evidently, resource base ν is sufficient for order q completion by IS S = < tb, R >, if there exists at least one set of resources amounts, necessary for this completion, being submultiset of ν:
Example 4. Resource base
ν = {4 • frame, 3 • engine, 15 • wheel, 12 • chair, 1500 • kW, 1200 • USD, 50 • mnt – asm – line}
is sufficient for order q from the example 3 completion, while resource base
ν = {1 • frame, 3 • engine, 15 • wheel, 12 • chair, 1500 • kW, 1200 • USD, 50 • mnt – asm – line}
is not sufficient, because number of frames having place in the resource base, i.e. one, is less than it is necessary for 3 cars assemblying, i.e. three, although all other resources amounts are sufficient (they even exceed necessary values).▪
Impact on industrial system may be represented as multiset Δν, which defines resources amount eliminated from the resource base of IS, so the last after impact would be ν–Δν.
All introduced notions and definitions provide formulation of the condition of IS sustainability/vulnerability to impact.
Let resource base ν is sufficient for order q completion by IS S = < tb, R >, i.e. it satisfies (20). Then IS S completing order q with resource base ν is sustainable to impact Δν, if
Otherwise IS S is vulnerable to impact Δν.
Example 5. IS S = < tb, R > from example 3, completing order q = {3 • car} with resource base from example 4, sufficient for this order completion, is sustainable to impact
Δν = {3 • wheel, 2 • chair, 300 • kW, 100 • USD, 5 • mnt – asm – line}
because resource base after impact
ν–Δν = {4 • frame, 3 • engine, 12 • wheel, 10 • chair, 1200 • kW, 1100 • USD, 45 • mnt – asm – line}
is sufficient for completion. At the same time this IS is vulnerable to impact
Δν = {1 • engine },
because resource base after impact
ν = {4 • frame, 2 • engine, 15 • wheel, 12 • chair, 1500 • kW, 1200 • USD, 50 • mnt – asm – line}
is not sufficient for completion (number of engines is less than necessary).▪
Until now we have considered impacts without their specific features. Natural disaster impacts most general feature is their localization, i.e. connection with some fixed areas (points) affected by the NDI. However, any information about technological base, as well as resource base, elements locations, in the considered higher UMG representation of industrial systems is not included.
Let us extend unitary rules in technological interpretation by geospatial information in such a way, that every object, having place in UR, would have form a/z, where z is locator defining area (point), where this object presents, and “/” is divider, which is not used anywhere in a and z strings. So UR would have the following form:
that means object a at location z may be produced (assembled) if there are n_{1} objects a_{1} at location z_{1}, …, n_{m} objects a_{m} at location z_{m}. (Objects like a/z, a_{1}/z_{1}, …, a_{n}/z_{n} are called “composite objects”, or “composits”).
Similarly, we shall extend resource base and order representation, which would become respectively
After that there is a simplest way for NDI representation, namely, by the set Z = {z_{1}, …, z_{k}}, of locations destroyed by this NDI completely. Corresponding relation for NDI in the multiset form is constructed directly:
and
From (23)–(24) and Z definition we may write the condition of IS sustainability/vulnerability, which is evident generalization of (21). If
then IS S = < tb, R >, completing order with resource base ν, is sustainable to NDI Z. Otherwise IS is vulnerable to Z.
Example 6. Let us consider IS, which resource base is
ν = {10 • a_{1}/z_{1}, 5 • a_{2}/z_{2}, 19 • a_{3}/z_{3}, 7 • a_{4}/z_{4}},
technological base is represented by scheme R containing two unitary rules
a/z_{1} → 3 • a_{1}/z_{1}, 2 • a_{2}/z_{2}, 7 • a_{3}/z_{3},
a/z_{1} → 2 • a_{2}/z_{2}, 3 • a_{4}/z_{4},
and order q completed by this IS is q = {2 • a_{1}/z_{1}}.
Natural disaster impact Z = {z_{3}} causes destruction of subset of the resource base, located at z_{3}, so according to (25),
Δν(Z) = {19 • a_{3}/z_{3}},
and
ν–Δν(Z) = {10 • a_{1}/z_{1}, 5 • a_{2}/z_{2}, 7 • a_{4}/z_{4}}.
As seen,
V̅_{q} = {ν_{1}, ν_{2}},
where
ν_{1} = {6 • a_{1}/z_{1}, 4 • a_{2}/z_{2}, 14 • a_{3}/z_{3}},
ν_{2} = {4• a_{2}/z_{2}, 6 • a_{4}/z_{4}},
and
ν_{1} ⊈ ν – Δν(Z),
ν_{2} ⊈ ν – Δν(Z),
that’s why IS is sustainable to NDI Z.▪
Note, that NDI may destruct facilities not always completely, but very often partially. In this case some objects located at the area, affected by the NDI, may remain in the undestructed state and thus may be used elements for manufacturing some products.
This case may be represented in the direct manner:
that provides use of condition (27) for the IS sustainability/vulnerability assessment.
Example 7. Let us consider IS from the previous example 7, and NDI, partially destructing locations z_{3} and z_{4}, so that
Δν(Z) = {12 • a_{3}/z_{3}, 2 • a_{4}/z_{4} },
and
ν–Δν(Z) = {10 • a_{1}/z_{1}, 5 • a_{2}/z_{2}, 7 • a_{3}/z_{3}, 5 • a_{4}/z_{4}}.
As seen, because of
ν_{1} ⊈ ν – Δν(Z)
ν_{2} ⊈ ν – Δν(Z)
IS is vulnerable to NDI Δν(Z).▪
Let us consider the case, when IS R, completing order q with resource base ν, is vulnerable to NDI (Z or Δν(Z)).
The question is as follows: what part of order q may be completed by IS R affected by NDI Z?
Simple, but, however, non-evident approach to this question consideration is based on the general form multiset grammars use for constructing the solution.
Multiset grammar is couple S = < ν_{0}, R >, where ν_{0} is multiset called kernel, and R is, as in the UMG, scheme, which elements are called rules, which structure is
where ν and ν′ are multisets. Semantics of multigrammars is similar to UMG semantics (Sheremet, 2010, 2011):
As seen, MG provides generation of new multisets from already generated, beginning from the kernel, by replacement of their submultisets in accordance with rules having place in the scheme. Generation is executed until it is possible, so, in general case, V_{S} and V̅_{S} may be infinite. However, if there exists i such, that V_{(i)} = V_{(i+1)}, then V_{(i)} = V_{S}, then both V_{S} and V̅_{S} are finite sets, and MG is finitary.
Let us consider UMG S = < tb, R >, representing IS with technological base R, and this IS resource base ν. Multiset grammar ${S}_{\nu}^{*}=<\nu ,{R}^{*}>$ will be called dual to unitary multiset grammar S = < tb, R >, if
i.e. every unitary rule a →n_{1} • a_{1}, …, n_{m} • a_{m} having place in the UMG S scheme R is substituted by one and the only one “mirror” rule in MG ${S}_{\nu}^{*}$ scheme R*.
As may be seen, set of multisets ${V}_{{S}_{\nu}^{*}}$ , generated by MG ${S}_{\nu}^{*}$ , contains all variants of production, which may be manufactured by IS S, beginning from the resource base ν. Set of variants of order q partial completion is, thus, subset of set generated by MG ${S}_{\nu}^{*}$ , each TMS of which contains at least one object from q order (here and lower we denote mentioned set of variants as V (R, ν, q)):
As a consequence, total set of solutions of the reverse problem is
Example 8. Let us consider IS with the same scheme R and resource base ν as in the previous examples 7 and 8, completing order q = { 3 • a/z_{1}}, and being affected by the same NDI Δν(Z) as in the example 8. Kernel ν_{0} of MG S* = < ν_{0}, R*>, dual to UMG S = < tb, R >, is
ν_{0} = ν– Δν(Z) = {10 • a_{1}/z_{1}, 5 • a_{2}/z_{2}, 7 • a_{3}/z_{3}, 5 • a_{4}/z_{4}},
while rules are
r_{1} ≡ {3 • a_{1}/z_{1}, 2 • a_{2}/z_{2}, 7 • a_{3}/z_{3}} → {1 • a/z_{1}},
r_{2} ≡ {2 • a_{2}/z_{2}, 3 • a_{4}/z_{4}} → {1 • a/z_{1}},
r_{2} ≡ {3 • a/z_{1}} → {1 • tbq}.
According to (36),
V (R, ν– Δν(Z), q) = {ν_{1}, ν_{2}, ν_{3}},
where
ν_{1} = {7 • a_{1}/z_{1}, 3 • a_{2}/z_{2}, 5 • a_{4}/z_{4}, 1 • a/z_{1}},
ν_{2} = {5 • a_{1}/z_{1}, 3 • a_{2}/z_{2}, 2 • a_{4}/z_{4}, 2 • a/z_{1}},
ν_{3} = {10 • a_{1}/z_{1}, 3 • a_{2}/z_{2}, 7 • a_{3}/z_{3}, 2 • a_{4}/z_{4}, 1 • a/z_{1}}.
As seen, ν_{1} is result of application of r_{1} to ν_{0}; ν_{2} – result of application of r_{2} to ν_{1}; while ν_{3} is result of application of r_{2} to ν_{0}.
So, a valuable part of the order (2 of 3 objects a located at z_{1}) may be completed by the affected IS, and even some valuable part of the resource base would remain after following this way of order completion.▪
However, in general case some of multisets entering set V (R, ν – Δν(Z), q) may be of no practical use (as ν_{1} and ν_{3} in the previous example 8), because the only purpose of the assessment is to get the best (“valuable” in the common sense) variants of order completion, which are not improvable from the practical point of view.
To filter STMS, constructed in accordance with (37), we shall define one useful function max, which value max(V) is subset of V including only so called non-dominated multisets entering V:
i.e. there is no one multiset in max(V) ⊆ V, which is submultiset of some other multiset entering V; max(V) is thus set of maximal elements of V.
Example 9. Let V = {ν_{1}, ν_{2}, ν_{3}, ν_{4}}, where
ν_{1} = {3 • a_{1}, 2 • a_{2}, 1 • a_{3}},
ν_{2} = {1 • a_{1}, 2 • a_{2}},
ν_{3} = {2 • a_{1}, 1 • a_{3}},
ν_{4} = {1 • a_{1}, 3 • a_{2}}.
As may be seen, according to (38), because of ν_{2} ⊆ ν_{1}, ν_{3} ⊆ ν_{1}, max(V) = {ν_{1}, ν_{4}}. ▪
From here set of valuable (“precise”) solutions of reverse problem, denoted V̅ (R, ν– Δν(Z), q) may be constructed in a following evident way:
As seen, set of valuable solutions includes those only intersections of elements of V (R, ν– Δν(Z), q) and q order, which are non-dominated multisets.
Example 10. Consider V (R, ν– Δν(Z), q) = {ν_{1}, ν_{2}, ν_{3}} and q = { 3 • a/z_{1}} from Example 9. According to (39),
V̅ (R, ν – Δν(Z), q) = max ({ν_{1} ∩ q, ν_{2} ∩ q, ν_{3} ∩ q}) =
= max ({{1 • a/z_{1}}, {2 • a/z_{1}}, {∅}}) = {{2 • a/z_{1}}}.▪
Note, that general form multigrammars application instead of unitary MG provides generation of all possible variants of work distribution between alternative facilities (devices), not only monopolial ones. However, this opportunity as a consequence leads to sensitive increasing of computational complexity of generation mentioned. Theory and implementation of this complexity reduction would be considered in separate publications.
Software implementation of IS sustainability assessment (“direct problem”) employs knowledge base (R set of unitary rules) representation and storage in a form of data base, which elements are selected by means of NoSQL-like (McCreary and Kelly, 2013; Vaish, 2013) query language.
Data base mentioned is set of records being couples of the form < a, B >, where a is object (key of the record) while B is set of bodies of unitary rules, which head is a:
where
so that (40)–(41) represent m unitary rules
While generation, set B is selected from data base by query, which processing is implemented by special function READ (a). Similarly, insertion of new unitary a→w to the knowledge base is implemented by function INSERT (a, w), as well as UR a→w deletion from KB (DB) is implemented by function DELETE (a, w). Also there is function DELALL (a), eliminating from KB all unitary rules with head a, i.e. deletion from data base record <a, B>, where B is current set of bodies of URs with head a.
Associative internal organization of the described data base along with physical blocks cash, supporting DB management via virtual memory space, provides fast execution of functions mentioned without redundant search (Sheremet, 2013).
Software implementation of assessment of part of the order, which may be completed by the affected vulnerable IS (“reverse problem”) employs knowledge base (scheme R* of MG, dual to the initial UMG) representation and storage in a form of data base similar to the considered higher.
However, this data base contains records of two types:
Example 11. Let dual UMG R* contains following “mirror” rules:
r_{1}: {3 • a_{1}, 2 • a_{2} } → {1 • a_{3}},
r_{2}: {2 • a_{1}, 5 • a_{3}} → {1 • a_{0}}.
Then corresponding data base will contain following records:
< r_{1}, {<a_{1}, 3>, <a_{2}, 2>}, a_{3}>,
< r_{2}, {<a_{1}, 2>, <a_{3}, 5>}, a_{0}>,
< a_{1}, {<r_{1}, 3>, <r_{2}, 2>} >,
< a_{2}, {<r_{1}, 2>} >,
< a_{3}, {<r_{2}, 5>} >.▪
As may be seen, quantity of records of the first type is |R*|=|R| while quantity of records of the second type is equal to number of objects having place in left parts of rules entering R*.
Records of the first type are used while generation of the TMS (i.e. solutions) set in accordance with (36)-(38) by application of “mirror” rules. If this would be done without any improvements, there would be full search of all |R*| rules at every generation step in order to apply some of them to the current multiset, generated while previous steps execution. So for practically interesting knowledge bases with |R*|, beginning from 10^{5}–10^{6}, direct implementation of generation algorithmics is unreal. To avoid this principal difficulty, records of the second type are introduced. They are stored and selected by key (object a) in such a way, that by one access to data base identifiers of all “mirror” rules, which possibly may be applied to current multiset by reason there is multiobject n • a in their left parts, and n ≤ m, where m • a enters current multiset. This techniques provides cut-off all the rest “mirror” rules, non-applicable to this MS by reason of object a absence in their left parts. There are several implementations of this basic idea, and they would be considered separately.
Described approach to software implementation of the proposed algorithmics is somewhat efficient from the practical point of view, that is verified by real software-intensive IS management experience (Sheremet, 2005; Sheremet, 2005; Karasev and Sheremet, 2008). Such software operates CALS-originated knowledge bases, which contain structural descriptions of all types of objects, manufactured by various facilities, entering distributed IS. Due to “granularity” of the described knowledge representation, all accumulation and correction of such KB from the distributed local sources is performed without any difficulties in the online regime. Assessment of the possibility of orders completion at moments, when they enter IS, is performed in soft real time mode (minutes per message) on knowledge bases containing 10–12 mln. unitary rules with 2–3 mln. type of objects (items) used and manufactured by the industrial system, and this mode does not require special-purpose or high-parallel hardware. Reverse problem software is activated, when various impacts like manufacturing equipment malfunctions and necessary resources delays occur, and is solved on the same hardware in practically the same time scale. More detailed description of the UMG toolkit software implementation in various hardware environments may be object of the special paper.
Multigrammatical approach shortly presented in the paper may be efficiently used for the assessment of consequences of natural disasters impacts (as well as human-implemented impacts) on large-scale industrial systems, no matter what production they are manufacturing, what infrastructure they use, what kind of producing devices they contain etc., due to the generality and flexibility of MG/UMG toolkit used for the assessment.
The main four directions of further development of the approach, in our opinion, are:
The first direction background is following. As it is easy to see, multigrammatical approach is strongly based on the additivity of quantities of objects represented by their multiplicities. However, time is additive only in consideration to one processing (manufacturing) unit (for example, assemblying line): if there are two or more such units, they may operate in parallel, that’s why total work may be completed by the system faster than in the sequential mode with additive time operating. Temporal MG/UMG are such generalization of the considered higher mathematical tools, that provide simple description of industrial systems and their elements extended by time intervals which are necessary to these elements to execute operations. Basic construction of temporal unitary multiset grammar is so called temporal unitary rule of the form
where t is fixed object denoting time measurement unit (for example, minute) while n multiplicity is duration of time interval (number of t objects), necessary for assemblying a object by utilizing n_{1} units of resource a_{1}, …, n_{m} units of resource a_{m}. This extension provides as a final purpose construction of Gantt diagrams charts of manufacturing (production) processes evolving all devices which are necessary for order completion, that’s why temporal MG/UMG algorithmics is in fact algorithmics of optimal (rational) scheduling (Conway et al., 2003; Hermann, 2006). It is much more deep and sophisticated in comparison with MG/UMG, however, providing practically useful generalization of well known scheduling problems and their solutions.
The second of the listed directions is from the practical point of view very important, because it provides end users (decision makers) with the opportunity to prepare to possible NDI before they really occur.
The third direction, being quite evident, follows from the non-procedural, declarative representation of the knowledge about industrial systems and their operation items. “Granularity” of multigrammatical knowledge bases provides easy, in fact, “additive” accumulation of knowledge as well as its correction.
However, like any other knowledge representation model, MG/UMG need special algorithmics providing minimization of redundant search while multisets generation, especially for the so called filtering MG/UMG (Sheremet, 2010, 2011; Sheremet and Zhukov, 2016; Sheremet and Zhukov, 2016). This direction is, perhaps, most critical, because it eliminates or mitigates sharp growth of redundant generation steps, which reason is well-known combinatorial explosion while knowledge base volume expansion. There would be combination of two basic approaches for such kind of problems solution: redundant steps elimination by some smart cutting-off conditions exploitation at maximal early stages of multisets generation, and “brutal force” application by parallel generation of alternative branches on asynchronously operating processor units. State of the art in this area is described in (Sheremet 2010, 2011).
The most general is, in our opinion, the fourth direction. As may be easily estimated, real large-scale industrial systems technological bases and IS production (manufactured objects) would be represented by UMG knowledge bases containing millions and millions unitary rules. Creating, maintaining and utilizing such amounts of knowledge is a great problem being the next step of computer technologies application after Big Data, which are in fact everyday reality, however, not yet understood (Roberts, 2016) (as may be seen from section V, when UMG are used, then Big Knowledge is implemented by Big Data tools). In many considerations, it would be a new way of thinking, which must lead us to the new understanding of the global technosphere as an interconnected set of devices, joined with one another by information infrastructure (that’s already “Internet of Things”) and logistical networks. Such understanding, in turn, may optimize humanity behavior and its relations with the nature.
Author is grateful to Prof. Alexey Gvishiani and Prof. Pavel Kabat for permanent support, and also to reviewers, which advices contributed to the quality of the manuscript. Author extends sincere appreciation to Prof. Fred Roberts for useful discussions.
The author has no competing interests to declare.
Igor Sheremet, Doct. Eng. Sci., Professor, Corresponding Member of Russian Academy of Science (RAS). Head of the department of Financial University under the Government of Russian Federation, deputy director for science of Russian Foundation for Basic Research. Works at areas of theoretical and applied computer science, systems analysis, data and knowledge engineering, robotics, cybersecurity. Vice-chairman of RAS Board on Robotics and Mechatronics, member of RAS Systems Analysis Committee, official member of the Scientific Advisory Committee of International Institute of Applied Systems Analysis (IIASA) at Laxenburg (Austria).
Apt, K 2003 Principles of Constraints Programming. Cambridge University Press, p. 420. DOI: https://doi.org/10.1017/CBO9780511615320
Banatre, J-P and Le Metoyer, D 1993 Programming by Multiset Transformation. Communications of the ACM, 36(1): 98–111. DOI: https://doi.org/10.1145/151233.151242
Burkart, O 1997 Automatic Verification of Sequential Infinite-State Processes. Lecture Notes in Computer Science, Vol. 1354, p. 163. DOI: https://doi.org/10.1007/3-540-69678-4
Calude, C S, Păun, G, Rozenberg, G and Salomaa, A 2001 Multisets Processing: Mathematical, Computer Science and Molecular Computing Points of View – Lecture Notes in Computer Science, Vol. 2235. NY: Springer, p. 359. DOI: https://doi.org/10.1007/3-540-45523-X
Carreras, B, Lynch, V, Dobson, J and Newman, D 2005 Critical Points and Transitions in Electric Power Transmission Model for Cascading Failure Blackouts. Chaos, 12(4): 985–994. DOI: https://doi.org/10.1063/1.1505810
Conway, R W, Maxwell, W L and Miller, L W 2003 Theory of Scheduling (Second Edition). Dover Publications, p. 304.
D’Andrea, R and Dullerud, G 2003 Distributed Control Design for Spatially Interconnected Systems. IEEE Transactions on Automatic Control, 48(9): 1478–1495. DOI: https://doi.org/10.1109/TAC.2003.816954
Dabrowski, C and Hunt, F 2011 Using Markov Chain and Graph Theory Concepts to Analyze Behaviour in Complex Distributed Systems. In: Proc. European Modelling and Simulation Conference (EMSS). Rome, Italy, pp. 658–669.
Dabrowski, C, Hunt, F and Morrison, K 2011 Improving the Efficiency of Markov Chain Analysis of Complex Distributed Systems. National Institute of Standards and Technology Interagency Report 7744, 2011. p. 81.
Dullerud, G and Paganini, F 2005 A Course in Robust Control Theory: A Convex Approach. NY: Springer Verlag, p. 398.
Fruhkwirth, T and Abdennadher, S 2003 Essentials of Constraint Programming. Berlin, Springer–Verlag, p. 147. DOI: https://doi.org/10.1007/978-3-662-05138-2
Goh, C J and Yang, X Q 2002 Duality in Optimization and Variational Inequalities. NY: Taylor & Francis, p. 330. DOI: https://doi.org/10.1201/9781420018868
Hermann, J W 2006 Handbook of Production Scheduling. New York: Springer, p. 318. DOI: https://doi.org/10.1007/0-387-33117-4
Hespanha, J, Naghstabrizi, P and Xu, Y 2007 A Survey of Recent Results in Networked Control Systems. Proceedings of the IEEE, 95(1): 138–162. DOI: https://doi.org/10.1109/JPROC.2006.887288
Horn, R A and Johnson, C R 1991 Matrix Analysis. NY: Cambridge University Press, p. 287.
Jadbabiae, A, Lin, J and Morse, A 2003 Coordination of Groups of Mobile Autonomous Agents Using Nearest Neighbor Rules. IEEE Transactions on Automatic Control, 48(6): 988–1001.
Karasev, R S and Sheremet, I A 2008 Assessment of the Goal-Driven Program Duration with Shifted Terms of Its Contracts. Defense Technology Issues, 1: 31–40 (In Russian).
Klavins, E, Christ, R and Lipsley, D 2006 A Grammatical Approach to Self-Organizing Robotic Systems. IEEE Transactions on Automatic Control, 51(6): 949–962. DOI: https://doi.org/10.1109/TAC.2006.876950
Levin, D A, Peres, Y and Wilmer, E L 2009 Markov Chains and Mixing Times. American Mathematical Society, p. 371.
Lade, S J and Gross, T 2012 Early Warning Signals for Critical Transitions: A Generalized Modeling Approach. Computational Biology, 8(2): e1002360. DOI: https://doi.org/10.1371/journal.pcbi.1002360
Marriott, K 1994 Constraint Multiset Grammars. Proc. IEEE Symposium on Visual Languages. IEEE Computer Society Press, pp. 118–125. DOI: https://doi.org/10.1109/VL.1994.363633
Marriott, K 1996 Parsing Visual Languages with Constraint Multiset Grammars. In: Programming Languages: Implementation, Logic and Programs. – Lecture Notes in Computer Science, Vol. 1292, p. 419.
Marriott, K and Meyer, B 1997 On the Classification of Visual Languages by Grammar Hierarchies. Journal of Visual Languages and Computing, 8(4): 375–402. DOI: https://doi.org/10.1006/jvlc.1997.0053
Marriott, K and Stucky, P G 1998 Programming with Constraints: An Introduction. MIT Press, p. 482.
Mesbahi, M and Egerstedt, M 2010 Graph-Theoretic Methods in Multiagent Networks. Princeton University Press, p. 424. DOI: https://doi.org/10.1515/9781400835355
McCreary, D and Kelly, A 2013 Making Sense of NoSQL: A Guide for Managers and the Rest of Us. Manning Publications, p. 312.
Mills, K and Dabrowski, C 2006 Investigating Global Behaviour in Computing Grids. Lecture Notes in Computer Science, Vol. 4124. Springer, pp. 120–136.
Mills, K and Dabrowski, C 2008 Can Economics-Based Resource Allocation Prove Effective in a Computation Marketplace? Journal of Grid Computing, 6(3): 291–311. DOI: https://doi.org/10.1007/s10723-007-9094-4
Mills, K, Filliben, J, Cho, D-Y and Schwartz, E 2011 Predicting Macroscopic Dynamics in Large Distributed Systems. Proc. ASME 2011 Conference on Pressure Vessels & Piping. Baltimore, MD, July 17–22, 2011.
Mills, K, Filliben, J and Dabrowski, C 2012 Predicting Global Failure Regimes in Complex Information Systems. DoE COMBINE Workshop, September 19, 2012.
Olfati-Saber, R, Fax, J A and Murray, R M 2007 Consensus and Cooperation in Networked Multiagent Systems. Proceedings of the IEEE, 95(1): 215–233. DOI: https://doi.org/10.1109/JPROC.2006.887293
Petrovskiy, A B 2003 Spaces of Sets and Multisets. Moscow: Editorial URSS, p. 248 (In Russian).
Red’ko, V N, Bui, D B and Grishko, Yu 2015 A. Modern State of Multisets Theory from the Entity Point of View. Cybernetics and System Analysis, 51(1): 171–178.
Roberts, F 2016 What is Big Data and How has it Changed. – Invited talk at International Conference on Data Intensive Systems Analysis for Geohazard Studies. Sochi, Russia, July 18–21, 2016.
Scheffer, M 2009 Critical Transitions in Nature and Society. Wiley, p. 400.
Sheffer, M, Bascompte, J, Brock, W A, Brovkin, V, Carenter, S R, Dakos, V, Held, V, Van Nes, E H, Rietkerk, M and Sugihara, G 2009 Early Warning Signals for Critical Transitions. Nature, 461(3): 53–59. DOI: https://doi.org/10.1038/nature08227
Sheremet, I A 2005 On the Approach to Goal-Driven Planning in Defense Acquisition Area. Defense Technology Issues, 5: 5–14 (In Russian).
Sheremet, I A 2005 Goal-Driven Planning Based on Recursive Generation of Contracts Chains. Moscow: FDAS, 42 p. (In Russian).
Sheremet, I A 2010 Recursive Multisets and Their Applications. Moscow: Nauka, p. 293 (In Russian).
Sheremet, I A 2011 Recursive Multisets and Their Applications. Berlin: NG Verlag, p. 249.
Sheremet, I A 2013 Augmented Post Systems: The Mathematical Framework for Knowledge and Data Engineering in Network-Centric Environment. Berlin: EANS, p. 395.
Sheremet, I A 2016 Multiset Approach to the Estimation of Consequences of Natural Disaster Impacts on Industrial Systems. Geoinformatics Research Papers, 4: BS4002, DOI: https://doi.org/10.2205/2016BS01Sochi
Sheremet, I and Zhukov, I 2016 Optimizing Multiset Metagrammars. Formal Definitions. International Journal of Computer Engineering and Information Technology, 8(7): 106–114.
Sheremet, I and Zhukov, I 2016 Optimizing Multiset Metagrammars. Multigrammatical Representation of Classical Optimization Problems. International Journal of Computer Engineering and Information Technology, 8(7): 115–124.
Singh, D, Ibrahim, A M, Yohanna, T and Singh, J N 2007 An Overview of Applications of Multisets. Novi Sad Journal of Mathematics, 37(2): 73–92.
Stewart, W 1994 Introduction to the Numerical Solutions of Markov Chains. Princeton University Press, p. 293.
Vaish, G 2013 Getting Started with NoSQL. Packt Publishing, p. 142.