Combinatorial Optimization Problems in Planning and Decision Making

Acknowledgements......Page 6
Contents......Page 7
Abbreviations......Page 13
 1.1 Scope......Page 15
 1.2 Content......Page 20
 1.3 Audience......Page 24
 References......Page 25
Intractable Combinatorial Optimization Problems. PSC-algorithms......Page 29
 2.1 The Problem Formulation......Page 30
 2.2 Construction of a Feasible Schedule with Maximum Start Time of Tasks......Page 31
 2.3 Construction of a Feasible Schedule That Minimizes the Total Earliness of Tasks with Maximum Start Time of the Machine s_{{\rm max}}......Page 35
 2.4 The Polynomial Algorithm for Finding an Optimal Schedule for the Total Earliness Criterion for a Given Start Time of the Machine for the Case if the Heuristics 1 and 2 Are True......Page 38
 2.5 Construction of a Feasible Schedule Which Is Optimal for the Criterion of the Total Earliness of Tasks Minimization......Page 41
 References......Page 51
 3.1 Introduction......Page 52
 3.2 Problem 1. Machines with Equal Productivities......Page 53
   3.2.1.1 SSOs for Vector Criterion 1......Page 54
   3.2.1.2 SSO for Scalar Criterion 2......Page 56
   3.2.2.1 The First Polynomial Component of PSC-Algorithm A......Page 57
   3.2.2.2 The Second Polynomial Component of PSC-Algorithm A......Page 58
   3.2.3.1 The First Polynomial Component of PSC-Algorithm B......Page 62
   3.2.3.2 The Second Polynomial Component of PSC-Algorithm B......Page 63
 3.3 Illustrative Examples for Problem 1......Page 64
 3.4 Problem 2. Machines with Various Productivities......Page 83
   3.4.1.1 Construction of SSO #1 for Criterion 1......Page 84
   3.4.1.3 Construction of SSO #1 for Criterion 2......Page 85
   3.4.2.1 The First Polynomial Component of PSC-Algorithm C......Page 86
   3.4.2.2 The Second Polynomial Component of PSC-Algorithm C......Page 87
   3.4.3.1 The First Polynomial Component of PSC-Algorithm D......Page 89
   3.4.3.2 The Second Polynomial Component of PSC-Algorithm D......Page 90
 3.5 Illustrative Examples for Problem 2......Page 91
 Reference......Page 118
 4.1 The Problem Statement......Page 119
 4.2 Main Theoretical Propositions......Page 120
  4.2.1 Sequence \upsigma ^{ord}......Page 122
  4.2.2 Sequence \upsigma ^{\hskip1pt fp}......Page 135
  4.2.3 Iterations of Optimization......Page 136
  4.2.5 The Current Iteration......Page 138
   4.3.1.1 Algorithm A0 (The Preliminary Stage of the PSC-Algorithm)......Page 157
   4.3.1.2 Algorithm A1 (The Optimization Stage of the PSC-Algorithm)......Page 160
  4.3.2 Properties of the First Polynomial Component of the PSC-Algorithm......Page 167
  4.3.3 Description of the Logic of the PSC-Algorithm Construction for the Case When None of the SSOs Is Satisfied......Page 171
   4.3.3.1 Outline of the Algorithm......Page 176
  4.3.4 Properties of the Exact Subalgorithm for the Problem Solving......Page 181
  4.4.1 Heuristics that Turn the Implementation of the Current Iteration of the Exact Subalgorithm into a Polynomial Subalgorithm......Page 184
  4.4.2 The Approximation Algorithm AA for TWT Problem Solving......Page 186
 4.5 Illustration to the Problem Solving by the PSC-Algorithm Using Procedures A–I......Page 194
 4.6 Illustrative Examples......Page 202
 References......Page 228
 5.1 The Formulation of E/T€1, E/T€2, E/T€3 Problems......Page 230
 5.2 PSC-Algorithm to Solve the Problem of Minimizing the Total Tardiness of Independent Tasks on a Single Machine......Page 233
  5.2.1 Main Theoretical Propositions......Page 234
  5.2.2 Modification of the PSC-Algorithm and Procedures A–I of the TWT Problem for the TT Problem......Page 249
  5.2.3 Properties of the First Polynomial Component of the PSC-Algorithm for the TT Problem Solving......Page 250
  5.2.4 Properties of the Exact Subalgorithm for the TT Problem Solving......Page 251
  5.2.5 Recommendations for Using the Approximation Algorithm......Page 254
  5.3.1 The First Polynomial Component of PSC-Algorithm for the Problem Solving......Page 255
  5.3.2 The Approximation Algorithm for E/T€1 Problem Solving (Algorithm A1)......Page 256
  5.3.3 Example for E/T€1 Problem Solving by Algorithm A1......Page 258
  5.4.2 The Approximation Algorithm for E/T€3 Problem Solving (Algorithm A2: Determining the Latest Start Time of the Tasks Execution at Which the Minimum Functional Value Is Reached)......Page 259
  5.4.3 The Approximation Algorithm for E/T€2 Problem Solving......Page 261
  5.4.4 Examples of E/T€3 Problem Solving by Algorithm A2......Page 262
  5.4.5 The Approximation Algorithm for E/T€2 Problem Solving (Algorithm A3: Determination of the Maximum Start Time of the Tasks Execution in a Given Time Segment)......Page 269
  5.4.6 Examples of E/T€2 Problem Solving......Page 270
 References......Page 272
 6.1 The Problem with the Common for All Machines (Fixed) Start Time of the Tasks Execution......Page 275
  6.1.1 Main Theoretical Thesis......Page 277
  6.1.2 Scheme of the Problem Solving......Page 288
  6.1.3 Description of PSC-Algorithms for the Problem Solving......Page 291
  6.2.2 Studying the Properties of the TTPL Problem and PSC-Algorithm for Its Solving......Page 295
 6.3 Illustrative Example......Page 297
 6.4 Statistical Research of PSC-Algorithms for the TTP Problem......Page 298
 References......Page 299
 7.1 The Problem Formulation......Page 301
 7.2 The Main Theoretical Thesises......Page 302
  7.3.1 Polynomially-Solvable Subclasses of TWCT Problem on a Set of Maximum Priority......Page 308
  7.3.2 The Structure of PSC-Algorithm......Page 317
   7.3.3.1 Sufficient Signs of Optimality of a Feasible Subsequence of Tasks......Page 318
   7.3.3.2 The Main Statements to Substantiate the Rules of a p-Ordered Schedule Construction When the Precedence Relations Are Specified by an Arbitrary Oriented Acyclic Graph......Page 325
   7.3.3.3 Rules of a p-Ordered Schedule Construction for the Case of a Series-Parallel Graph......Page 328
   7.3.3.4 Algorithm a for the Problem Solving When the Precedence Relations Are Specified by a Series-Parallel Graph......Page 334
   7.3.3.5 Theoretical Foundations of Generalization of Algorithm A for the Case When the Precedence Relations Are Specified by an Arbitrary Oriented Acyclic Graph. Formalization of SSO #16 of a Feasible Subsequence......Page 340
  7.3.4 Description of PSC-Algorithm for TWCT Problem Solving When the Precedence Relations Are Specified by an Arbitrary Oriented Acyclic Graph......Page 344
  7.3.5 Example of the Problem Solving......Page 350
 7.4 Statistical Research of the Algorithm for the Problem Solving......Page 352
 References......Page 353
