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

Chung-Ho Su and Jen-Ya Wang
Additional contact information
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

Mathematics, 2022, vol. 10, issue 7, 1-24

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.

Keywords: harmonic mean; optimization; total tardiness; branch-and-bound algorithm; lower bound (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/7/1200/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/7/1200/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:7:p:1200-:d:788300

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().