考量單日作業時間限制之影片拍攝排程

Abstract

在影片的製作與拍攝中，預算的掌控是最重要的問題之一。而拍攝影片時，由於每一個場景所需要的演員都不盡相同，因此要拍攝的場景跟演員相互之間會有所關聯，使得場景的拍攝順序會影響到演員的滯留天數以及總拍攝天數。在本論文中，我們將探討如何做到場景的安排以及演員的排班兩方面成本的最小化。在演員排班問題中，我們試著要找出一個場景的拍攝順序能夠使得演員的滯留成本最小化，而這個問題已經被證明是屬於strongly NP-hard。在本研究中，我們將問題的模型擴大到包含單日作業時間的限制，而這項條件會限制住每個拍攝天當中所有拍攝場景的總時數。在每個拍攝天中，所需要的成本包含了所有演員的滯留成本以及單日運作所需的固定成本，而拍攝天數的最小化也可視為一個裝箱問題，同樣地這也是屬於strongly NP-hard。在本文中，我們使用次適法及最先遞減配置法，將場景安排到不同的拍攝天內以求得問題的初始解，並且再以此去作後續的改善。而第二階段的改進步驟，則是使用了動態規劃、迭代區域搜尋法、禁忌搜尋法作為改善的演算法。對於上述所提出的各種解題方法，我們進行了一系列的電腦程式模擬實驗來驗證各個方法的效果、效率等表現。根據實驗結果顯示，我們所提出的迭代區域搜尋法跟禁忌搜尋法可以在短時間內求得良好的近似解。

Budgeting is one of the most critical issues in film production. This study addresses a cost minimization issue in scene arrangement and talent scheduling. In film production, there is a relation between the scenes to film and the actors involved. Talent scheduling seeks to determine a shooting sequence of the scenes such that the total hold cost of all actors is minimum. This problem is already known to be strongly NP-hard. This thesis generalizes the model by incorporating the constraints of daily working capacity, which confines the total duration of shooting scenes in every shooting day. The operating cost of shooting day is introduced. The cost structure of the studied problem is comprised of the total retention cost of the actors and the total operating cost of the active shooting days. To minimize the number of shooting days can be regarded as a bin packing problem. In this thesis, we use the next fit algorithm and the first fit decreasing algorithm to allocate scenes to working days so as to provide initial solutions for further improvements. Dynamic programming (DP), iterated local search (ILS) and tabu search (TS) are adopted to design the second-phase improvement procedures. We conduct a series of computational experiments to examine the performance, effectiveness and efficiency of the proposed solution approaches. The statics of computational experiments reveal that the proposed ILS and TS algorithms can produce quality approximate solutions in a very short time.