具有釋放時間的單機半連續(xù)型批處理機調(diào)度問題.pdf

1、半連續(xù)型批處理機調(diào)度問題是從鋼鐵工業(yè)加熱爐對管坯加熱的過程中提煉的，它的主要特征是工件按批加工，工件必須按周期的進入和離開處理機，只有一批工件全部加工完才可以加工下一批的工件，同一批中工件的加工時間為此批工件中的最大加工時間。由于批中的工件是連續(xù)進、連續(xù)出的，所以批的容量即批的大小可以是無限的。又因為工件具有釋放時間，所以在加工同批工件的過程中，存在有空位和無空位兩種情況。本文從這兩方面進行了研究，具體內(nèi)容概括如下：
　　1.當同

2、批工件加工過程中無空位產(chǎn)生，即工件按周期一個緊挨著一個進入和離開處理機時，本文主要從兩個方面進行了理論研究：
　　（1）為了提高機器的利用率，即對于目標函數(shù)是最大完工時間的調(diào)度問題，當工件的釋放時間和加工時間同序時，分析其問題的最優(yōu)解性質(zhì)，給出一個計算復(fù)雜性為On的動態(tài)規(guī)劃算法，證明了算法的最優(yōu)性，并用數(shù)值例子進一步說明此算法。
　?。?）當工件帶權(quán)時，對于工件的加工時間相等的特殊情況，給出了目標函數(shù)是最大完工時間的調(diào)度問題