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