考慮作業釋放時間和機器數量變化的同型機調度問題

趙福強, 劉桂慶

(合肥工業大學 數學學院,安徽 合肥 230009)

考慮作業釋放時間和機器數量變化的同型機調度問題

趙福強, 劉桂慶

(合肥工業大學 數學學院,安徽 合肥 230009)

同型機調度;機器影響;釋放時間;可中斷;最大完工時間

0 引 言

生產調度問題是一類典型的組合優化問題,它旨在利用現有資源,在滿足一些必要條件基礎上完成一定任務并達到特定的調度目標。在現代生產制造中,企業投入生產的機器數量是制造加工系統的一個重要特征,因此研究機器數量投入對企業生產效率的影響具有重要意義。當企業接收一批訂單后,雖然有足夠的機器資源去加工這些訂單,但如果投入很多機器處理這些訂單,很可能造成資源浪費。另外,機器數量變化調度問題不同于傳統調度問題。因此,該項研究內容具有重要的理論價值和現實意義。

關于作業帶有釋放時間且允許中斷的2臺同型機的最小化完工時間和問題,文獻[6]提出了一個啟發式算法,并證明了某些特殊的實例,該算法能夠得到最優調度,指出了當有n個作業時該算法的最壞情況誤差界為2(1-1/n)。關于作業帶有釋放時間且允許中斷m個同型機的最小化最大完工時間問題,文獻[7]構造了改進的McNaughton規則,并證明該規則可以求出該問題的最優解。另外,有些學者研究了考慮釋放時間其他目標函數的平行機調度問題。例如,文獻[8]基于SPT和ERD規則的綜合改進,為作業帶有釋放時間單機最小化完工時間和問題提出一種INSERT算法,并運用大量實驗數據證明了其性能更優。……