分支定界算法求解帶有釋放時間的單機雙調度問題

摘要：本文研究了帶有釋放時間的單機雙調度問題,目標函數為極小化最大完工時間和。為了便于利用優化軟件求解,建立了混合整數規劃模型。考慮到該問題具有NP困難性,因此采用近似與精確算法分別求解不同規模問題。針對大規模問題,提出了優勢優先啟發式算法,并證明了其漸近最優性。針對小規模問題,設計了分支定界法進行最優求解,其中基于釋放時間的分支規則和基于加工中斷的下界有效地減少了運算時間。最后,通過數值測試驗證了分支定界算法的有效性以及啟發式算法的收斂性。