Mark Sh. Levin

Mark Sh. Levin

The paper addresses design/building frameworks for some kinds of tree-like and hierarchical structures of systems. The following approaches are examined: (1) expert-based procedures, (2) hierarchical clustering; (3) spanning problems (e.g., minimum spanning tree, minimum Steiner tree, maximum leaf spanning tree problem; (4) design of organizational 'optimal' hierarchies; (5) design of multi-layer (e.g., three-layer) k-connected network; (6) modification of hierarchies or networks: (i) modification of tree via condensing of neighbor nodes, (ii) hotlink assignment, (iii) transformation of tree into Steiner tree, (iv) restructuring as modification of an initial structural solution into a solution that is the most close to a goal solution while taking into account a cost of the modification. Combinatorial optimization problems are considered as basic ones (e.g., classification, knapsack problem, multiple choice problem, assignment problem). Some numerical examples illustrate the suggested problems and solving frameworks.

Mark Sh. Levin, Aliaksei Andrushevich, Rolf Kistler et al.

The article addresses combinatorial evolution and forecasting of communication protocol for wireless sensor networks (ZigBee). Morphological tree structure (a version of and-or tree) is used as a hierarchical model for the protocol. Three generations of ZigBee protocol are examined. A set of protocol change operations is generated and described. The change operations are used as items for forecasting based on combinatorial problems (e.g., clustering, knapsack problem, multiple choice knapsack problem). Two kinds of preliminary forecasts for the examined communication protocol are considered: (i) direct expert (expert judgment) based forecast, (ii) computation of the forecast(s) (usage of multicriteria decision making and combinatorial optimization problems). Finally, aggregation of the obtained preliminary forecasts is considered (two aggregation strategies are used).

Mark Sh. Levin

In the paper, combinatorial synthesis of structure for applied Web-based systems is described. The problem is considered as a combination of selected design alternatives for system parts/components into a resultant composite decision (i.e., system configuration design). The solving framework is based on Hierarchical Morphological Multicriteria Design (HMMD) approach: (i) multicriteria selection of alternatives for system parts, (ii) composing the selected alternatives into a resultant combination (while taking into account ordinal quality of the alternatives above and their compatibility). A lattice-based discrete space is used to evaluate (to integrate) quality of the resultant combinations (i.e., composite system decisions or system configurations). In addition, a simplified solving framework based on multicriteria multiple choice problem is considered. A multistage design process to obtain a system trajectory is described as well. The basic applied example is targeted to an applied Web-based system for a communication service provider. Two other applications are briefly described (corporate system and information system for academic application).

Mark Sh. Levin

The paper focuses on some versions of connected dominating set problems: basic problems and multicriteria problems. A literature survey on basic problem formulations and solving approaches is presented. The basic connected dominating set problems are illustrated by simplifyed numerical examples. New integer programming formulations of dominating set problems (with multiset estimates) are suggested.

Mark Sh. Levin

The article addresses balanced clustering problems with an additional requirement as a tree-like structure over the obtained balanced clusters. This kind of clustering problems can be useful in some applications (e.g., network design, management and routing). Various types of the initial elements are considered. Four basic greedy-like solving strategies (design framework) are considered: balancing-spanning strategy, spanning-balancing strategy, direct strategy, and design of layered structures with balancing. An extended description of the spanning-balancing strategy is presented including four solving schemes and an illustrative numerical example.

Mark Sh. Levin

The article describes a special time-interval balancing in multi-processor scheduling of composite modular jobs. This scheduling problem is close to just-in-time planning approach. First, brief literature surveys are presented on just-in-time scheduling and due-data/due-window scheduling problems. Further, the problem and its formulation are proposed for the time-interval balanced scheduling of composite modular jobs. The illustrative real world planning example for modular home-building is described. Here, the main objective function consists in a balance between production of the typical building modules (details) and the assembly processes of the building(s) (by several teams). The assembly plan has to be modified to satisfy the balance requirements. The solving framework is based on the following: (i) clustering of initial set of modular detail types to obtain about ten basic detail types that correspond to main manufacturing conveyors; (ii) designing a preliminary plan of assembly for buildings; (iii) detection of unbalanced time periods, (iv) modification of the planning solution to improve the schedule balance. The framework implements a metaheuristic based on local optimization approach. Two other applications (supply chain management, information transmission systems) are briefly described.

Mark Sh. Levin

The paper describes combinatorial framework for planning of geological exploration for oil-gas fields. The suggested scheme of the geological exploration involves the following stages: (1) building of special 4-layer tree-like model (layer of geological exploration): productive layer, group of productive layers, oil-gas field, oil-gas region (or group of the fields); (2) generations of local design (exploration) alternatives for each low-layer geological objects: conservation, additional search, independent utilization, joint utilization; (3) multicriteria (i.e., multi-attribute) assessment of the design (exploration) alternatives and their interrelation (compatibility) and mapping if the obtained vector estimates into integrated ordinal scale; (4) hierarchical design ('bottom-up') of composite exploration plans for each oil-gas field; (5) integration of the plans into region plans and (6) aggregation of the region plans into a general exploration plan. Stages 2, 3, 4, and 5 are based on hierarchical multicriteria morphological design (HMMD) method (assessment of ranking of alternatives, selection and composition of alternatives into composite alternatives). The composition problem is based on morphological clique model. Aggregation of the obtained modular alternatives (stage 6) is based on detection of a alternatives 'kernel' and its extension by addition of elements (multiple choice model). In addition, the usage of multiset estimates for alternatives is described as well. The alternative estimates are based on expert judgment. The suggested combinatorial planning methodology is illustrated by numerical examples for geological exploration of Yamal peninsula.

Mark Sh. Levin

The article contains a preliminary glance at balanced clustering problems. Basic balanced structures and combinatorial balanced problems are briefly described. A special attention is targeted to various balance/unbalance indices (including some new versions of the indices): by cluster cardinality, by cluster weights, by inter-cluster edge/arc weights, by cluster element structure (for element multi-type clustering). Further, versions of optimization clustering problems are suggested (including multicriteria problem formulations). Illustrative numerical examples describe calculation of balance indices and element multi-type balance clustering problems (including example for design of student teams).

Mark Sh. Levin

Combinatorial evolution and forecasting of system requirements is examined. The morphological model is used for a hierarchical requirements system (i.e., system parts, design alternatives for the system parts, ordinal estimates for the alternatives). A set of system changes involves changes of the system structure, component alternatives and their estimates. The composition process of the forecast is based on combinatorial synthesis (knapsack problem, multiple choice problem, hierarchical morphological design). An illustrative numerical example for four-phase evolution and forecasting of requirements to communications is described.

Mark Sh. Levin

The paper described a generalized integrated glance to bin packing problems including a brief literature survey and some new problem formulations for the cases of multiset estimates of items. A new systemic viewpoint to bin packing problems is suggested: (a) basic element sets (item set, bin set, item subset assigned to bin), (b) binary relation over the sets: relation over item set as compatibility, precedence, dominance; relation over items and bins (i.e., correspondence of items to bins). A special attention is targeted to the following versions of bin packing problems: (a) problem with multiset estimates of items, (b) problem with colored items (and some close problems). Applied examples of bin packing problems are considered: (i) planning in paper industry (framework of combinatorial problems), (ii) selection of information messages, (iii) packing of messages/information packages in WiMAX communication system (brief description).

Mark Sh. Levin

The paper focuses on a new class of combinatorial problems which consists in restructuring of solutions (as sets/structures) in combinatorial optimization. Two main features of the restructuring process are examined: (i) a cost of the restructuring, (ii) a closeness to a goal solution. Three types of the restructuring problems are under study: (a) one-stage structuring, (b) multi-stage structuring, and (c) structuring over changed element set. One-criterion and multicriteria problem formulations can be considered. The restructuring problems correspond to redesign (improvement, upgrade) of modular systems or solutions. The restructuring approach is described and illustrated (problem statements, solving schemes, examples) for the following combinatorial optimization problems: knapsack problem, multiple choice problem, assignment problem, spanning tree problems, clustering problem, multicriteria ranking (sorting) problem, morphological clique problem. Numerical examples illustrate the restructuring problems and solving schemes.

Mark Sh. Levin

The paper focuses on composite multistage decision making problems which are targeted to design a route/trajectory from an initial decision situation (origin) to goal (destination) decision situation(s). Automobile routing problem is considered as a basic physical metaphor. The problems are based on a discrete (combinatorial) operations/states design/solving space (e.g., digraph). The described types of discrete decision making problems can be considered as intelligent design of a route (trajectory, strategy) and can be used in many domains: (a) education (planning of student educational trajectory), (b) medicine (medical treatment), (c) economics (trajectory of start-up development). Several types of the route decision making problems are described: (i) basic route decision making, (ii) multi-goal route decision making, (iii) multi-route decision making, (iv) multi-route decision making with route/trajectory change(s), (v) composite multi-route decision making (solution is a composition of several routes/trajectories at several corresponding domains), and (vi) composite multi-route decision making with coordinated routes/trajectories. In addition, problems of modeling and building the design spaces are considered. Numerical examples illustrate the suggested approach. Three applications are considered: educational trajectory (orienteering problem), plan of start-up company (modular three-stage design), and plan of medical treatment (planning over digraph with two-component vertices).

Mark Sh. Levin

The paper describes clustering problems from the combinatorial viewpoint. A brief systemic survey is presented including the following: (i) basic clustering problems (e.g., classification, clustering, sorting, clustering with an order over cluster), (ii) basic approaches to assessment of objects and object proximities (i.e., scales, comparison, aggregation issues), (iii) basic approaches to evaluation of local quality characteristics for clusters and total quality characteristics for clustering solutions, (iv) clustering as multicriteria optimization problem, (v) generalized modular clustering framework, (vi) basic clustering models/methods (e.g., hierarchical clustering, k-means clustering, minimum spanning tree based clustering, clustering as assignment, detection of clisue/quasi-clique based clustering, correlation clustering, network communities based clustering), Special attention is targeted to formulation of clustering as multicriteria optimization models. Combinatorial optimization models are used as auxiliary problems (e.g., assignment, partitioning, knapsack problem, multiple choice problem, morphological clique problem, searching for consensus/median for structures). Numerical examples illustrate problem formulations, solving methods, and applications. The material can be used as follows: (a) a research survey, (b) a fundamental for designing the structure/architecture of composite modular clustering software, (c) a bibliography reference collection, and (d) a tutorial.

Mark Sh. Levin

The survey methodological paper addresses a glance to a general decision support platform technology for modular systems (modular/composite alterantives/solutions) in various applied domains. The decision support platform consists of seven basic combinatorial engineering frameworks (system synthesis, system modeling, evaluation, detection of bottleneck, improvement/extension, multistage design, combinatorial evolution and forecasting). The decision support platform is based on decision support procedures (e.g., multicriteria selection/sorting, clustering), combinatorial optimization problems (e.g., knapsack, multiple choice problem, clique, assignment/allocation, covering, spanning trees), and their combinations. The following is described: (1) general scheme of the decision support platform technology; (2) brief descriptions of modular (composite) systems (or composite alternatives); (3) trends in moving from chocie/selection of alternatives to processing of composite alternatives which correspond to hierarchical modular products/systems; (4) scheme of resource requirements (i.e., human, information-computer); and (5) basic combinatorial engineering frameworks and their applications in various domains.

Mark Sh. Levin

The paper describes multistage design of composite (modular) systems (i.e., design of a system trajectory). This design process consists of the following: (i) definition of a set of time/logical points; (ii) modular design of the system for each time/logical point (e.g., on the basis of combinatorial synthesis as hierarchical morphological design or multiple choice problem) to obtain several system solutions; (iii) selection of the system solution for each time/logical point while taking into account their quality and the quality of compatibility between neighbor selected system solutions (here, combinatorial synthesis is used as well). Mainly, the examined time/logical points are based on a time chain. In addition, two complicated cases are considered: (a) the examined logical points are based on a tree-like structure, (b) the examined logical points are based on a digraph. Numerical examples illustrate the approach.

Mark Sh. Levin

The paper describes some basic approaches to detection of bottlenecks in composite (modular) systems. The following basic system bottlenecks detection problems are examined: (1) traditional quality management approaches (Pareto chart based method, multicriteria analysis as selection of Pareto-efficient points, and/or multicriteria ranking), (2) selection of critical system elements (critical components/modules, critical component interconnection), (3) selection of interconnected system components as composite system faults (via clique-based fusion), (4) critical elements (e.g., nodes) in networks, and (5) predictive detection of system bottlenecks (detection of system components based on forecasting of their parameters). Here, heuristic solving schemes are used. Numerical examples illustrate the approaches.

Mark Sh. Levin

This survey note describes a brief systemic view to approaches for evaluation of hierarchical composite (modular) systems. The list of considered issues involves the following: (i) basic assessment scales (quantitative scale, ordinal scale, multicriteria description, two kinds of poset-like scales), (ii) basic types of scale transformations problems, (iii) basic types of scale integration methods. Evaluation of the modular systems is considered as assessment of system components (and their compatibility) and integration of the obtained local estimates into the total system estimate(s). This process is based on the above-mentioned problems (i.e., scale transformation and integration). Illustrations of the assessment problems and evaluation approaches are presented (including numerical examples).

Mark Sh. Levin

The paper describes development (improvement/extension) approaches for composite (modular) systems (as combinatorial reengineering). The following system improvement/extension actions are considered: (a) improvement of systems component(s) (e.g., improvement of a system component, replacement of a system component); (b) improvement of system component interconnection (compatibility); (c) joint improvement improvement of system components(s) and their interconnection; (d) improvement of system structure (replacement of system part(s), addition of a system part, deletion of a system part, modification of system structure). The study of system improvement approaches involve some crucial issues: (i) scales for evaluation of system components and component compatibility (quantitative scale, ordinal scale, poset-like scale, scale based on interval multiset estimate), (ii) evaluation of integrated system quality, (iii) integration methods to obtain the integrated system quality. The system improvement/extension strategies can be examined as seleciton/combination of the improvement action(s) above and as modification of system structure. The strategies are based on combinatorial optimization problems (e.g., multicriteria selection, knapsack problem, multiple choice problem, combinatorial synthesis based on morphological clique problem, assignment/reassignment problem, graph recoloring problem, spanning problems, hotlink assignment). Here, heuristics are used. Various system improvement/extension strategies are presented including illustrative numerical examples.

Mark Sh. Levin

The paper briefly describes a basic set of special combinatorial engineering frameworks for solving complex problems in the field of hierarchical modular systems. The frameworks consist of combinatorial problems (and corresponding models), which are interconnected/linked (e.g., by preference relation). Mainly, hierarchical morphological system model is used. The list of basic standard combinatorial engineering (technological) frameworks is the following: (1) design of system hierarchical model, (2) combinatorial synthesis ('bottom-up' process for system design), (3) system evaluation, (4) detection of system bottlenecks, (5) system improvement (re-design, upgrade), (6) multi-stage design (design of system trajectory), (7) combinatorial modeling of system evolution/development and system forecasting. The combinatorial engineering frameworks are targeted to maintenance of some system life cycle stages. The list of main underlaying combinatorial optimization problems involves the following: knapsack problem, multiple-choice problem, assignment problem, spanning trees, morphological clique problem.

Mark Sh. Levin

The paper describes combinatorial synthesis approach with interval multset estimates of system elements for modeling, analysis, design, and improvement of a modular telemetry system. Morphological (modular) system design and improvement are considered as composition of the telemetry system elements (components) configuration. The solving process is based on Hierarchical Morphological Multicriteria Design (HMMD): (i) multicriteria selection of alternatives for system components, (ii) synthesis of the selected alternatives into a resultant combination (while taking into account quality of the alternatives above and their compatibility). Interval multiset estimates are used for assessment of design alternatives for telemetry system elements. Two additional systems problems are examined: (a) improvement of the obtained solutions, (b) aggregation of the obtained solutions into a resultant system configuration. The improvement and aggregation processes are based on multiple choice problem with interval multiset estimates. Numerical examples for an on-board telemetry subsystem illustrate the design and improvement processes.

Mark Sh. Levin

The paper addresses an approach to ordinal assessment of alternatives based on assignment of elements into an ordinal scale. Basic versions of the assessment problems are formulated while taking into account the number of levels at a basic ordinal scale [1,2,...,l] and the number of assigned elements (e.g., 1,2,3). The obtained estimates are multisets (or bags) (cardinality of the multiset equals a constant). Scale-posets for the examined assessment problems are presented. 'Interval multiset estimates' are suggested. Further, operations over multiset estimates are examined: (a) integration of multiset estimates, (b) proximity for multiset estimates, (c) comparison of multiset estimates, (d) aggregation of multiset estimates, and (e) alignment of multiset estimates. Combinatorial synthesis based on morphological approach is examined including the modified version of the approach with multiset estimates of design alternatives. Knapsack-like problems with multiset estimates are briefly described as well. The assessment approach, multiset-estimates, and corresponding combinatorial problems are illustrated by numerical examples.

Mark Sh. Levin, Alexander V. Fimin

The paper addresses combinatorial approach to design of modular wireless sensor as composition of the sensor element from its component alternatives and aggregation of the obtained solutions into a resultant aggregated solution. A hierarchical model is used for the wireless sensor element. The solving process consists of three stages: (i) multicriteria ranking of design alternatives for system components/parts, (ii) composing the selected design alternatives into composite solution(s) while taking into account ordinal quality of the design alternatives above and their compatibility (this stage is based on Hierarchical Morphological Multicriteria Design - HMMD), and (iii) aggregation of the obtained composite solutions into a resultant aggregated solution(s). A numerical example describes the problem structuring and solving processes for modular alarm wireless sensor element.

Mark Sh. Levin

In the paper, frameworks for electronic shopping of composite (modular) products are described: (a) multicriteria selection (product is considered as a whole system, it is a traditional approach), (b) combinatorial synthesis (composition) of the product from its components, (c) aggregation of the product from several selected products/prototypes. The following product model is examined: (i) general tree-like structure, (ii) set of system parts/components (leaf nodes), (iii) design alternatives (DAs) for each component, (iv) ordinal priorities for DAs, and (v) estimates of compatibility between DAs for different components. The combinatorial synthesis is realized as morphological design of a composite (modular) product or an extended composite product (e.g., product and support services as financial instruments). Here the solving process is based on Hierarchical Morphological Multicriteria Design (HMMD): (i) multicriteria selection of alternatives for system parts, (ii) composing the selected alternatives into a resultant combination (while taking into account ordinal quality of the alternatives above and their compatibility). The aggregation framework is based on consideration of aggregation procedures, for example: (i) addition procedure: design of a products substructure or an extended substructure ('kernel') and addition of elements, and (ii) design procedure: design of the composite solution based on all elements of product superstructure. Applied numerical examples (e.g., composite product, extended composite product, product repair plan, and product trajectory) illustrate the proposed approaches.

Mark Sh. Levin

The article addresses morphological approaches to design of modular systems. The following methods are briefly described: (i) basic version of morphological analysis (MA), (ii) modification of MA as method of closeness to ideal point(s), (iii reducing of MA to linear programming, (iv) multiple choice problem, (v) quadratic assignment problem, (vi) Pareto-based MA (i.e., revelation of Pareto-efficient solutions), (vii) Hierarchical Morphological Multicriteria Design (HMMD) approach, and (viii) Hierarchical Morphological Multicriteria Design (HMMD) approach based on fuzzy estimates. The above-mentioned methods are illustrated by schemes, models, and illustrative examples. An additional realistic example (design of GSM network) is presented to illustrate main considered methods.