Online Stochastic Combinatorial Optimization

0.0

The progress in optimization techniques and information technology has made it possible to solve complex problems involving uncertainty and severe time constraints. For example in the airline industry complex fleet assignments, crew scheduling, gate allocation etc. have to be precisely worked out using advance optimization algorithms, but major disruptions like unforeseen weather conditions, strikes, breakdown etc. have also to be reckoned. Increasingly there are many industries and occupations—from manufacturing units and power grid networks to emergency ambulance services to packed scheduling for internet communication and reservation system—need to employ online decision making processes. This book presents the ideal framework, online stochastic combinatorial optimization to address this challenge. The text gives several online stochastic algorithms implementing the framework, provides performance guarantees,and demonstrates a variety of applications. The authors discuss how to relax some of the assumptions in using historical sampling and machine learning and analyze different underlying algorithmic problems before addressing the framework’s possible limitations and suggesting directions for future research. The main innovation in the text lies in the class of online anticipatory algorithms that combine online algorithms (from computer science) and stochastic programming (from operation research), and combinatorial optimization for sequential decision making under uncertainty. Useful for advanced courses in operations research, computer science, and production engineering, this book will also be a useful companion to professionals concerned with optimization technology and online decision making methods. Table of Contents Preface 1. Introduction I ONLINE STOCHASTIC SCHEDULING 2. Online Stochastic Scheduling 3. Theoretical Analysis 4. Packet Scheduling II ONLINE STOCHASTIC RESERVATIONS 5. Online Stochastic Reservations 6. Online Multiknapsack Problems III ONLINE STOCHASTIC ROUTING 7. Vehicle Routing with Time Windows 8. Online Stochastic Routing 9. Online VehicleDispatching 10. Online Vehicle Routing with Time Windows IV LEARNING AND HISTORICAL SAMPLING 11. Learning Distributions 12. Historical Sampling V SEQUENTIAL DECISION MAKING 13. Markov Chance-Decision Processes References Index