CoChat
Sign Up
Cited by 100Satellite Communication SystemsSpacecraft Dynamics and ControlSpacecraft Design and Technology

Optimization-Based Scheduling Method for Agile Earth-Observing Satellite Constellation

Open access
Cho, Doo-Hyun, Kim, Jun-Hong, Choi, Han-Lim, Ahn, Jaemyung·2018·Journal of Aerospace Information Systems
DOI 10.2514/1.i010620
Open this paper in CoChat — free accountOpen PDF

Abstract

This Paper proposes a two-step binary linear programming formulation for task scheduling of a constellation of low-Earth-orbit satellites and demonstrates its applicability and scalability to obtain high-quality solutions using a standard mixed-integer linear programming solver. In this instance, the goal of satellite constellation task scheduling is to allocate each task for the satellites and to determine the task starting times in order to maximize the overall mission performance metric. The scheduling problem is formulated to find the solution by first finding a set of candidate communication time intervals for each satellite/ground-station pair as one of the key constraints and time tabling the observation task to acquire the user-requested data, with the incorporation of key constraints for satellite constellation operation. Numerical experiments are designed for investigating the trends, sensitivity, and characteristics of scheduling outputs based on multiple representative instances. The performance of the scheduling solutions by the proposed two-step binary linear programming method exhibits significant improvement of up to 35% in the number of assignments and the sum of profits over the general greedy algorithm.

Integrity signals

Registry

Crossref · 10.2514/1.i010620

Cites

59 of 60 references verified0 citation errors · 1 not checkable

Statistics

Nothing to recompute.

Claims the paper makes

