Abstract
One of the main tasks in dubbing studios is to design good schedules to assign actors/actresses to dubbing sessions. This paper provides an effective tool based on the simulated annealing philosophy. The performance of the proposed heuristic is guaranteed by a binary linear programming model (BP model). By relaxing some integrality conditions in the BP model, we can achieve optimal schedules in real instances gathered from several dubbed films. Yet, in most cases, it is not possible to obtain these optimal schedules in a suitable computational time. On the contrary, the heuristic algorithm gets high quality solutions (and even the optimal ones) in just few seconds.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
Note that the maximum number of takes divisions is the maximum number of work sessions into which a take can be divided.
Although this assumption works with our data set, we could obtain non-integer solutions with other data.
Note that the best value of the objective is obtained when the minimum number of paid sessions is reached.
References
Aarts EHL, Korst JHM, van Laarhoven PJM (1997) Simulated annealing. In: Aarts E, Lenstra JK (eds) Local search in combinatorial optimization. Wiley, New York, pp 91–120
Álmos A (1998) Scheduling algorithms for a video-dubbing studio. In: INTCOM’98, Miskolc
Anagnostopoulos A, Michel L, van Hentenryck P (2006) A simulated annealing approach to the traveling tournament problem. J Sched 9:177–193
Bouleimen K, Lecocq H (2003) A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version. Eur J Oper Res 149:268–281
Eglese RW (1990) Simulated annealing: a tool for operational research. Eur J Oper Res 46:271–281
Gunawan A, Ng KM, Poh KL (2012) A hybridized Lagrangian relaxation and simulated annealing method for the course timetabling problem. Comput Oper Res 39:3074–3088
Kendall G, Knust S, Ribeiro CC, Urrutia S (2010) Scheduling in sports: an annotated bibliography. Comput Oper Res 37:1–19
Kim KH, Moon KC (2003) Berth scheduling by simulated annealing. Transp Res Part B 37:541–560
Kirkpatrick S, Gelatt CD, Vecchi MP (1983) Optimization by simulated annealing. Science 220:671–680
Parr D, Thompson JM (2007) Solving the multi-objective nurse scheduling problem with a weighted cost function. Ann Oper Res 155:279–288
Thompson JM, Dowsland KA (1998) A robust simulated annealing based examination timetabling system. Comput Oper Res 25:637–648
van Laarhoven PJM, Aarts EHL, Lenstra JK (1992) Job shop scheduling by simulated annealing. Oper Res 40:113–125
Willis RJ, Terrill BJ (1994) Scheduling the Australian state cricket season using simulated annealing. J Oper Res Soc 45:276–280
Acknowledgments
We are very grateful for the constructive suggestions made by one anonymous referee, which helped us to improve an earlier version of this paper. Financial support from Ministerio de Ciencia y Tecnología, FEDER, and Ministerio de Ciencia e Innovación through Grants ECO2011-23460, MTM2011-27731-C03-02, TIN2009-14560-C03-02, and TIN2013-46238-C4-3-R; and from Xunta de Galicia through Grant GRC2013/053 is also gratefully acknowledged.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Brisaboa, N.R., Carpente, L., Cerdeira-Pena, A. et al. Optimization in dubbing scheduling. TOP 23, 685–702 (2015). https://doi.org/10.1007/s11750-015-0361-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-015-0361-4