IDEAS home Printed from https://ideas.repec.org/a/eee/jomega/v53y2015icp115-123.html
   My bibliography  Save this article

Satellite downlink scheduling problem: A case study

Author

Listed:
  • Karapetyan, Daniel
  • Mitrovic Minic, Snezana
  • Malladi, Krishna T.
  • Punnen, Abraham P.

Abstract

The synthetic aperture radar (SAR) technology enables satellites to efficiently acquire high quality images of the Earth surface. This generates significant communication traffic from the satellite to the ground stations, and, thus, image downlinking often becomes the bottleneck in the efficiency of the whole system. In this paper we address the downlink scheduling problem for Canada׳s Earth observing SAR satellite, RADARSAT-2. Being an applied problem, downlink scheduling is characterised with a number of constraints that make it difficult not only to optimise the schedule but even to produce a feasible solution. We propose a fast schedule generation procedure that abstracts the problem specific constraints and provides a simple interface to optimisation algorithms. By comparing empirically several standard meta-heuristics applied to the problem, we select the most suitable one and show that it is clearly superior to the approach currently in use.

Suggested Citation

  • Karapetyan, Daniel & Mitrovic Minic, Snezana & Malladi, Krishna T. & Punnen, Abraham P., 2015. "Satellite downlink scheduling problem: A case study," Omega, Elsevier, vol. 53(C), pages 115-123.
    • Handle: RePEc:eee:jomega:v:53:y:2015:i:c:p:115-123
    DOI: 10.1016/j.omega.2015.01.001
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0305048315000031
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.omega.2015.01.001?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Yenisey, Mehmet Mutlu & Yagmahan, Betul, 2014. "Multi-objective permutation flow shop scheduling problem: Literature review, classification and current trends," Omega, Elsevier, vol. 45(C), pages 119-135.
    2. Sawik, Tadeusz, 2010. "An integer programming approach to scheduling in a contaminated area," Omega, Elsevier, vol. 38(3-4), pages 179-191, June.
    3. Rom, Walter O. & Tukel, Oya Icmeli & Muscatello, Joseph R., 2002. "MRP in a job shop environment using a resource constrained project scheduling model," Omega, Elsevier, vol. 30(4), pages 275-286, August.
    4. Martin, Clarence H, 2009. "A hybrid genetic algorithm/mathematical programming approach to the multi-family flowshop scheduling problem with lot streaming," Omega, Elsevier, vol. 37(1), pages 126-137, February.
    5. Chen, Binchao & Matis, Timothy I., 2013. "A flexible dispatching rule for minimizing tardiness in job shop scheduling," International Journal of Production Economics, Elsevier, vol. 141(1), pages 360-365.
    6. Siwate Rojanasoonthon & Jonathan Bard, 2005. "A GRASP for Parallel Machine Scheduling with Time Windows," INFORMS Journal on Computing, INFORMS, vol. 17(1), pages 32-51, February.
    7. Sterna, Malgorzata, 2011. "A survey of scheduling problems with late work criteria," Omega, Elsevier, vol. 39(2), pages 120-129, April.
    8. J-F Cordeau & G Laporte, 2005. "Maximizing the value of an Earth observation satellite orbit," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(8), pages 962-968, August.
    9. Kolisch, Rainer, 1996. "Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation," European Journal of Operational Research, Elsevier, vol. 90(2), pages 320-333, April.
    10. Hartmann, Sönke & Briskorn, Dirk, 2010. "A survey of variants and extensions of the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 207(1), pages 1-14, November.
    11. Lin, Shih-Wei & Ying, Kuo-Ching, 2013. "Minimizing makespan in a blocking flowshop using a revised artificial immune system algorithm," Omega, Elsevier, vol. 41(2), pages 383-389.
    12. M Vanhoucke & E Demeulemeester & W Herroelen, 2002. "Discrete time/cost trade-offs in project scheduling with time-switch constraints," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 53(7), pages 741-751, July.
    13. Daniel Karapetyan & Snezana Mitrovic-Minic & Krishna T. Malladi & Abraham P. Punnen, 2015. "The Satellite Downlink Scheduling Problem: A Case Study of RADARSAT-2," International Series in Operations Research & Management Science, in: Katta G. Murty (ed.), Case Studies in Operations Research, edition 127, chapter 21, pages 497-516, Springer.
    14. Bianchessi, Nicola & Cordeau, Jean-Francois & Desrosiers, Jacques & Laporte, Gilbert & Raymond, Vincent, 2007. "A heuristic for the multi-satellite, multi-orbit and multi-user management of Earth observation satellites," European Journal of Operational Research, Elsevier, vol. 177(2), pages 750-762, March.
    15. R. Martí & J. Marcos Moreno-Vega & A. Duarte, 2010. "Advanced Multi-start Methods," International Series in Operations Research & Management Science, in: Michel Gendreau & Jean-Yves Potvin (ed.), Handbook of Metaheuristics, chapter 0, pages 265-281, Springer.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Bingyu Song & Feng Yao & Yuning Chen & Yingguo Chen & Yingwu Chen, 2018. "A Hybrid Genetic Algorithm for Satellite Image Downlink Scheduling Problem," Discrete Dynamics in Nature and Society, Hindawi, vol. 2018, pages 1-11, May.
    2. Rodriguez-Tello, Eduardo & Lardeux, Frédéric & Duarte, Abraham & Narvaez-Teran, Valentina, 2019. "Alternative evaluation functions for the cyclic bandwidth sum problem," European Journal of Operational Research, Elsevier, vol. 273(3), pages 904-919.
    3. Troilo, Michael & Bouchet, Adrien & Urban, Timothy L. & Sutton, William A., 2016. "Perception, reality, and the adoption of business analytics: Evidence from North American professional sport organizations," Omega, Elsevier, vol. 59(PA), pages 72-83.
    4. Xiao, Yiyong & Zhang, Siyue & Yang, Pei & You, Meng & Huang, Jiaoying, 2019. "A two-stage flow-shop scheme for the multi-satellite observation and data-downlink scheduling problem considering weather uncertainties," Reliability Engineering and System Safety, Elsevier, vol. 188(C), pages 263-275.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Lin, Shih-Wei & Ying, Kuo-Ching, 2016. "Optimization of makespan for no-wait flowshop scheduling problems using efficient matheuristics," Omega, Elsevier, vol. 64(C), pages 115-125.
    2. Yang-Kuei Lin & Chin Soon Chong, 2017. "Fast GA-based project scheduling for computing resources allocation in a cloud manufacturing system," Journal of Intelligent Manufacturing, Springer, vol. 28(5), pages 1189-1201, June.
    3. Shi, Yuhui & Reich, Daniel & Epelman, Marina & Klampfl, Erica & Cohn, Amy, 2017. "An analytical approach to prototype vehicle test scheduling," Omega, Elsevier, vol. 67(C), pages 168-176.
    4. Tamara Borreguero Sanchidrián & Tom Portoleau & Christian Artigues & Alvaro García Sánchez & Miguel Ortega Mier & Pierre Lopez, 2024. "Large neighborhood search for an aeronautical assembly line time-constrained scheduling problem with multiple modes and a resource leveling objective," Annals of Operations Research, Springer, vol. 338(1), pages 13-40, July.
    5. Chen, Xiaoyu & Reinelt, Gerhard & Dai, Guangming & Spitz, Andreas, 2019. "A mixed integer linear programming model for multi-satellite scheduling," European Journal of Operational Research, Elsevier, vol. 275(2), pages 694-707.
    6. Ghazaleh Ahmadi & Reza Tavakkoli-Moghaddam & Armand Baboli & Mehdi Najafi, 2022. "A decision support model for robust allocation and routing of search and rescue resources after earthquake: a case study," Operational Research, Springer, vol. 22(2), pages 1039-1081, April.
    7. Tangpattanakul, Panwadee & Jozefowiez, Nicolas & Lopez, Pierre, 2015. "A multi-objective local search heuristic for scheduling Earth observations taken by an agile satellite," European Journal of Operational Research, Elsevier, vol. 245(2), pages 542-554.
    8. Pan, Quan-Ke & Ruiz, Rubén, 2012. "An estimation of distribution algorithm for lot-streaming flow shop problems with setup times," Omega, Elsevier, vol. 40(2), pages 166-180, April.
    9. Alessandro Hill & Eduardo Lalla-Ruiz & Stefan Voß & Marcos Goycoolea, 2019. "A multi-mode resource-constrained project scheduling reformulation for the waterway ship scheduling problem," Journal of Scheduling, Springer, vol. 22(2), pages 173-182, April.
    10. Luise-Sophie Hoffmann & Carolin Kellenbrink & Stefan Helber, 2020. "Simultaneous structuring and scheduling of multiple projects with flexible project structures," Journal of Business Economics, Springer, vol. 90(5), pages 679-711, June.
    11. Xiaowei Lin & Jing Zhou & Lianmin Zhang & Yinlian Zeng, 2021. "Revenue sharing for resource reallocation among project activity contractors," Annals of Operations Research, Springer, vol. 301(1), pages 121-141, June.
    12. Kellenbrink, Carolin & Helber, Stefan, 2015. "Scheduling resource-constrained projects with a flexible project structure," European Journal of Operational Research, Elsevier, vol. 246(2), pages 379-391.
    13. Ramírez Palencia, Alberto E. & Mejía Delgadillo, Gonzalo E., 2012. "A computer application for a bus body assembly line using Genetic Algorithms," International Journal of Production Economics, Elsevier, vol. 140(1), pages 431-438.
    14. Bingyu Song & Feng Yao & Yuning Chen & Yingguo Chen & Yingwu Chen, 2018. "A Hybrid Genetic Algorithm for Satellite Image Downlink Scheduling Problem," Discrete Dynamics in Nature and Society, Hindawi, vol. 2018, pages 1-11, May.
    15. Feifei Li & Zhe Xu, 2018. "A multi-agent system for distributed multi-project scheduling with two-stage decomposition," PLOS ONE, Public Library of Science, vol. 13(10), pages 1-24, October.
    16. Jang, Jinbong & Choi, Jiwoong & Bae, Hee-Jin & Choi, In-Chan, 2013. "Image collection planning for KOrea Multi-Purpose SATellite-2," European Journal of Operational Research, Elsevier, vol. 230(1), pages 190-199.
    17. Shai Krigman & Tal Grinshpoun & Lihi Dery, 2024. "Scheduling of Earth observing satellites using distributed constraint optimization," Journal of Scheduling, Springer, vol. 27(5), pages 507-524, October.
    18. Naber, Anulark & Kolisch, Rainer, 2014. "MIP models for resource-constrained project scheduling with flexible resource profiles," European Journal of Operational Research, Elsevier, vol. 239(2), pages 335-348.
    19. Lei He & Mathijs Weerdt & Neil Yorke-Smith, 2020. "Time/sequence-dependent scheduling: the design and evaluation of a general purpose tabu-based adaptive large neighbourhood search algorithm," Journal of Intelligent Manufacturing, Springer, vol. 31(4), pages 1051-1078, April.
    20. Aidin Delgoshaei & Timon Rabczuk & Ahad Ali & Mohd Khairol Anuar Ariffin, 2017. "An applicable method for modifying over-allocated multi-mode resource constraint schedules in the presence of preemptive resources," Annals of Operations Research, Springer, vol. 259(1), pages 85-117, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:jomega:v:53:y:2015:i:c:p:115-123. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/375/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.