IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v10y2022i7p1200-d788300.html
   My bibliography  Save this article

A Branch-and-Bound Algorithm for Minimizing the Total Tardiness of Multiple Developers

Author

Listed:
  • Chung-Ho Su

    (Department of Animation and Game Design, Shu-Te University, Kaohsiung 824, Taiwan)

  • Jen-Ya Wang

    (Department of Multimedia Game Development and Application, Hungkuang University, Taichung 433, Taiwan)

Abstract

In the game industry, tardiness is an important issue. Unlike a unifunctional machine, a developer may excel in programming but be mediocre in scene modeling. His/her processing speed varies with job type. To minimize tardiness, we need to schedule these developers carefully. Clearly, traditional scheduling algorithms for unifunctional machines are not suitable for such versatile developers. On the other hand, in an unrelated machine scheduling problem, n jobs can be processed by m machines at n × m different speeds, i.e., its solution space is too wide to be simplified. Therefore, a tardiness minimization problem considering three job types and versatile developers is presented. In this study, a branch-and-bound algorithm and a lower bound based on harmonic mean are proposed for minimizing the total tardiness. Theoretical analyses ensure the correctness of the proposed method. Computational experiments also show that the proposed method can ensure the optimality and efficiency for n ≤ 18. With the exact algorithm, we can fairly evaluate other approximate algorithms in the future.