Hierarchical Planning and Decision Making in Network Systems with Limited Resources......Page 355
 8.1 General Description of Systems with Network Representation of Technological Processes and Limited Resources......Page 356
 8.2 Requirements for the Creation of Software for Scheduling and Operational Planning in Systems with Network Representation of Technological Processes and Limited Resources......Page 358
 8.3 Overview of Known Models, Methods and Software for Scheduling and Operational Planning......Page 361
 8.4 Characteristic Features of the Four-Level Model of Planning and Decision Making......Page 375
 8.5 Models and Methods of Decision Making Based on Hierarchical Goal Estimation of Alternatives......Page 380
   8.5.1.1 Weights Estimation by an Empirical PCM Based on Optimization Models with Weighted Components of an Additive Functional......Page 383
   8.5.1.2 Analytic Hierarchy Process Modification......Page 390
   8.5.2.1 Univariate Polynomial Regression Construction from a Redundant Representation Using an Active Experiment......Page 391
   8.5.2.2 Multivariate Polynomial Regression Construction from a Redundant Representation Using an Active Experiment......Page 397
   8.5.2.3 Unknown Function Reconstruction from a Redundant Representation and the Results of a Passive Experiment with a Limited Dataset......Page 401
 References......Page 407
 9.1 The Structure of the Planning System......Page 416
  9.1.1 Structural Elements of the Network Model......Page 418
  9.1.2 Properties of the Technological Process Specified by a Network......Page 420
  9.2.1 The Problem Formulation. The Formalization of Optimality Criteria......Page 426
   9.2.2.1 The Technological Network Aggregation into a Single Machine Model with Precedence Relations Specified by an Oriented Acyclic Graph......Page 438
   9.2.2.2 TWCT Problems Construction for the Corresponding Basic Components of a Synthetic Optimality Criterion......Page 448
  9.2.3 Algorithm for TWCT Problem Solving When Nonzero Weights Are Specified Only for the Terminal Vertices of the Oriented Graph (The TWCTZ Problem)......Page 451
  9.3.1 The Formalization of the Model of the Second Level of Planning Using the Model of the First Level......Page 459
  9.3.2 Coordinated Planning Algorithms. Properties, Heuristics......Page 460
  9.3.3 The Coordinated Plan Analysis in Decision Making Unit......Page 473
 9.4 Unit 4. The Model of the Third Level of Planning (Multi-stage Network Scheduling Problem Construction)......Page 476
  9.5.1 A Method to Solve the Multi-stage Network Scheduling Problem Corresponding a Basic Optimality Criterion......Page 478
  9.5.2 Methods to Solve the Multi-stage Network Scheduling Problem Corresponding a Synthetic Optimality Criterion......Page 482
 9.6 Example of the Methodology Implementation for the Model of the Third Level of Planning Construction from the Initial Data......Page 489
  9.7.1 The Operative Planning Model Formalization......Page 505
  9.7.2 Universal Method of the Operative Planning Problem Solving Using a Modified Method of Planning......Page 507
  9.7.3 The Operative Planning Problem Solving Methodology if the Third Level Planning Problem Solved by a Basic Criterion......Page 515
 9.8 Single Stage Scheduling Problems Used in Hierarchical Planning and Decision Making Models in Network Systems with Limited Resources......Page 517
 9.9 The Universal Informational System of Planning and Decision Making for Small-Series Type Productions......Page 518
 References......Page 525