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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. Nobuyuki Harada, 2007. "Video game demand in Japan: a household data analysis," Applied Economics, Taylor & Francis Journals, vol. 39(13), pages 1705-1710.
    12. 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.
    13. 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.
    14. 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.
    15. 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.
    16. 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.
    17. 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.
    18. 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.
    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. 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.
    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. 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.
    4. 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.
    5. 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.
    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. Wiebke Roß & Jens Weghake, 2018. "Wa(h)re Liebe: Was Online-Dating-Plattformen über zweiseitige Märkte lehren," TUC Working Papers in Economics 0017, Abteilung für Volkswirtschaftslehre, Technische Universität Clausthal (Department of Economics, Technical University Clausthal).
    8. 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.
    9. 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.
    10. Yifan Dou & D. J. Wu, 2021. "Platform Competition Under Network Effects: Piggybacking and Optimal Subsidization," Information Systems Research, INFORMS, vol. 32(3), pages 820-835, September.
    11. Karol Borowiecki & Juan Prieto-Rodriguez, 2015. "Video games playing: A substitute for cultural consumptions?," Journal of Cultural Economics, Springer;The Association for Cultural Economics International, vol. 39(3), pages 239-258, August.
    12. Cenamor, Javier, 2021. "Complementor competitive advantage: A framework for strategic decisions," Journal of Business Research, Elsevier, vol. 122(C), pages 335-343.
    13. Yinliang (Ricky) Tan & Janice E. Carrillo, 2017. "Strategic Analysis of the Agency Model for Digital Goods," Production and Operations Management, Production and Operations Management Society, vol. 26(4), pages 724-741, April.
    14. Jin Li & Gary Pisano & Yejia Xu & Feng Zhu, 2023. "Marketplace Scalability and Strategic Use of Platform Investment," Management Science, INFORMS, vol. 69(7), pages 3958-3975, July.
    15. 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.
    16. Joe Cox, 2008. "Purchasing power parity and cultural convergence: evidence from the global video games market," Journal of Cultural Economics, Springer;The Association for Cultural Economics International, vol. 32(3), pages 201-214, September.
    17. Bachtenkirch, David & Bock, Stefan, 2022. "Finding efficient make-to-order production and batch delivery schedules," European Journal of Operational Research, Elsevier, vol. 297(1), pages 133-152.
    18. Jens Foerderer & Thomas Kude & Sunil Mithas & Armin Heinzl, 2018. "Does Platform Owner’s Entry Crowd Out Innovation? Evidence from Google Photos," Information Systems Research, INFORMS, vol. 29(2), pages 444-460, June.
    19. Shabtay, Dvir, 2022. "Single-machine scheduling with machine unavailability periods and resource dependent processing times," European Journal of Operational Research, Elsevier, vol. 296(2), pages 423-439.
    20. Krzysztof Bartczak & Stanisław Łobejko, 2022. "The Implementation Environment for a Digital Technology Platform of Renewable Energy Sources," Energies, MDPI, vol. 15(16), pages 1-16, August.

    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.