Issue |
RAIRO-Oper. Res.
Volume 56, Number 6, November-December 2022
|
|
---|---|---|
Page(s) | 3895 - 3913 | |
DOI | https://doi.org/10.1051/ro/2022191 | |
Published online | 18 November 2022 |
A makespan minimization problem for versatile developers in the game industry
1
Department of Animation and Game Design, Shu-Te University, Kaohsiung City, Taiwan, R.O.C.
2
Department of Multimedia Game Development and Application, Hungkuang University, Taichung City, Taiwan, R.O.C.
* Corresponding author: jywang@sunrise.hk.edu.tw
Received:
12
January
2022
Accepted:
25
October
2022
Today, the development of a modern video game draws upon multiple areas of expertise. Moreover, its development cost could be as high as tens of millions of dollars. Consequently, we should carefully schedule its jobs so as not to increase the total cost. However, project leaders traditionally treat developers alike or even schedule all the jobs manually. In this study, we consider a versatile-developer scheduling problem. The objective is to minimize the makespan of a game project. We propose a branch-and-bound algorithm (B&B) to generate the optimal schedules for small problem instances. On the other hand, an imperialist competitive algorithm (ICA) is proposed to obtain approximate schedules for large problem instances. Lastly, computational experiments are conducted to show the performances of both algorithms. When the problem size is small (e.g., n ≤ 12), B&B can generate the optimal schedules within 5 s. For some large problem instances (e.g., n = 600), near-optimal schedules can be obtained by ICA within 10 min. The final results imply that both algorithms converge quickly and are of high solution quality.
Mathematics Subject Classification: 90C05 / 90-08
Key words: Job scheduling / game development / makespan / branch-and-bound algorithm / imperialist competitive algorithm
© The authors. Published by EDP Sciences, ROADEF, SMAI 2022
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.