1、不同于傳統(tǒng)加工機器，批處理機器一次能夠加工一批多個工件（或作業(yè)）。批處理機在生產企業(yè)中具有廣泛的應用，包括電子芯片廠、鋼鐵企業(yè)、航空工業(yè)等。合理地調度批處理機的加工任務，能夠有效地提高企業(yè)的生產效率，降低生產成本。因此，研究批處理機調度（簡稱批調度）問題不但具有重要的理論價值，還具有迫切的現(xiàn)實意義。
　　不同尺寸的工件（簡稱差異工件）是一個常見于制造車間的現(xiàn)實約束。而早期的研究大都假設工件具有相同的尺寸（即單位尺寸）。本論文研究不

2、同尺寸工件機器批調度問題。相比相同尺寸的情形，本文問題是更一般也更為復雜的調度問題，它兼具排序問題和裝箱問題的雙重性質。
　　本文的主要研究工作和創(chuàng)新點如下:
　　(1)研究了工件具有不同尺寸和任意到達時間的單機批調度問題。問題的目標函數(shù)為最小化制造跨度。該問題屬于NP-hard問題。首先，我們提出了本問題的兩個下界，并證明了下界的有效性。其次，我們從一種新的角度提出了若干種啟發(fā)式構造型算法。在制定分批的決策中，工件的加工時

3、問和到達時間常常是兩個相互矛盾的因素。這也正是研究本問題的一個難點。因此，現(xiàn)有的算法在分批過程中往往只考慮了某一個因素的影響。然而，我們提出的算法在分批時試圖兼顧加工時間和到達時間兩個因素的作用。第一，我們提出了距離矩陣的概念;第二，我們設計了若干種基于距離矩陣的構造型算法，用于將工件分批;然后，我們采用已有的批排序算法ERT規(guī)則，用于安排批在機器上的加工。大量的仿真實驗比較了我們的算法和現(xiàn)有的求解方法。實驗結果證明了本文下界以及啟發(fā)式

4、算法的有效性。
　　(2)研究了一類兩階段流水車間批調度問題，考慮不同的工件尺寸、任意到達時間、以及阻塞約束。優(yōu)化目標為最小化制造跨度。首先，我們對這一問題建立了混合整數(shù)規(guī)劃模型。然后，提出了一種混合的離散差分進化算法。在提出的算法中，個體采用離散的工件序列編碼。然后，基于該編碼方式，設計新穎的變異和交叉算子。接著，我們使用first-fit規(guī)則將工件分批;并提出一種新的最小閑置/阻塞時間算法，用來安排批在車間里的加工次序。為了進

5、一步改進求解質量，一種局部搜索算法被集成到差分進化算法當中。仿真實驗證實了所提出算法在解質量、魯棒性以及計算時間方面的優(yōu)異性。
　　(3)考察了差異工件兩類批處理機的流水車間調度問題。兩階段各包含一臺批處理機。第一臺機器為并行批處理機，第二臺為串行批處理機。優(yōu)化目標為最小化制造跨度。我們對該問題建立了混合整數(shù)規(guī)劃模型。然后，我們提出了一種基于種群的進化算法-分布估計算法。在該分布估計算法中，個體被編碼成工件序列。接著，構造一種概率