IDEAS home Printed from https://ideas.repec.org/a/spr/joinma/v29y2018i3d10.1007_s10845-015-1075-z.html
   My bibliography  Save this article

Mathematical programming models for scheduling in a CPU/FPGA architecture with heterogeneous communication delays

Author

Listed:
  • Abdessamad Ait El Cadi

    (UVHC - LAMIH CNRS UMR 8201
    IRT Railenium, Espace Technopôle, Le Mont Houy)

  • Omar Souissi

    (UVHC - LAMIH CNRS UMR 8201)

  • Rabie Ben Atitallah

    (UVHC - LAMIH CNRS UMR 8201)

  • Nicolas Belanger

    (Aéroport Marseille Provence)

  • Abdelhakim Artiba

    (UVHC - LAMIH CNRS UMR 8201)

Abstract

This paper deals with the mathematical modelling of a scheduling problem in a heterogeneous CPU/FPGA architecture with heterogeneous communication delays in order to minimize the makespan, $$C_{max}$$ C m a x . This study was motivated by the quality of the available solvers for Mixed Integer Program. The proposed model includes the communication delay constraints in a heterogeneous case, depending on both tasks and computing units. These constraints are linearized without adding any extra variables and the obtained linear model is reduced to speed-up the solving with CPLEX up to 60 times. Computational results show that the proposed model is promising. For an average sized problem of up to 50 tasks and five computing units the solving time under CPLEX is a few seconds.

