申論題

四、某公司欲以單一機臺處理 N 批貨件。所有貨件各不相同，編號 1 至 N。 該機臺在同一時間僅能處理一批貨件。第 i 批貨件在機臺上所需要之處 理時間長度已知為 Ti。機臺可依任何順序處理，但在完成貨件 i 之後， 若下一批貨為第 j 貨件時，其間的機臺清理時間已知為 ，在進行清理 時，機臺無法處理任何貨件。在開始工作之前，以及完成所有工作之後， 均無額外機臺清理時間。今欲將此問題模化成為旅行推銷員問題 （travelling salesman problem） ，以求取能夠極小化完成處理所有貨件總時 間之工作順序。