# Pico-Sat to Ground Control: Optimizing Download Link via Laser Communication
## 3 Satellite Scheduling by a Ground Station  
In this section, we explore the algorithmic solutions for a scheduling problem that arises when a ground station needs to successively communicate with many satellites. A ground station is expected to successively communicate with many satellites. Each satellite has its own orbit; therefore, from the viewpoint of the ground station the satellites appear (and disappear) in different times and from different angles. Moreover, it is expected that for a given ground station at a given time there might be several visible satellites, as illustrated in Figure 1. This, in turn, yields that the ground station should choose with which satellites to communicate. In many real-world situations, such scheduling choices are of high importance. For instance, a ground station may serve as a \"middleman\" that downloads valuable information from the different satellites and then sells this information to various buyers. The value of the downloaded data may vary considerably depending on the satellite with which the ground station chooses to communicate. Consequently, an efficient scheduling policy may lead to high revenues. This financial model can be naturally generalized to any type of utility, not necessarily monetary, that the owner of the ground station may gain from the obtained data. Planet's use-case [21] represents such a large-scale optimization and scheduling problem. The described problem of the ground station is known in the scheduling literature as the \(1|r_{j}|\Sigma w_{i}U_{j}\) problem. Following the \(\alpha|\beta|\gamma\) notation of scheduling problems [34], 1 in the \(\alpha\) field means that there is a single ground station (as opposed to a more involved many-to-many model). Each satellite (job) has a time window in which the ground station can communicate with it. In the scheduling terminology, such a time window is expressed by a _release time_ and a _deadline_ for each job. Having release times for jobs is expressed by the \(r_{j}\) constraint in the \(\beta\) field, whereas the existence of a deadline is implied by the objective function \(\Sigma w_{i}U_{j}\) in the \(\gamma\) field. \(\Sigma U_{j}\) indicates a _unit penalty_ for each job that does not meet the deadline, whereas the multiplication in \(w_{j}\) enables job-dependent weights (utilities). The objective functions in scheduling literature are usually minimization functions. As a consequence, instead of maximizing the utility gained from successful communications with satellites, we minimize the unsuccessful (or missed) communications. More than four decades ago, [PERSON] et al. [35] proved that the \(1|r_{j}|\Sigma w_{j}U_{j}\) problem is strongly NP-hard, even in its unweighted form (\(1|r_{j}|\Sigma U_{j}\)). Nevertheless, some exact algorithms were developed for this intractable problem. [PERSON] et al. [36] proposed a branch-and-bound algorithm that utilizes a Lagrangian lower bound. Their algorithm  
Figure 8: The FSO pico-satellite engineering model. (**a**) The attitude control unit, composed of three tiny reaction wheels, one for each axis, and a tiny flight controller with IMU for controlling each motor. (**b**) SATLLA-2.0 pico-satellite under construction. (**c**) The final model of SATLLA-2B pico-satellite, with its LEDs, camera, laser, UHF antenna, and solar panels. This model was recently successfully launched into LEO. managed to solve most 100-job instances in reasonable time. Slightly better results were obtained by the branch-and-check algorithm of [PERSON] [37]. Despite the improvement in exact solution methods, large-scale problems require heuristic methods. [PERSON] and [PERSON] [38] propose genetic algorithms for solving \(1|r_{j}|\Sigma w_{j}U_{j}\). An advantage of genetic algorithms is that they can be easily adapted to changes in the model. For instance, [PERSON] and [PERSON] [39] also devised a genetic algorithm for a similar problem in which the release times of jobs are not precisely known in advance.