# An Efficient Local Search Heuristic for Earth Observation Satellite Integrated Scheduling
## 3 Model
### Mathematical Formulation  
An observation activity is to be arranged within a VTW and a download activity within a DW. The basic elements of scheduling are VTWs and DWs. We use \(\mathcal{V}\) to represent the union of available VTWs of all user requests and \(\mathcal{D}\) to represent the union of all download windows. For simplicity, we define \(\mathcal{N}=\mathcal{V}\cup\mathcal{D}\). A VTW \(i\) is associated with the feature of the corresponding request: \(p_{i}\), \(d_{i}\). \(p_{i}\) is the profit, and \(d_{i}\) is the minimum duration to accomplish the observation. For a satellite \(a\) to accomplish the request, the total occupied memory is the imaging data rate times imaging duration, \(d_{i}p_{a}\). The total time required for downloading the image is \(\frac{d_{i}|p_{a}}{b_{a}}\). The start and end of a VTW or a DW \(i\) are denoted as \(s_{i}\) and \(e_{i}\).  
We use matrix \(H\) to identify the associated user request of a VTW and \(H_{tr}\) equals 1 when VTW \(i\) is associated with request \(r\), 0 otherwise. Matrix \(U\) indicates the associated satellite and \(U_{iu}\) equals 1 if VTW \(i\) is associated with satellite \(a\), 0 otherwise. As the VTW and DW are continuous time intervals, we discretize these time windows uniformly into \(K\) time points and we define \(\mathcal{K}=\{1,2,...,K\}\). \(TT_{ij}^{k}\) is the time required for a EOS to maneuver from \(i\) to \(j\), starting at the \(k_{th}\) time point of \(i\).  
We use the following decision variables to build our MIP model:  
1. \(y_{i}:\) is a binary variable that equals 1 if window \(i\)(VTW or DW) is included in the observation plan, 0 otherwise.
2. \(x_{ij}:\) is a binary variable which equals 1 if a satellite reaches window \(j\) after \(i\), 0 otherwise.
3. \(z_{ij}^{k}:\) is a binary variable which equals 1 if a satellite visits window \(j\) after \(i\), leaving \(i\) at the \(k_{th}\) time point of \(i\), 0 otherwise.
4. \(s_{i}:\) indicates the time instant at which the observation or download activity at window \(i\) starts.
5. \(w_{i}:\) indicates the memory level of a EOS at VTW \(i\).
6. \(t_{l}:\) indicates the transmission duration of a download activity \(l\).  
Given the above definitions, we present an integer linear programming (ILP) model for the EOSIS problem:  
\[Maximize:\sum_{i\in\mathcal{T}}p_{i}y_{i}\] (1) _subject to_ : (2) \[\sum_{j\in\mathcal{V}}x_{ji}-\sum_{i\in\mathcal{V}}x_{ij}=0, \forall i\in\mathcal{N} \tag{3}\] \[\sum_{i\in\mathcal{V}}H_{ir}y_{i}\leq 1, \forall r\in\mathcal{R}\] (4) \[\sum_{k\in\mathcal{K}}(z_{ij}^{k}TT_{ij}^{k})+d_{i}+s_{i}\leq s_{ j}+(1-x_{ij})M, \forall i,j\in\mathcal{N}\] (5) \[l_{i}\leq s_{i}\leq u_{i}, \forall i\in\mathcal{N}\] (6) \[0\leq w_{j}\leq w_{i}-d_{i}p_{a}+(1-x_{ij})M, \forall i\in\mathcal{N},j\in\mathcal{V}\] (7) \[w_{i}+t_{l}b_{a}-(1-x_{ij})M\leq w_{j}\leq w_{i}+t_{l}b_{a}+(1-x_ {ij})M, \forall i\in\mathcal{N},j\in\mathcal{D}\] (8) \[\sum_{k\in\mathcal{K}}z_{ij}^{k}=x_{ij}, \forall i,j\in\mathcal{N}\] (9) \[\sum_{j\in\mathcal{N}}x_{ij}=y_{i}, \forall i\in\mathcal{N} \tag{10}\]  
The goal of the EOS scheduling problem is to maximize the total profit. Constraint 3 ensures the integrity and validity of the observation schedule. Constraint 4 indicates the fact that each target should only be observed once.  
Time constraints is modeled by 5 and 6. Constraint 5 models the time consumed by maneuver operation and imaging process. Constraint 6 is the VTW constraint.  
Memory constraints are modeled by 7 and 8. Constraint 7 models the memory consumed by imaging process. Constraint 8 models the change of onboard memory level by download activity.  
Constraints 9 and 10 define the relationship between three binary decision variables.  
Given the above ILP model, the preliminary experimental results showed that CPLEX is able to solve instances with very limited size given a time limit of five hours. To solve large-sized real-life problems, we resort to a heuristic local search method introduced in the next section.