Suggested Citation

  • Chung-Ho Su & Jen-Ya Wang, 2022. "A Branch-and-Bound Algorithm for Minimizing the Total Tardiness of Multiple Developers," Mathematics, MDPI, vol. 10(7), pages 1-24, April.
    • Handle: RePEc:gam:jmathe:v:10:y:2022:i:7:p:1200-:d:788300
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/10/7/1200/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/10/7/1200/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Fuh-Der Chou, 2013. "Minimising the total weighted tardiness for non-identical parallel batch processing machines with job release times and non-identical job sizes," European Journal of Industrial Engineering, Inderscience Enterprises Ltd, vol. 7(5), pages 529-557.
    2. Ghirardi, M. & Potts, C. N., 2005. "Makespan minimization for scheduling unrelated parallel machines: A recovering beam search approach," European Journal of Operational Research, Elsevier, vol. 165(2), pages 457-467, September.
    3. Onur Ozturk & Mehmet A. Begen & Gregory S. Zaric, 2017. "A branch and bound algorithm for scheduling unit size jobs on parallel batching machines to minimize makespan," International Journal of Production Research, Taylor & Francis Journals, vol. 55(6), pages 1815-1831, March.
    4. Rabia Nessah & Imed Kacem, 2009. "Branch-and-bound method for minimizing the weighted completion time scheduling problem on a single machine with release dates," Working Papers 2010-ECO-08, IESEG School of Management.
    5. S-O Shim & Y-D Kim, 2007. "Minimizing total tardiness in an unrelated parallel-machine scheduling problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(3), pages 346-354, March.
    6. Mensendiek, Arne & Gupta, Jatinder N.D. & Herrmann, Jan, 2015. "Scheduling identical parallel machines with fixed delivery dates to minimize total tardiness," European Journal of Operational Research, Elsevier, vol. 243(2), pages 514-522.
    7. R. Nessah & Farouk Yalaoui & C. Chu, 2008. "A branch and bound algorithm to minimize total weighted completion time on identical parallel machines with job release date," Post-Print hal-00580602, HAL.
    8. Kacem, Imed & Chu, Chengbin, 2008. "Efficient branch-and-bound algorithm for minimizing the weighted sum of completion times on a single machine with one availability constraint," International Journal of Production Economics, Elsevier, vol. 112(1), pages 138-150, March.
    9. Tanaka, Shunji & Araki, Mituhiko, 2008. "A branch-and-bound algorithm with Lagrangian relaxation to minimize total tardiness on identical parallel machines," International Journal of Production Economics, Elsevier, vol. 113(1), pages 446-458, May.
    10. Cheng-Hsiung Lee, 2018. "A dispatching rule and a random iterated greedy metaheuristic for identical parallel machine scheduling to minimize total tardiness," International Journal of Production Research, Taylor & Francis Journals, vol. 56(6), pages 2292-2308, March.
    11. Edward G. Anderson & Geoffrey G. Parker & Burcu Tan, 2014. "Platform Performance Investment in the Presence of Network Externalities," Information Systems Research, INFORMS, vol. 25(1), pages 152-172, March.
    12. Wen-Chiung Lee & Jen-Ya Wang & Lin-Yo Lee, 2015. "A hybrid genetic algorithm for an identical parallel-machine problem with maintenance activity," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 66(11), pages 1906-1918, November.
    13. Luis Henrique Magalhães Costa & Bruno Prata & Helena M. Ramos & Marco Aurélio Holanda Castro, 2016. "A Branch-and-Bound Algorithm for Optimal Pump Scheduling in Water Distribution Networks," Water Resources Management: An International Journal, Published for the European Water Resources Association (EWRA), Springer;European Water Resources Association (EWRA), vol. 30(3), pages 1037-1052, February.
    14. Jen-Ya Wang, 2020. "Minimizing the total weighted tardiness of overlapping jobs on parallel machines with a learning effect," Journal of the Operational Research Society, Taylor & Francis Journals, vol. 71(6), pages 910-927, June.
    15. Chengbin Chu, 1992. "A branch‐and‐bound algorithm to minimize total tardiness with different release dates," Naval Research Logistics (NRL), John Wiley & Sons, vol. 39(2), pages 265-283, March.
    16. Nobuyuki Harada, 2007. "Video game demand in Japan: a household data analysis," Applied Economics, Taylor & Francis Journals, vol. 39(13), pages 1705-1710.
    17. Ju-Yong Lee & Yeong-Dae Kim, 2015. "A branch and bound algorithm to minimize total tardiness of jobs in a two identical-parallel-machine scheduling problem with a machine availability constraint," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 66(9), pages 1542-1554, September.
    18. Gretz, Richard T., 2010. "Hardware quality vs. network size in the home video game industry," Journal of Economic Behavior & Organization, Elsevier, vol. 76(2), pages 168-183, November.
    19. Asmaa Khoudi & Ali Berrichi, 2020. "Minimize total tardiness and machine unavailability on single machine scheduling problem: bi-objective branch and bound algorithm," Operational Research, Springer, vol. 20(3), pages 1763-1789, September.
    20. Zhi Pei & Mingzhong Wan & Ziteng Wang, 2020. "A new approximation algorithm for unrelated parallel machine scheduling with release dates," Annals of Operations Research, Springer, vol. 285(1), pages 397-425, February.
    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. Arthur Kramer & Anand Subramanian, 2019. "A unified heuristic and an annotated bibliography for a large class of earliness–tardiness scheduling problems," Journal of Scheduling, Springer, vol. 22(1), pages 21-57, February.
    2. Berghman, Lotte & Leus, Roel, 2015. "Practical solutions for a dock assignment problem with trailer transportation," European Journal of Operational Research, Elsevier, vol. 246(3), pages 787-799.
    3. Teobaldo Bulhões & Ruslan Sadykov & Anand Subramanian & Eduardo Uchoa, 2020. "On the exact solution of a large class of parallel machine scheduling problems," Journal of Scheduling, Springer, vol. 23(4), pages 411-429, August.
    4. Herr, Oliver & Goel, Asvin, 2016. "Minimising total tardiness for a single machine scheduling problem with family setups and resource constraints," European Journal of Operational Research, Elsevier, vol. 248(1), pages 123-135.
    5. Xing Wan & Javier Cenamor & Geoffrey Parker & Marshall Van Alstyne, 2017. "Unraveling Platform Strategies: A Review from an Organizational Ambidexterity Perspective," Sustainability, MDPI, vol. 9(5), pages 1-18, May.
    6. Kerem Bülbül & Halil Şen, 2017. "An exact extended formulation for the unrelated parallel machine total weighted completion time problem," Journal of Scheduling, Springer, vol. 20(4), pages 373-389, August.
    7. Biber Nurit & Mor Baruch & Schlissel Yitzhak & Shapira Dana, 2023. "Lot scheduling involving completion time problems on identical parallel machines," Operational Research, Springer, vol. 23(1), pages 1-29, March.
    8. Omid Shahvari & Rasaratnam Logendran & Madjid Tavana, 2022. "An efficient model-based branch-and-price algorithm for unrelated-parallel machine batching and scheduling problems," Journal of Scheduling, Springer, vol. 25(5), pages 589-621, October.
    9. Nascimento, Paulo Jorge & Silva, Cristóvão & Antunes, Carlos Henggeler & Moniz, Samuel, 2024. "Optimal decomposition approach for solving large nesting and scheduling problems of additive manufacturing systems," European Journal of Operational Research, Elsevier, vol. 317(1), pages 92-110.
    10. Fowler, John W. & Mönch, Lars, 2022. "A survey of scheduling with parallel batch (p-batch) processing," European Journal of Operational Research, Elsevier, vol. 298(1), pages 1-24.
    11. Chen, Jiang Hang & Lee, Der-Horng & Cao, Jin Xin, 2011. "Heuristics for quay crane scheduling at indented berth," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 47(6), pages 1005-1020.
    12. Wu, Lingxiao & Wang, Shuaian, 2018. "Exact and heuristic methods to solve the parallel machine scheduling problem with multi-processor tasks," International Journal of Production Economics, Elsevier, vol. 201(C), pages 26-40.
    13. 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.
    14. Li, Feng & Xu, Shifu & Xu, Zhou, 2023. "New exact and approximation algorithms for integrated production and transportation scheduling with committed delivery due dates and order acceptance," European Journal of Operational Research, Elsevier, vol. 306(1), pages 127-140.
    15. Christos Koulamas, 1997. "Decomposition and hybrid simulated annealing heuristics for the parallel‐machine total tardiness problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 44(1), pages 109-125, February.
    16. Jens Foerderer & Nele Lueker & Armin Heinzl, 2021. "And the Winner Is …? The Desirable and Undesirable Effects of Platform Awards," Information Systems Research, INFORMS, vol. 32(4), pages 1155-1172, December.
    17. Wu, Cheng-Han & Chiu, Yun-Yao, 2023. "Pricing and content development for online media platforms regarding consumer homing choices," European Journal of Operational Research, Elsevier, vol. 305(1), pages 312-328.
    18. Gur Mosheiov & Daniel Oron, 2023. "A note on batch scheduling on a two-machine flowshop with machine-dependent processing times," 4OR, Springer, vol. 21(3), pages 457-469, September.
    19. Zhi Pei & Mingzhong Wan & Ziteng Wang, 2020. "A new approximation algorithm for unrelated parallel machine scheduling with release dates," Annals of Operations Research, Springer, vol. 285(1), pages 397-425, February.
    20. K. H. Adjallah & K. P. Adzakpa, 2007. "Minimizing maintenance cost involving flow-time and tardiness penalty with unequal release dates," Journal of Risk and Reliability, , vol. 221(1), pages 57-65, March.

    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:gam:jmathe:v:10:y:2022:i:7:p:1200-:d:788300. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.