An Introduction to Optimal Satellite Range Scheduling (Springer Optimization and Its Applications (106))

Description

The satellite range scheduling (SRS) problem, an important operations research problem in the aerospace industry consisting of allocating tasks among satellites and Earth-bound objects, is examined in this book. SRS principles and solutions are applicable to many areas, including: Satellite communications, where tasks are communication intervals between sets of satellites and ground stationsEarth observation, where tasks are observations of spots on the Earth by satellitesSensor scheduling, where tasks are observations of satellites by sensors on the Earth. This self-contained monograph begins with a structured compendium of the problem and moves on to explain the optimal approach to the solution, which includes aspects from graph theory, set theory, game theory and belief networks. This book is accessible to students, professionals and researchers in a variety of fields, including: operations research, optimization, scheduling theory, dynamic programming and game theory. Taking account of the distributed, stochastic and dynamic variants of the problem, this book presents the optimal solution to the fixed interval SRS problem and how to migrate results into more complex cases. Reference algorithms and traditional algorithms for solving the scheduling problems are provided and compared with examples and simulations in practical scenarios. Preface Acknowledgments Contents Acronyms Symbols List of Figures List of Tables Part I Introduction 1 Motivation 1.1 Motivation 1.2 Why Optimal Scheduling? 1.3 Why this Book? 1.4 Structure of the Book 1.5 Main Contributions References 2 Scheduling Process 2.1 Scheduling Process 2.2 Scheduler Characteristics 2.3 Satellite Range Scheduling Problems 2.4 Issues Beyond the Scope of this Text References Part II Satellite Range Scheduling 3 The Satellite Range Scheduling Problem 3.1 Problem Formulation 3.1.1 Model for the Scenario 3.1.2 Model for the Requests 3.1.3 Problem Constraints 3.1.3.1 Preemption 3.1.3.2 Number of Entities 3.1.3.3 Duration of the Requests 3.1.3.4 Redundancy 3.1.3.5 Precedence 3.1.3.6 Priority 3.1.4 Schedule Metrics 3.2 Complexity of SRS 3.2.1 Introduction to Complexity Theory 3.2.2 Complexity of the SRS Problem 3.3 General Scheduling Problems 3.3.1 Problem Classification 3.3.2 Problem Reducibility 3.4 Relating Satellite and General Scheduling Problems 3.4.1 One Machine Problems 3.4.1.1 1 rj,pij Uj 3.4.1.2 1 rj,pij, prec Uj 3.4.1.3 1 rj,pij wj Uj 3.4.1.4 1 rj wj Uj 3.4.1.5 1 rj,pij pij pij wj Uj 3.4.2 Several Identical Machines Problems 3.4.2.1 P rj,pij,CΣ Uj 3.4.3 Several Unrelated Machines Problems 3.4.3.1 R rj, pij,CΣ wj Uj 3.4.3.2 R rj, pij,Cx wj Uj 3.4.3.3 R rj, pij,CΣ, prec wj Uj 3.4.3.4 R rj, CΣ wj Uj 3.4.3.5 R rj, CΣ, prec wj Uj 3.4.3.6 R rj,pij pij pij,CΣ wj Uj 3.5 Summary References 4 Optimal Satellite Range Scheduling 4.1 Scenario Model for Fixed Interval SRS 4.2 Optimal Solution for Fixed Interval SRS 4.2.1 Description of the Algorithm 4.2.1.1 Event Generation 4.2.1.2 Graph Creation 4.2.1.3 Longest Path Calculation 4.2.2 Optimality of the Solution and Complexityof the Algorithm 4.3 Extension of the Algorithm 4.3.1 Optimal Discretized Variable Slack SRS 4.3.2 Optimal Fixed Interval SRS with Redundancy 4.4 Remarks on the Complexity 4.4.1 Greedy Earliest Deadline Algorithm 4.4.2 Greedy Maximum Priority Algorithm 4.4.3 About the Topology of the Scenario 4.4.4 About the Number of Passes 4.4.5 About Partial Results 4.5 Graph Generation Example Event Generation Stage Z0 Stage Z1 Stage Z2 Stage Z3 Stage Z4 Rest of Stages 4.6 Simulations 4.6.1 Simulation: Practical Case 4.6.2 Simulation: Worst Case 4.6.3 Simulation: Number of Passes 4.6.4 Simulation: Partial Results 4.7 Summary References Part III Variants of Satellite Range Scheduling 5 Noncooperative Satellite Range Scheduling 5.1 Scenario Model for the SRS Game 5.2 Elements of the SRS Game 5.2.1 Players 5.2.2 Sequential Decisions 5.2.3 Actions 5.2.4 Shared Information 5.2.5 Payoffs 5.2.6 Rationality 5.2.7 Extensive Form 5.3 SRS Game with Perfect Information 5.3.1 Description of the Algorithm 5.3.1.1 Event Generation 5.3.1.2 Graph Elements 5.3.1.3 Graph Creation 5.3.2 Stackelberg Equilibrium Solution 5.3.3 Computational Complexity 5.4 Limited Information Versions of the Problem 5.4.1 SRS Game with Uncertain Priorities 5.4.2 SRS Game with Uncertain Passes 5.5 Remarks on the SRS Game 5.5.1 Equilibrium vs. Security Strategy 5.5.2 Stackelberg Equilibrium vs. Nash Equilibrium 5.5.3 Social Welfare and Price of Anarchy 5.5.4 Machine Scheduling vs. SRS 5.6 Graph Generation Example Stage Z0 Extensive form Representation Stage Z1 EFR Stage Z2 EFR Stage Z3 EFR Stage Z4 EFR Rest of Stages 5.7 Simulations 5.8 Summary References 6 Robust Satellite Range Scheduling 6.1 Scenario Model for Robust SRS 6.1.1 Complexity of the Robust SRS Problem 6.2 Restricted Robust SRS Problem 6.3 Remarks regarding Multiple Scheduling Entities 6.4 Variants of the Robust SRS Problem 6.4.1 Robust SRS with Random Priorities 6.4.2 Robust SRS with Random Durations 6.5 Considerations on the Basic SRS Problem 6.6 Schedule Computation Example 6.7 Simulations 6.8 Summary References 7 Reactive Satellite Range Scheduling 7.1 Scenario Model for Reactive SRS 7.1.1 Complexity of the Reactive SRS Problem 7.2 Restricted Reactive SRS: Single Pass Update Model 7.2.1 Overview of the Algorithm 7.2.2 Preprocessing 7.2.2.1 Phase 1: Forward Graph Creation 7.2.2.2 Phase 2: Backward Graph Creation 7.2.2.3 Phase 3: Best Pairs in Stages Search 7.2.2.4 Phase 4: Alternative Paths Search 7.2.3 Recomputation 7.3 Restricted Reactive SRS: Multiple Pass Update Model 7.4 Schedule Computation Example Phase 1: Forward Graph Creation Phase 2: Backward Graph Creation Phase 3: Best Pairs in Stages Search Phase 4: Alternative Paths Search Phase 5: Recomputation 7.5 Summary References 8 Summary 8.1 Conclusions 8.2 Future Work Glossary Index