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.
Keywords: Job scheduling, game development, makespan, branch-and-bound algorithm, imperialist competitive algorithm
@article{RO_2022__56_6_3895_0,
author = {Su, Chung-Ho and Wang, Jen-Ya},
title = {A makespan minimization problem for versatile developers in the game industry},
journal = {RAIRO. Operations Research},
pages = {3895--3913},
year = {2022},
publisher = {EDP-Sciences},
volume = {56},
number = {6},
doi = {10.1051/ro/2022191},
mrnumber = {4511223},
zbl = {1539.90037},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2022191/}
}
TY - JOUR AU - Su, Chung-Ho AU - Wang, Jen-Ya TI - A makespan minimization problem for versatile developers in the game industry JO - RAIRO. Operations Research PY - 2022 SP - 3895 EP - 3913 VL - 56 IS - 6 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2022191/ DO - 10.1051/ro/2022191 LA - en ID - RO_2022__56_6_3895_0 ER -
%0 Journal Article %A Su, Chung-Ho %A Wang, Jen-Ya %T A makespan minimization problem for versatile developers in the game industry %J RAIRO. Operations Research %D 2022 %P 3895-3913 %V 56 %N 6 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2022191/ %R 10.1051/ro/2022191 %G en %F RO_2022__56_6_3895_0
Su, Chung-Ho; Wang, Jen-Ya. A makespan minimization problem for versatile developers in the game industry. RAIRO. Operations Research, Tome 56 (2022) no. 6, pp. 3895-3913. doi: 10.1051/ro/2022191
[1] , and , A new efficient biased random key genetic algorithm for open shop scheduling with routing by capacitated single vehicle and makespan minimization. Eng. Appl. Artif. Intell. 104 (2021) 104373. | DOI
[2] and , Two parallel machine sequencing problems involving controllable job processing times. Eur. J. Oper. Res. 70 (1993) 335–341. | Zbl | DOI
[3] , GTA IV: most expensive game ever developed? Games Ind. Int. 30 (2008).
[4] , and , A two-stage Ant Colony optimization algorithm to minimize the makespan on unrelated parallel machines-part II: enhancements and experimentations. J. Intell. Manuf. 25 (2014) 43–53. | DOI
[5] and , A new branch-and-bound algorithm for the unrelated parallel machine scheduling problem with sequence-dependent setup times, in Proceedings of the 13th IFAC Symposium on Information Control Problems in Manufacturing. Vol. 42. Moscow, Russia (2009) 792–797.
[6] and , Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Comput. Surv. 35 (2003) 268–308. | DOI
[7] , IN BRIEF: Tencent’s Supercell hit with $92 million mobile-game patent verdict. Available: https://www.reuters.com/business/legal/brief-tencents-supercell-hit-with-92-million-mobile-game-patent-verdict-2021-05-10/ (2021).
[8] , and , A novel approach for product makespan prediction in production life cycle. Int. J. Adv. Manuf. Technol. 80 (2015) 1433–1448. | DOI
[9] , , and , Introduction to Algorithms, 3rd edition. MIT Press (2009). | MR | Zbl
[10] , and , Minimizing the total completion time on a parallel machine system with tool changes. Comput. Ind. Eng. 91 (2016) 290–301. | DOI
[11] , , and , An optimization approach for green tourist trip design. Soft Comput. 26 (2022) 4303–4332. | DOI
[12] and , Stochastic weekly operating room planning with an exponential number of scenarios. Ann. Oper. Res. (2022). DOI: . | DOI | MR | Zbl
[13] , , and , Minimizing total energy cost and tardiness penalty for a scheduling-layout problem in a flexible job shop system: a comparison of four metaheuristic algorithms. Comput. Ind. Eng. 141 (2020) 106295. | DOI
[14] , Video Game Borrows Page from Hollywood Playbook. Los Angeles Times (2009).
[15] and , Star Wars: The Old Republic – The Story Behind a Galactic Gamble. Los Angeles Times (2012).
[16] , , and , A green multi-objective integrated scheduling of production and distribution with heterogeneous fleet vehicle routing and time windows. J. Cleaner Prod. 259 (2020) 120824. | DOI
[17] , and , A branch-and-price approach to the multitasking scheduling with batch control on parallel machines. Int. Trans. Oper. Res. 2022 (2022) 1–22. | MR | Zbl
[18] and , Makespan minimization for scheduling unrelated parallel machines: a recovering beam search approach. Eur. J. Oper. Res. 165 (2005) 457–467. | Zbl | DOI
[19] and , Alleles, loci and the traveling salesman problem, in Proceedings of an International Conference on Genetic Algorithms and Their Application. Hillsdale, New Jersey, USA (1985) 154–159. | Zbl
[20] , and , Scheduling to minimize the makespan in large-piece one-of-a-kind production with machine availability constraints. Expert Syst. App. 42 (2015) 9174–9182. | DOI
[21] and , Fixed set search application for minimizing the makespan on unrelated parallel machines with sequence-dependent setup times. Appl. Soft Comput. 110 (2021) 107521. | DOI
[22] and , Efficient branch-and-bound algorithm for minimizing the weighted sum of completion times on a single machine with one availability constraint. Int. J. Prod. Econ. 112 (2008) 138–150. | DOI
[23] , , and , Minimizing total tardiness and earliness on unrelated parallel machines with controllable processing times. Comput. Oper. Res. 41 (2014) 31–43. | MR | Zbl | DOI
[24] , Using reinforcement learning to forecast the spread of COVID-19 in France, in 2021 IEEE International Conference on Autonomous Systems (ICAS), Montreal, Canada (2021). | DOI
[25] and , Robust modelling and prediction of the COVID-19 pandemic in Canada. Int. J. Prod. Res. 2021 (2021) 1–17.
[26] , , and , Gradient-based grey wolf optimizer with Gaussian walk: application in modelling and prediction of the COVID-19 pandemic. Expert Syst. App. 177 (2021) 114920. | DOI
[27] and , Minimize total tardiness and machine unavailability on single machine scheduling problem: bi-objective branch and bound algorithm. Oper. Res. 20 (2020) 1763–1789.
[28] , , , and , Machining sensor data management for operation-level predictive model. Expert Syst. App. 159 (2020) 1–10.
[29] , and , Modelling activity times by hybrid synthetic method. Prod. Planning Control 27 (2016) 909–924. | DOI
[30] and , A branch and bound algorithm to minimize total tardiness of jobs in a two identical-parallel-machine scheduling problem with a machine availability constraint. J. Oper. Res. Soc. 66 (2015) 1542–1554. | DOI
[31] and , A three-agent scheduling problem for minimizing the flow time on two machines. RAIRO: Oper. Res. 54 (2020) 307–323. | MR | Zbl | Numdam | DOI
[32] , and , A hybrid genetic algorithm for an identical parallel-machine problem with maintenance activity. J. Oper. Res. Soc. 66 (2015) 1906–1918. | DOI
[33] , and , A branch-and-bound algorithm for minimizing the total weighted completion time on parallel identical machines with two competing agents. Knowl.-Based Syst. 105 (2016) 68–82. | DOI
[34] , , , and , An unsupervised user behavior prediction algorithm based on machine learning and neural network for smart home. IEEE Access 6 (2018) 49237–49247. | DOI
[35] and , Unrelated parallel machine scheduling with setup times and ready times. Int. J. Prod. Res. 52 (2014) 1200–1214. | DOI
[36] and , Runtime estimation and scheduling on parallel processing supercomputers via instance-based learning and swarm intelligence. Int. J. Mach. Learn. Comput. 9 (2019) 592–598. | DOI
[37] and , ABC-based manufacturing scheduling for unrelated parallel machines with machine-dependent and job sequence-dependent setup times. Comput. Oper. Res. 51 (2014) 172–181. | MR | Zbl | DOI
[38] , A nature inspired intelligent water drops evolutionary algorithm for parallel processor scheduling with rejection. Appl. Soft Comput. 26 (2015) 166–179. | DOI
[39] , and , Minimizing maximum tardiness on a single machine with family setup times and machine disruption. Comput. Oper. Res. 129 (2021) 105231. | MR | Zbl | DOI
[40] and , Game Development Essentials: Game Industry Career Guide. Cengage Learning (2010).
[41] , , and , Exact and metaheuristic approaches for unrelated parallel machine scheduling. J. Scheduling 25 (2021) 507–534. | MR | DOI
[42] , Exact and hybrid metaheuristic algorithms to solve bi-objective permutation flow shop scheduling problem, in Iraqi Academics Syndicate International Conference for Pure and Applied Sciences. Vol. 1818. Babylon, Iraq (2022) 1–10.
[43] , and , A fuzzy robust planning model in the disaster management response phase under precedence constraints. Operational Research 22 (2022) 3571–3605. | DOI
[44] and , Branch-and-bound method for minimizing the weighted completion time scheduling problem on a single machine with release dates. Comput. Oper. Res. 39 (2012) 471–478. | MR | Zbl | DOI
[45] , and , A branch-and-bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates. Comput. Oper. Res. 35 (2008) 1176–1190. | MR | Zbl | DOI
[46] , and , A branch and bound algorithm for scheduling unit size jobs on parallel batching machines to minimize makespan. Int. J. Prod. Res. 55 (2017) 1815–1831. | DOI
[47] , and , A multi-start tabu search method for a single-machine scheduling problem with periodic maintenance and sequence-dependent set-up times. J. Scheduling 16 (2013) 661–673. | MR | DOI
[48] , and , A new approximation algorithm for unrelated parallel machine scheduling with release dates. Ann. Oper. Res. 285 (2020) 397–425. | MR | Zbl | DOI
[49] , Scheduling: Theory, Algorithms, and Systems. Springer, New York (2010). | MR
[50] , , and , An iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problem. Comput. Oper. Res. 40 (2013) 1829–1841. | MR | Zbl | DOI
[51] , The single processor total weighted completion time scheduling problem with the sum-of-processing-time based learning model. Inf. Sci. 199 (2012) 216–229. | MR | Zbl | DOI
[52] , A fast neighborhood search scheme for identical parallel machine scheduling problems under general learning curves. Appl. Soft Comput. 113 (2021) 108023. | DOI
[53] , Minimizing total tardiness for scheduling identical parallel machines with family setups. Comput. Ind. Eng. 72 (2014) 274–281. | DOI
[54] , and , Performance-effective DAG scheduling for heterogeneous distributed systems, in ICDCN 2022: 23rd International Conference on Distributed Computing and Networking. Delhi, India (2022) 234–235.
[55] , and , Exact and metaheuristic approaches for identical parallel machine scheduling with a common server and sequence-dependent setup times. J. Oper. Res. Soc. 72 (2021) 444–457. | DOI
[56] , , , and , Metaheuristics for scheduling of heterogeneous tasks in cloud computing environments: analysis, performance evaluation, and future directions. Simul. Modell. Pract. Theory 111 (2021) 102353. | DOI
[57] , , , and , Scheduling of unrelated parallel machines considering sequence-related setup time, start time-dependent deterioration, position-dependent learning and power consumption minimization. J. Cleaner Prod. 249 (2020) 119428. | DOI
[58] and , A branch-and-bound algorithm for minimizing the total tardiness of multiple developers. Mathematics 10 (2022) 10071200.
[59] , and , An Iterated Local Search heuristic for the single machine total weighted tardiness scheduling problem with sequence-dependent setup times. Int. J. Prod. Res. 52 (2014) 2729–2742. | DOI
[60] and , Minimizing makespan on a single burn-in oven in semiconductor manufacturing. Eur. J. Oper. Res. 120 (2000) 559–574. | Zbl | DOI
[61] and , A branch-and-bound algorithm with Lagrangian relaxation to minimize total tardiness on identical parallel machines. Int. J. Prod. Econ. 113 (2008) 446–458. | DOI
[62] , A branch and bound algorithm for minimizing makespan on a single machine with unequal release times under learning effect and deteriorating jobs. Comput. Oper. Res. 38 (2011) 1361–1365. | MR | Zbl | DOI
[63] , Algorithms for minimizing resource consumption over multiple machines with a common due window. IEEE Access 7 (2019) 172136–172151. | DOI
[64] , A branch-and-bound algorithm for minimizing the total tardiness of a three-agent scheduling problem considering the overlap effect and environment protection. IEEE Access 7 (2019) 5106–5123. | DOI
[65] , Minimizing the total weighted tardiness of overlapping jobs on parallel machines with a learning effect. J. Oper. Res. Soc. 71 (2020) 910–927. | DOI
[66] and , A branch and bound algorithm for single-machine production scheduling integrated with preventive maintenance planning. Int. J. Prod. Res. 51 (2013) 847–868. | DOI
[67] , and , Minimizing the total tardiness of a game project considering the overlap effect. IEEE Access 8 (2020) 216507–216518. | DOI
[68] , , , , and , Minimizing the sum of makespan on multi-agent single-machine scheduling with release dates. Swarm Evol. Comput. 69 (2022) 100996. | DOI
[69] , and , A branch and bound algorithm for minimizing total completion time on a single batch machine with incompatible job families and dynamic arrivals. Comput. Oper. Res. 39 (2012) 939–951. | MR | Zbl | DOI
[70] , , and , A branch-and-bound algorithm for a single machine sequencing to minimize the total tardiness with arbitrary release dates and position-dependent learning effects. Inf. Sci. 256 (2014) 91–108. | MR | Zbl | DOI
[71] and , A biogeography-based optimization algorithm for order acceptance and scheduling. J. Ind. Prod. Eng. 34 (2017) 312–321.
[72] , , , and , A combinatorial evolutionary algorithm for unrelated parallel machine scheduling problem with sequence and machine-dependent setup times, limited worker resources and learning effect. Expert Syst. App. 175 (2021) 114843. | DOI
Cité par Sources :
