标题: 蚂蚁族群演算法于电影拍摄排程之应用
An Application of Ant Colony Optimization in Film Production Scheduling
作者: 余姿蓉
Yu, Tz Rong
林妙聪
Lin, Bertrand M. T.
资讯管理研究所
关键字: 影片制作;滞留成本;蚂蚁演算法;Film production;Talent scheduling;Hold cost;ACO
公开日期: 2011
摘要: 在制作与拍摄影片过程中,预算的掌控为最重要的问题之一,本论文主要是探讨其中之拍摄排程问题。而在拍摄影片过程中,由于每个场景所需要的演员都不尽相同,因此拍摄的场景跟演员相互之间会有很大的关联,使得场景的拍摄循序会影响到演员的滞留天数以及总拍摄天数。
在本研究中,我们主要是在探讨透过所上述的条件之下,如何做到场景的安排以及演员的排班两方面的成本能减至最少。在演员排班问题中,我们试着要找出一个场景的拍摄顺序能够使得演员的滞留成本最小化,而这个问题已经被证明是一件很难的问题(NP-hard)。
论文是主要利用蚂蚁演算法(Ant Colony Optimization Algorithm, ACO)、将问题的模型推广至包含单日作业时间的限制,而这项条件会限制住每个拍摄天当中所有拍摄场景的总时数。在每个拍摄计画当中,所需要的成本包含了所有演员的滞留成本以及单日运作所需要的固定成本,而拍摄天数的最小化也可视为一个装箱问题,在使用启发式演算法之一将场景安排到不同的拍摄天内以求得问题初始解,并且再以此解去作后续的改善。
In film production, budgeting is one of the most important issues. In this study, we present the cost minimization issue in talent scheduling and scene scheduling. We determine the sequence of the scenes of shooting days so that the total hold cost of actors can be minimized. We also concern about the daily working capacity, which defines the total duration of scenes allocated in a single day. Our objective function is the total hold cost of all actors’ hold cost and the total operating cost of the active shootings days. This problem is already known to be strongly NP-hard and computationally challenging. In this thesis, we propose an algorithm based upon Ant Colony Optimization (ACO) to solve the scheduling problem. We examine the computational results of our ACO algorithm by using different parameter settings. The computational experiments reveal that the ACO algorithm is more effective and more efficient in obtaining near-optimal solutions.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT079934535
http://hdl.handle.net/11536/50160
显示于类别:Thesis