0 of 8 cited sources checked · 0 supported · 0 flagged

  • Findingown data

    For a constellation of up to 50 satellites at 500 km altitude with a minimum elevation angle greater than 5 degrees, the ground-control center can see only one satellite at a time.

    “For a constellation of up to 50 satellites, only a single satellite can be seen from the ground-control center with the orbit altitude set as 500 km and the minimum elevation angle at which the ground station can communicate with the satellite greater than 5 deg.”
    Quote in the paperSubstantial claim
  • Findingown data

    The number of observation tasks assigned to satellite scheduling increased as the numbers of given tasks and ground stations increased.

    “Figure 9 reveals that the number of observation tasks assigned to satellite scheduling increased as the numbers of given tasks and ground stations increased.”
    Quote in the paperNot a substantial claim
  • Findingown data

    Most instances exhibited a similar pattern in how the upper bounds and solution values changed.

    “We found that most instances had a similar tendency on a change of the upper bounds and solution values.”
    Quote in the paperSubstantial claim
  • Findingown data

    When the number of tasks exceeds 500, the calculation usually finishes without finding the optimal solution.

    “When the number of tasks is more than 500, the calculation is completed without finding the optimal solution in most cases.”
    Quote in the paperNot a substantial claim
  • Findingown data

    Among the parameters in Table 1, the number of observation tasks has the strongest effect on computation time.

    “Among the parameters in Table 1, the number of observation tasks has the greatest influence on computation time.”
    Quote in the paperNot a substantial claim
  • Classified as probably not a substantial claim. 14
  • May combine two claims. 13

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Findingown data

    A clear trend depending on the number of tasks and satellites is visible in the upper plot of Fig. 8.

    “A clear trend depending on the number of tasks and satellites is shown in the upper plot of Fig. 8.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingown data

    The proposed two-step binary linear programming formulation for scheduling a low-Earth-orbit satellite constellation can be solved with a standard mixed-integer linear programming solver to obtain high-quality solutions and is applicable and scalable to representative instances.

    “This Paper proposes a two-step binary linear programming formulation for task scheduling of a constellation of low-Earth-orbit satellites and demonstrates its applicability and scalability to obtain high-quality solutions using a standard mixed-integer linear programming solver.”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: All parameters needed for task scheduling, including the satellite orbits, are assumed to be known beforehand.

  • May combine two claims.

    Findingown data

    After 10^2 seconds, only the upper bounds from LP relaxation are tightened as time increases, while the best-known solution values change little.

    “After that, only the upper bounds from LP relaxation are tightened as the time increases and the best-known solution values have little change.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data

    The optimal solution is found within a reasonable time for up to approximately 400 tasks, and for up to 500 tasks the optimal solution is found within the time limit when there are up to three satellites.

    “Through both plots, it can be seen that the optimal solution is found within a reasonable time until the number of tasks is approximately 400, and up to 500 tasks, the optimal solution is found within the time limit up to three satellites.”
    Quote in the paperSubstantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Findingown data

    The FIFO algorithm solved the largest instance in less than one second.

    “We also excluded the computation time of the FIFO algorithm because the largest instance was solved in under 1 s.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Findingnone given

    In the simulation, most time intervals used for the data and energy constraints were set to be similar to or shorter than the processing time.

    “In the simulation, most time intervals used to set the data and energy constraints are set to be similar to or shorter than the processing time, which can be an answer for condition 4.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingown data

    In that extreme instance, the greedy algorithm first included task 1, then scheduled task 4 rather than task 3 because task 3 could not be executed due to a large roll-angle difference, and afterward scheduled task 7 rather than task 6.

    “In the case of the greedy algorithm, task 1, which was the first to be encountered by a satellite, was included in the schedule at first, and the satellite controlled its attitude to the left side.After task 1, task 4 with a small setup time was scheduled instead of task 3, which was inexecutable because of the huge roll angle difference.Likewise, after task 4, task 7 was scheduled instead of task”
    Quote in the paperNot a substantial claim
    • The authors state this as an assumption: In the extreme-instance analysis, the satellite's initial pitch and roll angles were assumed to be zero so that it pointed at the nadir.

  • May combine two claims.

    Findingown data

    In the same extreme instance, the TSBLP method rotated the satellite to the right and scheduled more tasks than the greedy algorithm.

    “On the contrary, in the case of the TSBLP method, the satellite turned to the right to schedule more tasks than the greedy algorithm.”
    Quote in the paperNot a substantial claim
    • The authors state this as an assumption: In the extreme-instance analysis, the satellite's initial pitch and roll angles were assumed to be zero so that it pointed at the nadir.

  • May combine two claims.

    Findingreasoning

    The two methods showed little difference until 200 given tasks, but the difference then grew gradually, reaching up to 30% for the number of assigned tasks and 35% for the objective value.

    “There was little difference between the results of the two methods until the number of the given tasks was 200, but the difference increased gradually up to 30% for the number of assigned tasks and 35% for the objective value.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data

    As the number of overlaps grew, the problem instance became more complex and the greedy algorithm's performance worsened, in contrast to the case where only the number of tasks increased.

    “we confirmed that the complexity of the problem instance increased and the performance of the greedy algorithm is degraded as the overlaps increased as opposed to when only the number of tasks increased.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingown data

    For given numbers of observation tasks, the mean order of overlap and the standard deviation of overlap were approximately: 100 tasks: mean 1.53, std 0.23; 200 tasks: mean 1.93, std 0.44; 300 tasks: mean 2.26, std 0.58; 500 tasks: mean 2.94, std 0.91; 700 tasks: mean 3.44, std 1.18.

    “According to the given number of observation tasks, the mean order of overlap and the standard of overlap are approximately as follows (number-mean, std): (100-1.53,0.23), (200-1.93,0.44), (300-2.26,0.58), (500-2.94,0.91), (700-3.44,1.18).”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingown data

    With 700 observation tasks and a 2-day planning horizon, rewards did not increase substantially once the data transfer rate exceeded 0.6, and the gap to the unrestricted model stayed around 30-35%.

    “Because of the data and energy constraints, the rewards did not substantially increase when the data transfer rate exceeded 0.6, and the gap with the unrestricted model was maintained around 30-35%.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Findingown data

    With 700 observation tasks, 4 ground stations, and a 1-day planning horizon, the result values rose as the number of satellites increased, and the average gap between methods was about 30%.

    “The result values were increased as the number of satellites increased, and the average gap between each method was around 30%.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S4 (based).

    Premisenone given

    The authors are unaware of any studies that explicitly study the satellite constellation scheduling problem as formulated in this paper.

    “Although much work has focused on the scheduling problem, we are unaware of any studies explicitly studying the problem as formulated in this Paper.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S4 (based).

    Premisenone given

    Many formulations and approaches in the reviewed satellite operation scheduling literature ignored important constraints such as energy and data.

    “Generally, many of the formulations and approaches in the reviewed papers dealing with satellite operation scheduling problems ignored important constraints, such as energy and data.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Premisecitation

    The simplest version of either satellite communication scheduling or observation scheduling is NP-hard, and finding optimal solutions becomes extremely difficult as problem size grows.

    “The simplest version of either problem belongs to the NP-hard (non-deterministic polynomial-time hard) class [8,9], and it is extremely difficult to obtain the optimal solution as the size of the problem increases.”
    Quote in the paperSubstantial claim0 of 2 sources checked
    • cites [8] 8. Garey, M. R., and Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, Macmillan Higher Education, 1979. Algorithm 1 FIFO Greedy Algorithm Input: Download candidate intervals, information about satellites, and observation tasks Output: Constellation mission schedulings for each satellite 1: procedure SCHEDULEFIFO 2: for each satellite s, do 3: Initialize data and energy value 4: Plan s ←fg ⊳Plan s : schedule of satellite s 5: end for 6: TW O ← ∪ j∈J;s∈S TW O j;s ⊳TW O : universal set of observation time windows 7: Sort TW O in time ascending order 8: t←0 9

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

    • cites [9] 9. Barbulescu, L., Watson, J.-P., Whitley, L. D., and Howe, A. E., "Scheduling Space-Ground Communications for the Air Force Satellite Control Network," Journal of Scheduling, Vol. 7, No. 1, 2004, pp. 7-34. doi:10.1023/B:JOSH.0000013053.32600.3c source

  • Probably not a substantial claim: may not pass S2 (checkable).

    Premisereasoning

    To construct the satellite scheduling problem realistically, more constraints and practical inputs, including parameters for operating the satellite constellation system, are needed.

    “To construct the problem realistically, more constraints and practical inputs are needed, including parameters for operating the system of the satellite constellation.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation

    The most common approach in previous satellite scheduling studies is a greedy algorithm with task priorities.

    “The most common approach is a greedy algorithm with task priorities [7,[10][11][12][13][14].”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [7,[10][11][12][13][14]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • May combine two claims.

    Interpretationown data

    The small difference between three and four ground stations arose because the fourth station was intentionally placed near the second station, and few observation tasks existed between them.

    “Little difference was found between the cases of three and four ground stations in each instance because the position of the fourth ground station was intentionally positioned near to the second station, and only a few observation tasks existed between them.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Premisecitation

    More recent work has broadened the scheduling problem to include data routing or energy constraints.

    “In a different way, recent studies have tended to expand the existing scheduling problem considering data routing or energy constraints.[2,9,[53][54][55][56][57][58].”
    Quote in the paperNot a substantial claim0 of 1 sources checked
    • cites [2,9,[53][54][55][56][57][58]

      Couldn’t be matched to a paper in Crossref, so it can’t be checked.

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

    Premisenone given

    Most studies on scheduling Earth observation satellites concentrated on the single-satellite problem.

    “Numerous studies have been developed on scheduling EOSs, and most of them concentrated on the single-satellite problem.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

    Interpretationnone given

    For the negative energy phenomenon to occur, the battery energy level must be close to zero.

    “1) The energy level of the battery should be close to zero.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

    Interpretationnone given

    For the negative energy phenomenon to occur, the processing time must be shorter than the given time interval.

    “4) The processing time must be shorter than the given time interval.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Interpretationreasoning

    For the negative energy phenomenon to occur, the energy generated must change rapidly.

    “3) The energy generated must change rapidly.”
    Quote in the paperNot a substantial claim

  • May combine two claims.

    Interpretationown data

    These values are not representative because tasks are heavily concentrated in a specific part of the Earth, so no time window exists for most of the planning horizon.

    “In general, however, the given values are not representative because the tasks are heavily crowded on a specific part of the Earth, so a time window does not exist on most of the planning horizon (the upper plot of Fig. 10).”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Interpretationnone given

    For the negative energy phenomenon to occur, the energy consumption per unit time must exceed the amount generated by the solar panel.

    “2) The energy consumption per unit time should be higher than the amount generated by the solar panel.”
    Quote in the paperNot a substantial claim

  • Probably not a substantial claim: may not pass S3 (load-bearing), S4 (based).

    Interpretationreasoning

    A feasible solution from the previous model can have a negative energy level if a download or observation task and solar energy generation together cause a sharply nonlinear change in energy within a time interval.

    “The energy level of a feasible solution from the previous model can be thought to be negative if a download or observation task and energy generation via a solar panel together lead to a sharply nonlinear change of energy value in a certain time interval.”
    Quote in the paperNot a substantial claim
