An Introduction to Optimal Satellite Range Scheduling

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