Suggested Citation

  • Abdessamad Ait El Cadi & Omar Souissi & Rabie Ben Atitallah & Nicolas Belanger & Abdelhakim Artiba, 2018. "Mathematical programming models for scheduling in a CPU/FPGA architecture with heterogeneous communication delays," Journal of Intelligent Manufacturing, Springer, vol. 29(3), pages 629-640, March.
    • Handle: RePEc:spr:joinma:v:29:y:2018:i:3:d:10.1007_s10845-015-1075-z
    DOI: 10.1007/s10845-015-1075-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10845-015-1075-z
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10845-015-1075-z?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. S. Zhang & T. N. Wong, 2018. "Integrated process planning and scheduling: an enhanced ant colony optimization heuristic with parameter tuning," Journal of Intelligent Manufacturing, Springer, vol. 29(3), pages 585-601, March.
    2. Tatjana Davidović & Pierre Hansen & Nenad Mladenović, 2005. "Permutation-Based Genetic, Tabu, And Variable Neighborhood Search Heuristics For Multiprocessor Scheduling With Communication Delays," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 22(03), pages 297-326.
    3. SOUSA, Jorge P. & WOLSEY, Laurence A., 1992. "A time indexed formulation of non-preemptive single machine scheduling problems," LIDAM Reprints CORE 984, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    4. Timothy L. Urban, 1998. "Note. Optimal Balancing of U-Shaped Assembly Lines," Management Science, INFORMS, vol. 44(5), pages 738-741, May.
    Full references (including those not matched with items on IDEAS)

    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. de Lima, Vinícius L. & Alves, Cláudio & Clautiaux, François & Iori, Manuel & Valério de Carvalho, José M., 2022. "Arc flow formulations based on dynamic programming: Theoretical foundations and applications," European Journal of Operational Research, Elsevier, vol. 296(1), pages 3-21.
    2. Baptiste, Philippe & Sadykov, Ruslan, 2010. "Time-indexed formulations for scheduling chains on a single machine: An application to airborne radars," European Journal of Operational Research, Elsevier, vol. 203(2), pages 476-483, June.
    3. Kramer, Arthur & Dell’Amico, Mauro & Iori, Manuel, 2019. "Enhanced arc-flow formulations to minimize weighted completion time on identical parallel machines," European Journal of Operational Research, Elsevier, vol. 275(1), pages 67-79.
    4. Roberto Cordone & Pierre Hosteins & Giovanni Righini, 2018. "A Branch-and-Bound Algorithm for the Prize-Collecting Single-Machine Scheduling Problem with Deadlines and Total Tardiness Minimization," INFORMS Journal on Computing, INFORMS, vol. 30(1), pages 168-180, February.
    5. Sanjeev Swami & Jehoshua Eliashberg & Charles B. Weinberg, 1999. "SilverScreener: A Modeling Approach to Movie Screens Management," Marketing Science, INFORMS, vol. 18(3), pages 352-372.
    6. Kara, Yakup & Paksoy, Turan & Chang, Ching-Ter, 2009. "Binary fuzzy goal programming approach to single model straight and U-shaped assembly line balancing," European Journal of Operational Research, Elsevier, vol. 195(2), pages 335-347, June.
    7. Boysen, Nils & Fliedner, Malte, 2008. "A versatile algorithm for assembly line balancing," European Journal of Operational Research, Elsevier, vol. 184(1), pages 39-56, January.
    8. J.M. van den Akker & C.A.J. Hurkens & M.W.P. Savelsbergh, 2000. "Time-Indexed Formulations for Machine Scheduling Problems: Column Generation," INFORMS Journal on Computing, INFORMS, vol. 12(2), pages 111-124, May.
    9. Wenkang Zhang & Yufan Zheng & Rafiq Ahmad, 2023. "The integrated process planning and scheduling of flexible job-shop-type remanufacturing systems using improved artificial bee colony algorithm," Journal of Intelligent Manufacturing, Springer, vol. 34(7), pages 2963-2988, October.
    10. Laureano Escudero & Javier Salmeron, 2005. "On a Fix-and-Relax Framework for a Class of Project Scheduling Problems," Annals of Operations Research, Springer, vol. 140(1), pages 163-188, November.
    11. Kelly Cristina Poldi & Silvio Alexandre Araujo, 2016. "Mathematical models and a heuristic method for the multiperiod one-dimensional cutting stock problem," Annals of Operations Research, Springer, vol. 238(1), pages 497-520, March.
    12. Balasubramanian, Hari & Fowler, John & Keha, Ahmet & Pfund, Michele, 2009. "Scheduling interfering job sets on parallel machines," European Journal of Operational Research, Elsevier, vol. 199(1), pages 55-67, November.
    13. Zhu, Xuedong & Son, Junbo & Zhang, Xi & Wu, Jianguo, 2023. "Constraint programming and logic-based Benders decomposition for the integrated process planning and scheduling problem," Omega, Elsevier, vol. 117(C).
    14. Artur Alves Pessoa & Teobaldo Bulhões & Vitor Nesello & Anand Subramanian, 2022. "Exact Approaches for Single Machine Total Weighted Tardiness Batch Scheduling," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1512-1530, May.
    15. Kaouthar Deghdak & Vincent T’kindt & Jean-Louis Bouquard, 2016. "Scheduling evacuation operations," Journal of Scheduling, Springer, vol. 19(4), pages 467-478, August.
    16. Gokcen, Hadi & Ag[caron]pak, Kursad, 2006. "A goal programming approach to simple U-line balancing problem," European Journal of Operational Research, Elsevier, vol. 171(2), pages 577-585, June.
    17. Chatterjee A K & Mukherjee, Saral, 2006. "Unified Concept of Bottleneck," IIMA Working Papers WP2006-05-01, Indian Institute of Management Ahmedabad, Research and Publication Department.
    18. Soric, Kristina, 2000. "A cutting plane algorithm for a single machine scheduling problem," European Journal of Operational Research, Elsevier, vol. 127(2), pages 383-393, December.
    19. Averbakh, Igor & Pereira, Jordi, 2015. "Network construction problems with due dates," European Journal of Operational Research, Elsevier, vol. 244(3), pages 715-729.
    20. Suresh Chand & Ting Zeng, 2001. "A Comparison of U-Line and Straight-Line Performances Under Stochastic Task Times," Manufacturing & Service Operations Management, INFORMS, vol. 3(2), pages 138-150, January.

    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:spr:joinma:v:29:y:2018:i:3:d:10.1007_s10845-015-1075-z. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.