27 of 27

  • The authors state this as an assumption.

    For wide-area coverage requests, the mission center is assumed to divide the region of interest into several strips.

    “For the wide-area coverage mode, it is assumed that the mission center appropriately divides the region of interest into several strips.”

  • The authors state this as an assumption.

    For requests with multiple image strips, each strip is assumed to be weighted in proportion to its expected image acquisition time.

    “for the request consisting of multiple image strips, it is assumed that each strip is weighted proportionally to the expected image acquisition time, also known as the processing time.”

  • The authors state this as an assumption.

    For each ground station, data are assumed to be downloaded from only one satellite during a pass.

    “For each ground station, we assume that data are downloaded from a single satellite as it passes over the station.”

  • The authors state this as an assumption.

    Tasks are nonpreemptive: once a satellite starts a task, it cannot be interrupted before the task finishes.

    “In this Paper, tasks are nonpreemptive; in other words, once a satellite begins to execute a certain task, it cannot be interrupted by another task until completion of the first task.”

  • The authors state this as an assumption.

    The setup time between two observation tasks is assumed to be determined by the difference in their roll angles.

    “While the detailed quantification of the setup time involves knowledge of full attitude dynamics of the satellite and the associated controllers, this Paper assumes that the setup time between two observation tasks is represented in terms of the differences in the roll angles.”

  • The authors state this as an assumption.

    The setup time between two download tasks is assumed to depend mainly on the difference in the antenna roll angles at the ground station.

    “It is primarily dependent on the differences in the roll angles of the antenna on the ground station.”

  • The authors state this as an assumption.

    The minimum allowable onboard data storage is assumed to be zero.

    “The storage has a certain positive minimum and maximum allowable data limit denoted as d min and d max , where d min is assumed to be 0.”

  • The authors state this as an assumption.

    The separation of download scheduling and mission scheduling assumes that a suitable mechanism exists to choose the ground-control center for each satellite download task.

    “This separation of the download scheduling and mission scheduling assumes that there exists an appropriate mechanism to determine the ground-control center for each download task of a satellite.”

  • The authors state this as an assumption.

    All parameters needed for task scheduling, including the satellite orbits, are assumed to be known beforehand.

    “To solve the TSBLP problem, all related parameters for task scheduling including the satellite orbits are assumed to be known in advance.”

  • The paper relies on this without support.

    If several ground stations are within a satellite's communication range, using a simple heuristic to select the ground station is assumed not to cause significant performance loss.

    “In case there are multiple ground stations within the communication range of a satellite, a simple heuristic to choose the ground station would not incur significant performance degradation.”

  • The paper relies on this without support.

    Satellite applications need highly efficient schedules to collect more data.

    “although satellite applications require highly efficient schedule solutions to obtain more data.”

  • The paper relies on this without support.

    Satellite communication scheduling and observation scheduling are strongly linked through resource use, and their solutions depend on each other.

    “These problems are strongly connected to each other in terms of the resource usage (e.g., time and energy), and their solutions are interdependent.”

  • The authors state this as an assumption.

    In the extreme-instance analysis, the satellite's initial pitch and roll angles were assumed to be zero so that it pointed at the nadir.

    “the initial pitch and roll angle were assumed to be 0 for the satellite to point to the nadir.”
