Decision Analysis, Location Models, and Scheduling Problems

by Eiselt, Horst A.; Blazewicz, J. (CON); Church, Robert L. (CON); Drexl, A. (CON); Finke, G. (CON); Revelle, Charles S. (CON)

• ISBN13: 9783540403388
• ISBN10: 3540403388
• Format: Hardcover
• Copyright: 2003-11-01
• Publisher: Springer Verlag

Summary

The book presents a unified treatment of decision analysis, location theory and scheduling, with topics ranging from multicriteria decision-making, multiattribute utility theory, classical decision analysis and game theory, to location and layout planning, and to project and machine scheduling. While the emphasis of the book is on models and applications, the most important methods and algorithms, exact as well as heuristic, are described in detail and illustrated by numerical examples. The formulations and the discussion of a large variety of models provide insight into their structures, allowing the user to better evaluate the solutions to the problems.

Table of Contents

Introduction	1	(1)
Notation	1	(2)
Support Methodology	3	(16)
Algorithms and Computational Complexity	3	(2)
Matrix Algebra	5	(4)
Graphs and Networks	9	(2)
Linear and Integer Optimization	11	(2)
Statistics	13	(6)
Part I: Analysis of Decision Making	19	(132)
Multicriteria Decision Making	23	(50)
Vector Optimization	24	(5)
Basic Ideas of Multicriteria Decision Making	29	(8)
Reference Point Methods	37	(3)
Data Envelopment Analysis	40	(3)
Preference Cones	43	(3)
Multiattribute Value Functions	46	(4)
Outranking Methods	50	(11)
Methods Allowing Inconsistent Estimates	61	(12)
Games Against Nature	73	(38)
Elements of Games Against Nature	73	(14)
Basic Components	73	(3)
Lotteries and Certainty Equivalents	76	(5)
Visualizations of the Structure of Decision Problems	81	(6)
Rules for Decision Making Under Uncertainty and Risk	87	(12)
Multi-Stage Decisions and the Value of Information	99	(12)
Game Theory	111	(40)
Features of Game Theory	112	(10)
Elements and Representations of Games	112	(4)
Solution Concepts	116	(6)
Two-Person Zero-Sum Games	122	(11)
Extensions	133	(18)
Bimatrix Games	133	(7)
Multi-Stage Games	140	(3)
n-Person Games	143	(8)
Part II: Location and Layout Decisions	151	(144)
Fundamentals of Location and Layout Problems	153	(16)
The Nature of Location Problems	153	(2)
The History of Location Models	155	(2)
The Major Elements of Location Problems	157	(7)
Applications of Location Problems	164	(5)
Location Models on Networks	169	(42)
Covering Models	170	(8)
The Location Set Covering Problem	171	(4)
The Maximal Covering Location Problem	175	(3)
Center Problems	178	(10)
1-Center Problems	179	(7)
p-Center Problems	186	(2)
Median Problems	188	(17)
Basic Results and Formulation of the Problem	189	(3)
1-Median Problems	192	(2)
p-Medians Problems	194	(11)
Simple and Capacitated Plant Location Problems	205	(3)
An Application of the Capacitated Facility Location Problem	208	(3)
Continuous Location Models	211	(26)
Covering Problems	212	(2)
Single-Facility Minimax Problems	214	(6)
Minisum Problems	220	(17)
Single-Facility Problems	220	(8)
Multi-Facility Problems	228	(9)
Other Location Models	237	(18)
The Location of Undesirable Facilities	237	(6)
p-Dispersion Problems	243	(1)
Location Models with ``Equity'' Objectives	244	(3)
Hub Location Problems	247	(1)
Competitive Location Problems	248	(4)
Locating Extensive Facilities and Routing in Irregular Spaces	252	(3)
Layout Models	255	(40)
Facility Layout Planning	256	(4)
Formulations of the Basic Layout Problem	260	(6)
Special Cases of the Quadratic Assignment Problem	266	(4)
Triangulation Problems	267	(1)
Traveling Salesman Problems	268	(1)
Matching Problems	269	(1)
Applications	270	(5)
Relay Team Running	270	(1)
Backboard Wiring	271	(1)
Building Layout Planning	272	(1)
Keyboard Design	273	(2)
Solution Methods	275	(20)
Exact Solution Methods	275	(15)
Heuristic Solution Methods	290	(2)
Solving General Facility Layout Problems	292	(3)
Part III: Project Scheduling	295	(38)
Unconstrained Time Project Scheduling	297	(22)
Network Representations	297	(5)
The Critical Path Method	302	(7)
Project Acceleration (Crashing)	309	(4)
Incorporating Uncertainties (PERT)	313	(6)
Project Scheduling with Resource Constraints	319	(14)
The Problems and its Formulation	319	(7)
Exact Solution methods	326	(2)
Heuristic Methods	328	(5)
Part IV: Machine Scheduling Models	333	(88)
Fundamentals of Machine Scheduling	335	(18)
Introductory Examples	335	(5)
The Models and Their Components	340	(10)
Basic Concepts, Notation and Performance Criteria	340	(5)
Interpretation and Discussion of Assumptions	345	(1)
A Classification Scheme	346	(4)
Algorithmic Approaches	350	(3)
Single Machine Scheduling	353	(14)
Minimizing Makespan	353	(1)
Minimizing Mean Flow Time	353	(7)
The Shortest Processing Time Algorithm	354	(2)
The Mean Weighted Flow Time and Other Problems	356	(4)
Minimizing Objectives Involving Due Dates	360	(7)
Earliest Due Date Scheduling	360	(2)
Other Problems	362	(5)
Parallel Machine Models	367	(32)
Minimizing Makespan	367	(20)
Identical Machines and Tasks of Arbitrary Lengths	367	(8)
Other Algorithms for Identical Machines	375	(6)
Algorithms for Uniform and Unrelated Machines	381	(6)
Minimizing Mean Flow Time	387	(6)
Identical Machines	387	(2)
Uniform and Unrelated Machines	389	(4)
Minimizing Maximal Lateness	393	(6)
Identical Machines	393	(3)
Uniform and Unrelated Machines	396	(3)
Dedicated Machine and Resource-Constrained Models	399	(22)
Open Shop Scheduling	399	(2)
Flow Shop Scheduling	401	(2)
Job Shop Scheduling	403	(12)
Basic Ideas	403	(4)
A Branch and Bound Algorithm	407	(4)
The Shifting Bottleneck Heuristic	411	(4)
Resource-Constrained Machine Scheduling	415	(6)
References	421	(32)
Subject Index	453