ISBN: 3540403388
TITLE: Decision Analysis, Location Models and Scheduling Problems
AUTHOR: Eiselt, Sandblom
TOC:

Introduction 1
Notation 1
Support Methodology 3
a. Algorithms and Computational Complexity 3
b. Matrix Algebra 5
c. Graphs and Networks 9
d. Linear and Integer Optimization 11
e. Statistics 13
Part I: Analysis of Decision Making 19
1 Multicriteria Decision Making 23
1.1 Vector Optimization 24
1.2 Basic Ideas of Multicriteria Decision Making 29
1.3 Reference Point Methods 37
1.4 Data Envelopment Analysis 40
1.5 Preference Cones 43
1.6 Multiattribute Value Functions 46
1.7 Outranking Methods 50
1.8 Methods Allowing Inconsistent Estimates 61
2 Games Against Nature 73
2.1 Elements of Games Against Nature 73
2.1.1 Basic Components 73
2.1.2 Lotteries and Certainty Equivalents 76
2.1.3 Visualizations of the Structure of Decision Problems 81
2.2 Rules for Decision Making Under Uncertainty and Risk 87
2.3 Multi-Stage Decisions and the Value of Information 99
3 Game Theory 111
3.1 Features of Game Theory 112
3.1.1 Elements and Representations of Games 112
3.1.2 Solution Concepts 116
3.2 Two-Person Zero-Sum Games 122
3.3 Extensions 133
3.3.1 Bimatrix Games 133
3.3.2 Mufti-Stage Games 140
3.3.3 n-Person Games 143
Part II: Location and Layout Decisions 151
1 Fundamentals of Location and Layout Problems 153
1.1 The Nature of Location Problems 153
1.2 The History of Location Models 155
1.3 The Major Elements of Location Problems 157
1.4 Applications of Location Problems 164
2 Location Models on Networks 169
2.1 Covering Models 170
2.1.1 The Location Set Covering Problem 171
2.1.2 The Maximal Covering Location Problem 175
2.2 Center Problems 178
2.2.1 1-Center Problems 179
2.2.2 p-Center Problems 186
2.3 Median Problems 188
2.3.1 Basic Results and Formulation of the Problem 189
2.3.2 1-Median Problems 192
2.3.3 p-Medians Problems194
2.4 Simple and Capacitated Plant Location Problems 205
2.5 An Application of the Capacitated Facility Location Problem 208
3 Continuous Location Models 211
3.1 Covering Problems 212
3.2 Single-Facility Minimax Problems 214
3.3 Minisum Problems 220
3.3.1 Single-Facility Problems 220
3.3.2 Multi-Facility Problems 228
4 Other Location Models 237
4.1 The Location of Undesirable Facilities 237
4.2 p-Dispersion Problems 243
4.3 Location Models with "Equity" Objectives 244
4.4 Hub Location Problems 247
4.5 Competitive Location Problems 248
4.6 Locating Extensive Facilities and Routing in Irregular Spaces 252
5 Layout Models 255
5.1 Facility Layout Planning 256
5.2 Formulations of the Basic Layout Problem 260
5.3 Special Cases of the Quadratic Assignment Problem 266
5.3.1 Triangulation Problems 267
5.3.2 Traveling Salesman Problems 268
5.3.3 Matching Problems 269
5.4 Applications270
5.4.1 Relay Team Running270
5.4.2 Backboard Wiring 271
5.4.3 Building Layout Planning 272
5.4.5 Keyboard Design 273
5.5 Solution Methods 275
5.5.1 Exact Solution Methods 275
5.5.2 Heuristic Solution Methods290
5.5.3 Solving General Facility Layout Problems 292
Part III: Project Scheduling 295
1 Unconstrained Time Project Scheduling 297
1.1 Network Representations 297
1.2 The Critical Path Method 302
1.3 Project Acceleration (Crashing) 309
1.4 Incorporating Uncertainties (PERT) 313
2 Project Scheduling with Resource Constraints 319
2.1. The Problems and its Formulation 319
2.2 Exact Solution methods 326
2.3 Heuristic Methods 328
Part IV: Machine Scheduling Models 333
1 Fundamentals of Machine Scheduling 335
1.1 Introductory Examples 335
1.2 The Models and Their Components 340
1.2.1 Basic Concepts, Notation and Performance Criteria 340
1.2.2 Interpretation and Discussion of Assumptions 345
1.2.3 A Classification Scheme 346
1.3 Algorithmic Approaches 350
2 Single Machine Scheduling 353
2.1 Minimizing Makespan 353
2.2 Minimizing Mean Flow Time 353
2.2.1 The Shortest Processing Time Algorithm 354
2.2.2 The Mean Weighted Flow Time and Other Problems 356
2.3 Minimizing Objectives Involving Due Dates 360
2.3.1 Earliest Due Date Scheduling 360
2.3.2 Other Problems 362
3 Parallel Machine Models 367
3.1 Minimizing Makespan 367
3.1.1 Identical Machines and Tasks of Arbitrary Lengths 367
3.1.2 Other Algorithms for Identical Machines 375
3.1.3 Algorithms for Uniform and Unrelated Machines 381
3.2 Minimizing Mean Flow Time 387
3.2.1 Identical Machines 387
3.2.2 Uniform and Unrelated Machines 389
3.3 Minimizing Maximal Lateness 393
3.3.1 Identical Machines 393
3.3.2 Uniform and Unrelated Machines 396
4 Dedicated Machine and Resource-Constrained Models 399
4.1 Open Shop Scheduling 399
4.2 Flow Shop Scheduling 401
4.3 Job Shop Scheduling 403
4.3.1 Basic Ideas 403
4.3.2 A Branch and Bound Algorithm 407
4.3.3 The Shifting Bottleneck Heuristic 411
4.4 Resource-Constrained Machine Scheduling 415
References 421
Subject Index 453
END