13 of 13

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

Each contradiction between two passages listed here was confirmed by an independent check.

  • Data-transfer-rate results point to two different figures

    Minor

    The results paragraph identifies Fig. 13 as showing the data-transfer-rate comparison, but then directs readers to the upper plot of Fig. 12 for a comparison in that discussion. The figure captions identify Fig. 12 as the satellite-count comparison and Fig. 13 as the data-transfer-rate comparison.

  • Unrestricted-model plot is attributed to the wrong figure

    Minor

    The data-transfer-rate plot is identified as Fig. 13 and shows the unrestricted series, but the accompanying description directs readers to Fig. 12 for that series.

  • Data and energy levels are assigned opposite interval endpoints

    Minor

    The nomenclature defines both levels at the end of an interval, but the constraint descriptions place them at its beginning.

3 of 3

Cites

Flagged first, then by citations

Cited by

Sorted by citations

Related

Authors
Cho, D.-H., Kim, J.-H., Choi, H.-L., & Ahn, J.
Affiliations
  • Korea Advanced Institute of Science and Technology (KR)
  • Korea Advanced Institute of Science and Technology, Daejeon 34141, Republic of Korea
ORCID
Venue
Journal of Aerospace Information Systems
Publisher
American Institute of Aeronautics and Astronautics (AIAA)
Published
2018-11
Volume
15
Issue
11
Pages
611-626
ISSN
2327-3097 (ISSN-L)
DOI
10.2514/1.i010620
OpenAlex
W2895574744
Cited by
98
References
46
Citations by year
2026: 9 · 2025: 20 · 2024: 18 · 2023: 12 · 2022: 15 · 2021: 8 · 2020: 11 · 2019: 5
FWCI
4.88
Type
journal article
Language
en
Open access
Locations
Journal of Aerospace Information Systems (publishedVersion)
Funders
National Research Foundation of Korea (NRF-2016M1A3A3A02017919)
Topics
  • Physical Sciences › Engineering › Aerospace Engineering › Satellite Communication Systems
  • Physical Sciences › Engineering › Aerospace Engineering › Spacecraft Dynamics and Control
  • Physical Sciences › Engineering › Aerospace Engineering › Spacecraft Design and Technology
Keywords
low Earth orbit satellites, binary linear programming, mixed-integer linear programming, ground station communication, greedy algorithm comparison

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Claims read by deepseek-v4.1-flash under definition version 3 (extract-v3) on 2026-09-28.

Classified by jev-1.13-20260917 (gold-guideline-v0.2) on 2026-09-28.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review