組合優化問題Talent Scheduling Problem（TSP）簡介

2020 年 3 月 9 日
筆記

今天為大家介紹的問題是Talent Scheduling Problem，因為沒有合適的中文翻譯，所以下面直接簡稱其為TSP (注意，這裡的TSP可不是旅行商問題哦)。

背景介紹
模型建立
演算法求解
參考文獻

背景介紹

不久之前，我們剛當一波老闆了解了選址-路徑問題（LRP），現在為了更好地摸清TSP的來龍去脈，這次假設我們是學過運籌優化的電影製片人。

一部電影由多個場景組成，每個場景都需要持續拍攝一段時間，且可能只要部分演員參與拍攝即可。

演員只有當他後期無拍攝任務才可離開劇組，而他的總片酬取決於其參與電影拍攝的總持續時間，即從他開始參與的第一場拍攝那天算起，到最後一個需要他出鏡的場景結束當天，在這期間即使有些場景不需要其參與，都得支付其每日的片酬。

想像一下我們籌拍的這部電影，如果單純按照最終上映的場景順序進行拍攝，某位客串的大咖需要很高的每日片酬，但他只出鏡第一場和最後一場，由於中間幾場戲的拍攝期間仍得支付他每日片酬，可就非常划不來了。

所以尋找場景的最佳拍攝順序將可以為團隊省下不少錢。舉個具體的例子。

圖(a)表示了一部電影的拍攝任務實例。s為12個拍攝場景，a為6個演員，X表示演員i在場景j有拍攝任務，·表示演員i未出現在場景j中，c為各個演員每天的工資（無論當天是否有拍攝任務），d為各個場景完成拍攝的持續時間。

圖(b)表示了按照最終上映的順序進行拍攝所產生的成本計算。–表示演員i在場景j無拍攝任務但因為後續有檔期而滯留在劇組。Cost表示每個場景產生的成本，包括了holding cost，即演員滯留所產生的等待成本。這種順序最終的總成本為604，包含了223的總等待成本。

而這個實例的最優解場景順序為5-2-7-1-6-8-4-9-3-11-10-12，產生的兩類成本分別為434和53（大家可以自己動手算一算）。可見，如果你學過TSP的優化，將節省演員開支，多餘的預算還可以投入到其他方面的製作，意義重大。

雖然Cheng等(1993)【1】便提出這個問題，但假設每個場景的持續時間均為1天，且每個演員拿著一樣的片酬。直到de la Banda等(2011)【2】拓展模型使其一般化，並用動態規劃得到了小規模實例的精確解。之後對TSP的研究都是基於【2】的問題背景，其中Qin, Zhang, Lim,and Liang (2016)【3】首次將問題定義為混合整數線性規劃模型，下面介紹完整的模型建立。

模型建立

對n個場景、m個演員的TSP進行如下符號定義：