高考申論題
110年
[工業工程] 作業研究
第 一 題
📖 題組：
某公司欲以單一機臺處理 N 批貨件。所有貨件各不相同，編號 1 至 N。該機臺在同一時間僅能處理一批貨件。第 i 批貨件在機臺上所需要之處理時間長度已知為 Ti。機臺可依任何順序處理，但在完成貨件 i 之後，若下一批貨為第 j 貨件時，其間的機臺清理時間已知為 Rij，在進行清理時，機臺無法處理任何貨件。在開始工作之前，以及完成所有工作之後，均無額外機臺清理時間。今欲將此問題模化成為旅行推銷員問題（travelling salesman problem），以求取能夠極小化完成處理所有貨件總時間之工作順序。
某公司欲以單一機臺處理 N 批貨件。所有貨件各不相同，編號 1 至 N。該機臺在同一時間僅能處理一批貨件。第 i 批貨件在機臺上所需要之處理時間長度已知為 Ti。機臺可依任何順序處理，但在完成貨件 i 之後，若下一批貨為第 j 貨件時，其間的機臺清理時間已知為 Rij，在進行清理時，機臺無法處理任何貨件。在開始工作之前，以及完成所有工作之後，均無額外機臺清理時間。今欲將此問題模化成為旅行推銷員問題（travelling salesman problem），以求取能夠極小化完成處理所有貨件總時間之工作順序。
📝 此題為申論題，共 2 小題
小題 (一)
試寫出旅行推銷員問題之定義。（文字敘述即可，不必寫出數學式）（5 分）
思路引導 VIP
TSP 是 OR 的經典問題。定義中必須包含：1. 訪遍所有給定城市。2. 每個城市恰好經過一次。3. 回到出發點。4. 總旅行距離（或成本）最小。
小題 (二)
說明將這個機臺處理貨件問題模化成為旅行推銷員問題之方法。至少需要說明如何定義旅行推銷員問題中之⑴節點、⑵節線長度，並說明求解完成後，如何將旅行推銷員問題之最佳解轉化成為原機臺處理貨件問題之最佳解。（20 分）
思路引導 VIP
這題要求將排程問題（Scheduling）轉化為 TSP。關鍵在於：1. 節點要包含所有貨件。2. 由於原題沒有「回原點」的清理時間，需要增加一個「虛擬節點」（Dummy Node）來代表起始與結束狀態。3. 節線長度要能反映總時間（處理時間 + 清理時間）。