COURSE
“DESIGN OF SYSTEMS: Structural approach”
MAIN
TOPICS (SECTIONS):
I.SYSTEM
ISSUES
1.1.systems, life cycle, systems engineering, concurrent
engineering,
1.2.structural models (graphs, digraphs, binary relations)
1.3.information technology
1.4.design frameworks
II.SYSTEM
ANALYSIS & DECISION MAKING
2.1.principles of system analysis,
2.2.paradigm of decision making by H. Simon,
2.3.basic decision making problems (4), kinds of scales,
2.4.hierarchy of requirements and criteria systems, organizational
framework of decision making, roles in decision making,
2.5.methods of multicriteria ranking:
utility functions,
2.6.Pareto-approach and
its usage for multicriteria ranking
2.7.methods of multicriteria ranking:
outranking techniques (ELECTRE),
2.8.schemes for integration / aggregation of results
III.OPTIMIZATION
AND COMBINATORIAL OPTIMIZATION
3.1.general optimization model
3.2.ellipsoid method
3.3.knapsack, multiple choice problem,
3.4.bin-packing, packing
3.5.graph coloring, clique, covering,
3.6.satisfiability, 3-satisfiability
3.7.TSP, Hamiltonian cycle, scheduling problems,
3.8.spanning tree, minimal Steiner tree
3.9.alignment, maximal substructure, minimal superstructure,
string matching
3.10.complexity of combinatorial optimization problems
(polynomial solvable problems, NP-complete and NP-hard problems, approximate
solvable problems),
3.11.types of algorithms, methods as global methods and local
techniques,
3.12.heuristics and approximate algorithms
3.13.genetic algorithms and evolutionary multiobjective
optimization
3.14.allocation like problems (assignment problem, quadratic
assignment problem, generalized assignment problem, matching problems)
IV.DESIGN
FRAMEWORKS
4.1.design as generation/evaluation/selection,
4.2.parameter space investigation PSI,
4.3.multidisciplinary optimization,
4.4.hierarchical and cascade-like design
4.5.revelation of system bottlenecks
V.MOPHOLOGICAL
DESIGN APPROACH
5.1.morphological design approaches (morphological analysis,
proximity to ideal solution, multicriteria evaluation
of all feasible solutions, hierarchical design)
5.2.morphological combinatorial synthesis
5.3.combinatorial morphological synthesis for system
improvement (upgrade)
5.4.combinatorial morphological synthesis for multi-stage
design and design of life cycle
5.5.combinatorial morphological synthesis for design of
multi-product system
VI.ADDITIONAL
SYSTEM ISSUES
6.1.system testing
6.2.system evaluation (diagnosis)
6.3.system maintenance
6.4.requirements engineering
BASIC
REFERENCE:
Course
on “Design of System: structural approach” http://www.iitp.ru/mslevin/
ADDITIONAL
REFERENCES
I.SYSTEM
ISSUES
1.G.S.Altshuller, Creativity as Exact Science: The
Theory of the Solution of Inventive Problems.
Gordon&Breach, 1984.
2.R.U. Ayres, Technological Forecasting
and Long-Time Planning. McGraw-Hill, 1969.
4.G. Booch,
Object Oriented Development, The Benjamin / Cummings, 1991.
Addison-Wesley, 1975.
6.D. M. Buede,
The Engineering Design of Systems: Models and Methods, Wiley, 1999.
7.J.R. Dixon, Design Engineering:
Inventiveness, Analysis and Decisions.
McGraw-Hill, 1966.
8.Y.A. Dubov,
S.I. Travkin, V.N. Iakimets,
Multicriteria Models for Building of
System Choice Variants. Nauka, 1986 (in Russian).
9.Y.Y. Haimes, (Ed.). Large Scale Systems.
11.D.M. Himmelblau, Morphology of decomposition. In: D.M. Himmelblau, (Ed.). Decomposition of
Large-Scale Problem.
13.V. Hubka, W.E. Eder, Theory of TechniCal Systems. A Total Concept Theory
for Engineering Design. Springer, 1988.
15.J. Gero, F. Sudweeks, Eds., Advances in Formal Design Methods, Kluwer, 1998.
16.J.C. Jones, Design
Methods. Wiley, Wiley, 1981.
17.P.S. Krasnoshekov, V.V. Morozov, V.V. Fedorov, Decomposition in design problems. Engineering
Cybernetics, No. 2, 7-17, 1979 (in Russian)
18.A. Kusiak, Engineering Design: Products, Processes, and
Systems, Academic Press, 1999.
19.O.P. Kuznezov, G.M. Adelson-Velsky,
Discrete Mathematics for Engineers. Energoizdat, 1988
(in Russian)
20.M.Sh. Levin, On
Teaching of information technology. Nauchno-Tekhnicheskaya
Informatsya, Ser. 1, No. 5, 14-23, 1996 (in Russian)
21.M.Sh.Levin,
Combinatorial design of systems. Automatization of
Design,
No. 4, 14-19, 1997 (in Russian)
22.M.Sh. Levin,
Combinatorial Engineering of Decomposable Systems, Kluwer,
1998.
23.M.D. Mesarovic, D. Macko, Y. Takahara, Theory of Hierarchical Multilevel Systems. Academic Press, 1970.
24.E. Minieka, Optimization Algorithms for Networks and Graphs.
Marcel Dekker, 1978.
25.B.G. Mirkin, Group Choice, Winston, 1979.
26.O. Ore, Theory of
Graphs, Amer. Math. Society, 1962.
27.J. Pahl, W. Beitz, Engineering
Design: A Systematic Approach. Springer, 1988.
28.B. Prasad,
Concurrent Engineering Fundamentals: Integrated Product and Process Organization, Vols. 1 & 2, Prentice Hall,
1996.
30.M.I. Rubinshtein, Optimal Grouping of Interconnected Objects, Nauka, 1989 (in Russian).
31.A.P. Sage, W.B.
Rouse, Eds., Handbook of Systems Engineering and Management. Wiley,
1999.
32.M. Shaw, D. Garlan, Software Architecture: Perspectives on an Emerging
Disciplines. Prentice Hall, 1995.
33.R.J. Wilson,
Introduction to Graph Theory. Oliver & Boyd, 1972.
34.M.Sh. Levin,
Composite Systems Decisions, Springer, 2006.
35.D.M. Buede, The Engineering Design of Systems: Models and
Methods. Wiley, 1999.
36.M.W. Mayer, E. Rechtin, The Art of Systems Architecting. 2nd ed., CRC, 2000.
37.Ch.S. Wasson,
System Analysis, Design, and Development: Concepts, Principles, and Practice. Wiley, 2006.
38.A. Kossiakoff, W.N. Sweet, Systems Engineering Principles and
Practice. Wiley, 2002.
39.B.S. Blanchard,
Systems Engineering Management, 3rd ed., Wiley, 2002.
40.J.O. Grady, System
Requirements Analysis. Academic Press, 2006.
SITES:
1.Course “Design of Systems: structural
approach” http://www.iitp.ru/mslevin/
2.
3.Int. Council on Systems Engineering: http://www.incose.org/
II.SYSTEM ANALYSIS & DECISION MAKING
1.A.R. Belkin, M.Sh. Levin, Decision Making: Combinatorial Models of
Information Approximation, Nauka, 1990 (in Russian)
2.P.C. Fishburn,
Utility Theory for Decision Making, Wiley, 1976.
3.V.A. Glotov,
V.V. Paveljev, Vector Stratification. Nauka, 1976 (in
Russian).
4.R.L. Keeny,
H. Raiffa, Decisions with Multiple Objectives:
Preferences and Value Tradeoffs, Wiley, 1976.
5.M.Sh. Levin, A.A. Michailov,
Fragments of object set stratification technology.
Preprint, Institute for System Studies (now
Institute for System Analysis),
6.M.Sh. Levin, The 3rd Literacy, Autom. Doc. & Math. Lingistics,
29(3), 66-81, 1995.
7.A.V. Lotov,
V.A. Bushenkov, G.K. Kamenev,
Interactive Decision Maps: Approximation and Visualization of Pareto Frontier, Kluwer, 2004.
8.B.G. Mirkin,
Group Choice, Winston, 1979.
9.V. Pareto, Manual of Political
Economy, Reprint ed.,
10.B. Roy, The
Outranking Approach and Foundations of ELECTRE Methods. In:
11.T.L. Saaty, The Analytic Hierarchy Process, MacGraw-Hill,
1988.
12.H. Simon, The
Science of Artifcial, MIT Press, 1969.
13.H.A. Simon, G.B. Dantzig,
R. Hogarth, C.R. Plott, H. Raiffa, T.C. Schelling, K.A. Shepsle, R. Thaler, A. Tversky, S. Winter, Decision Making and Problem Solving. Interfaces, 17(5), 11-31, 1987.
14.R.E. Steuer, Multiple Criteria Optimization: Theory,
Computation, and Application. Wiley, 1986.
15.M.Sh. Levin,
Composite Systems Decisions. Springer, 2006.
16.B.G. Mirkin, Clustering for Data Mining: A Data Discovery
Approach. NJ: Chapman&Hill/CRC, 2005.
17.S.R. Watson, D.M. Buede, Decision Synthesis: the principles of decision
analysis.
SITES
1.Int. Society on MCDM: http://www.terry.uga.edu/mcdm/
2.Decision Science Institute: http://www.decisionsciences.org/
3.INFORMS: http://www.informs.org/
III.OPTIMIZATION AND COMBINATORIAL OPTIMIZATION
1.N.M. Alexandrov,
M.Y. Hussaini, Eds., Multidisciplinary Design
Optimization: State of the Art (Proc. in Applied Math. Series;
No. 80),
2.J.Aoe, (Ed.), Computer Algorithms: String
Pattern Matching Strategies.
IEEE CS Press, 1994.
3.R. Bellman, Dynamic Programming,
4.M. Ball, M. Magazine, The design and
analysis of heuristics, Networks, 11(2), 215-219, 1981.
5.J. Blazewicz,
W. Cellary, R. Slowinski,
J. Weglarz, Scheduling under Resource Constraints: Deterministic
Models, Baltzer, 1986.
6. E.G. Coffmann, Jr. (Ed.), Scheduling in Computer and Job Shop
Systems, Wiley, 1976.
7.R.W. Conway, W.L. Maxwell, L.W. Miller,
Theory of Scheduling. Addison-Wesley, 1967.
8.D.Gusfield, R.W. Irwing,
The Stable Marriage Problem: Structure and Algorithms, The MIT Press, 1989.
9.M.S. Daskin,
Networks and Discrete Location. Models, Algorithms, and A9pplications.
Wiley, 1995.
10.K. Deb,
Multi-Objective Optimization Using Evolutionary Algorithms. Wiley,
2001.
11.Ch.A. Floudas, Deterministic Global Optimization, Kluwer, 1999.
13.D.E. Goldberg,
Genetic Algorithms in Search, Optimization, and Machine
Learning. Addison-Wesley,
1989.
15.A.O. Ivanov, A.A.Tuzhilin, Minimal
Networks. The Steiner Problem and Its
Generalizations. CRC Press, 1994.
16.T.R. Jensen, B. Toft, Graph Coloring Problems. Wiley,
1994.
17.D.S. Johnson, M.A.
Trick, (Eds.), Cliques, Coloring, and Satisfiability.
AMS, Vol. 26, 1996.
18.R.M. Karp, Combinatorics, Complexity, and Randomness, Comm. of the ACM, 29(2), 98-109, 1986.
19.O.P. Kuznezov, G.M. Adelson-Velsky,
Discrete Mathematics for Engineers. Energoizdat, 1988
(in Russian)
20.E.L. Lawler, J.K. Lenstra,
A.H.G. Rinnooy Kan, D.B. Shmoys,
(Eds.),
Traveling Salesman Problem. Wiley, 1985.
21.J. Lee, First
Course in Combinatorial Optimization.
22.M.Sh. Levin,
Applications of Combinatorial Models in Computer-Aided Systems, VNIITEMR, 1986
(in Russian)
23.M.Sh. Levin, Combinatorial
Engineering of Decomposable Systems, Kluwer, 1998.
24.S. Martello, P. Toth, Knapsack Problem: Algorithms, and Computer
Implementation, Wiley, 1990.
25.Z. Michalewicz, Genetic Algorithms + Data Structures +
Evolution Programs.
Springer, 1996.
26.E. Minieka, Optimization Algorithms for Networks and Graphs.
Marcel Dekker, 1978.
27.B.G. Mirkin, Group Choice, Winston, 1979.
28.G.L. Nemhauser,
29.A.S Nemirovski, B.D. Yudin, Problem
Complexity and Method Efficiency in Optimization, Wiley, 1983.
30.O. Ore, Theory of
Graphs, Amer. Math. Society, 1962.
32.P. Pardalos, M.G.C. Resende,
Handbook on Applied Optimization.
33.P.M. Pardalos, H. Wolkowicz, (Ed.),
Quadratic Assignment and Related Problems. American
Mathematical Society, 1994.
34.E.M. Reingold, J. Nievergelt,
35.G. Reinelt, The Traveling Salesman. Springer,
1994.
37.R.Rubinstein, D.P. Kroese, The Cross Entropy Method: A Unified Approach
to Combinatorial Optimization,
Monte-Carlo Simulation and Machine Learning. Springer, 2004.
38.M.I. Rubinshtein, Optimal Grouping of Interconnected Objects, Nauka, (in Russian), 1989.
39.R. Burkard, M. Dell’Amico,
40.E. Cela, The Quadratic Assignment Problem, Kluwer,
1998.
41.R.J. Wilson,
Introduction to Graph Theory. Oliver & Boyd, 1972.
42.G. Winter, J. Periaux,
M. Galan, P. Cuesta,
Genetic Algorithms in Engineering and Computer Science, Wiley, 1996.
43.M.Sh. Levin,
Composite Systems Decisions. Springer, 2006.
44.D.L. Applegate,
R.E. Bixby, V. Chvatal, W.J. Cook, The Traveling
Salesman Problem: A Computational Study.
45.A. Nayak, I. Stojmenovich, Handbook on Applied Algorithms: Solving Scientific,
Engineering, and Practical Problems. IEEE & Wiley, 2008.
46.M.X. Cheng, Y. Li,
D.-Z. Du, (Eds.), Combinatorial Optimization in
Communication Networks. Sprigner, 2006.
47.G. Gan, G. Ma, J. Wu, Data Clustering: Theory, Algorithms, and
Applications.
48. R.E. Bellman, S.E. Dreyfus, Applied Dynamic
Programming.
49.T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms. 2nd ed.,
50. S.S. Skiena, The Algorithm Design Manual. 2nd ed.,
Springer, 2008.
51. V.T. Paschos
(Ed.), Paradigms of Combinatorial Optimization: Problems and New Approaches. Wiley-ISTE, 2010.
52. V.T. Paschos
(Ed.), Applications of Combinatorial Optimization. Wiley-ISTE,
2010.
SITES
1.Dictionary of Algorithms and Data Structure
(NIST): http://www.nist.gov/dads/
2.Combinatorial Problems: Formulations, Algorithms
http://www.cs.sunysb.edu/algorith/implement/syslo/implement.shtml
3.Genetic Algorithm Archive http://www.aic.nrl.navy.mil/galist/
4.OR-Library by J.E. Beasley: http://www.brunel.ac.uk/depts/research/jeb/info.html
5.Repository of e-prints about optimization
(Mathematical Programming Society)
http://www.optimization-online.org/
6.Evolutionary multiobjective
optimization: http://www.lania.mx/~ccoello/EMOO/
7.Graph Coloring Page (Joseph Culberson): http://www.cs.ualberta.ca/~joe/Coloring/
8.Network Resources for Coloring a Graph
(Michael Trick):
http://mat.gsia.cmu.edu/COLOR/color.html
9.Quadratic Assignment Problem Library:
http://www.opt.math.tu-graz.ac.at/qaplib/
10.Traveling Salesman
Problem Homepage: http://www.tsp.gatech.edu
11.Steiner Minimal Tree Problem (Bob Bell): http://www.css.tayloru.edu/~bbell/steiner/
12.Cross Entropy Page:
http://iew3.technion.ac.il/CE/about.php
13.Working Group on
Automated TimeTabling: http://www.asap.cs.nott.ac.uk/watt/
IV.DESIGN FRAMEWORKS
1.N.M. Alexandrov,
M.Y. Hussaini, Eds., Multidisciplinary Design
Optimization: State of the Art (Proc. in Applied Math. Series;
No. 80),
2.R.U. Ayres, Technological Forecasting
and Long-Time Planning. McGraw-Hill, 1969.
3.D. M. Buede,
The Engineering Design of Systems: Models and Methods, 2nd ed., Wiley,
2009.
4.G. Booch,
Object Oriented Development, The Benjamin / Cummings, 1991.
5.D. Braha,
O. Maimon, A Mathematical Theory of Design:
Foundations, Algorithms and Applications. Kluwer, 1998.
6.J.R. Dixon, Design Engineering:
Inventiveness, Analysis and Decisions.
McGraw-Hill, 1966.
7.Y.A. Dubov,
S.I. Travkin, V.N. Iakimets,
Multicriteria Models for Building of
System Choice Variants. Nauka, 1986 (in Russian).
8.V. Hubka,
W.E. Eder, Theory of Techncial
Systems. A Total Concept Theory for Engineering Design.
Springer, 1988.
9.J.C. Jones, Design Methods. Wiley, 1981.
10.P.S. Krasnoshekov, V.V. Morozov, V.V. Fedorov, Decomposition in design problems. Engineering
Cybernetics, No. 2, 7-17, 1979 (in Russian)
11.A. Kusiak, Engineering Design:
Products, Processes, and Systems, Academic Press, 1999.
12.H. Li,
14.J. Pahl, W. Beitz, Engineering
Design: A Systematic Approach. Springer, 1988.
15.R.B. Statnikov, J. Matusov, Multicriteria Optimization and Engineering, Chapman&Hall, 1995.
16.M.Sh. Levin,
Composite Systems Decisions, Springer, 2006.
SITES
1.Optimal Decomposition of Design Problems (
2.
3.The Synthesis Coalition: http://www.synthesis.org
4.Int. Council on Systems Engineering: http://www.incose.org/
5.Computer-Aided Systems Laboratory (
6.Design Decision Support Laboratory (Sapour Azarm) http://ddsl.umd.edu/
7.Int. Society for Structural and
Multidisciplinary Optimization http://www.issmo.org
V.MOPHOLOGICAL DESIGN APPROACH
1.R.U. Ayres, Technological Forecasting
and Long-Time Planning. McGraw-Hill, 1969.
2.Y.A. Dubov,
S.I. Travkin, V.N. Iakimets,
Multicriteria Models for Building of
System Choice Variants. Nauka, 1986 (in Russian).
3.P.S. Krasnoshekov,
V.V. Morozov, V.V. Fedorov,
Decomposition in design problems. Engineering Cybernetics, No. 2, 7-17, 1979
(in Russian)
4.J.C. Jones, Design Methods. Wiley, 1981.
5.M.Sh. Levin, Combinatorial Engineering
of Decomposable Systems, Kluwer, 1998.
7.M.Sh. Levin, Composite Systems
Decisions, Springer, 2006.
SITES:
1.The Synthesis Engineering Education
Coalition: http://www.synthesis.org/
2.Swedish Morphological Society: http://www.swemorph.com/
VI.ADDITIONAL SYSTEM ISSUES
1.K. Bogdanov,
M. Holombe, Statechart
testing method for aircraft control systems. Software
Testing, Verification and Reliability, 11, 39-54, 2001.
2.D.M. Cohen, S.R. Dalal, J. Parelius, G.C. Patton,
The combinatorial design approach to automatic test generation, IEEE Software, pp. 83-87, Sept. 1996.
3.J.M. Cross, Fundamentals of Preventive
Maintenance.
American Management Association,
2002.
4.
5.
6.P.C. Jorgensen, Software Testing. A Craftman's Approach, 2 ed., CRC Press,
7.C. Kaner, J. Falk, H.Q. Nguyen, Testing
Computer Software, 2nd ed., Wiley, 1999.
8.M.G. Karpovsky,
E.A. Moskalev, Covering of edges of graph by a
minimal set of paths. Discr. Math. 58(2),
214, 1986.
9.K.R.P.H. Leung, W. Wong, J.K-Y. Ng, Generating test cases from class
vectors, The J.
of Systems and Software 66(1), 35-46, 2003.
10.M.Sh. Levin, M.
Last, Multi-Function System Testing: Composition of Test Sets. 8th
IEEE Int. Conf.
HASE 2004, Tampa, FL, 99-108, 2004.
11.J. Levitt, Complete Guide to Preventive and Predictive
Maintenance. Industrial Press, 2002.
12.V.V. Lipaev, A methodology of verification and testing of large
software systems. Programming and
Computer Software 29(6), 298-309, 2003.
13.S. Robertson, J.
Robertson, Mastering the Requirements Process.
Addison-Wesley, 1999.
14.P.J. Schroeder, B. Korel, Black-box test reduction using Input-Output
analysis, ACM SIGSOFT Software Eng. Notes 25(5), 173-177, 2000.
15.S. Stoica, Generating functional
design verification tests, IEEE Design&Test
16(3), 53-63, 1999.
16.R.D. Palmer,
Maintenance Planning and Scheduling Handbook. McGraw-Hill,
1999.
17.T.J. Ostrand, M.J. Balcer,
The category-partition method for specifying and generating functional tests,
Comm. of the ACM 31(6), 676-686, 1988.
18.K.E. Wiegers, Software
Requirements. 2nd ed., Microsoft Press, 2003.
19.T. Wireman, Total Productive Maintenance. Industrial Press, 2004.
20.R.R. Yong, The Requirements Engineering Handbook. Artech House, 2004.
21.M.Sh. Levin, Composite Systems Decisions. Springer, 2006.
SITES
1.STORM: software testing online resources http://www.mtsu.edu/~storm
2.IEEE Task Force on Requirements Engineering: http://www.shu.ac.uk/tfre/
3.Maintenance World: http://www.maintenanceworld.com/
4.The Software Quality Engineering & Data Mining Laboratory (M. Last) http://www.ise.bgu.ac.il/faculty/mlast/
5.Verification and Testing Research Group (M. Holombe) http://www.dcs.shef.ac.uk/research/groups/vt/
EXAMINATION
A.Preliminary Part: Reports on Lab. Works 1, 2, 3, 4, 5, 6, 7,
8, 9, 10, 11, and 12
B.Main Part:
(1)Questions:
(a) from section I or II or VI
(b) from
section III
(c) from
section IV or V
(2)Discussion