差異工件機(jī)器批調(diào)度若干問(wèn)題研究.pdf

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

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

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

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

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