本文選題：調(diào)度　切入點(diǎn)：批處理機(jī)　出處：《中國(guó)科學(xué)技術(shù)大學(xué)》2016年博士論文　論文類型：學(xué)位論文

【摘要】：不同于傳統(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è)上件具有相同的尺寸(即單位尺寸)。本論文研究不同尺-寸工件機(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í)間和到達(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ā)式算法的有效性。(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)一步改進(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)造一種概率模型以抽樣產(chǎn)生新個(gè)體,并提出一種增量學(xué)習(xí)型方法以更新概率模型。我們采用best-fit規(guī)則對(duì)工件分批,并提出一種最小閑置/等待時(shí)間算法,以排列批的加工次序。為了進(jìn)一步改進(jìn)算法的求解質(zhì)量,兩種局部搜索算法被嵌入到該分布估計(jì)算法當(dāng)中。計(jì)算機(jī)實(shí)驗(yàn)表明了該分布估計(jì)算法在解質(zhì)量與魯棒性方面的有效性。
[Abstract]:Different from the traditional processing machine, a batch machine can process a batch of jobs (or operation). Batch processor is widely used in the production of enterprises, including electronic chip factory, iron and steel enterprises, aviation industry and other processing tasks reasonably. Scheduling of batch processing, can effectively improve the production efficiency of enterprises and reduce the production cost. Therefore, study on batch scheduling (the batch scheduling problem) not only has important theoretical value, but also has the realistic meaning. The workpieces with different sizes (the different workpiece) is a common in cars between real constraints. The early studies on a hypothesis with the same dimensions (the unit size). This paper studies the different scale - Inch workpiece machine batch scheduling problem. Compared with the same size of the case, the problem is more general and more complex scheduling problems, and it has sorting and packing The dual nature of the problem. This paper mainly studies on the work and innovation are as follows: (1) study the workpiece with different size and arrival time of any single batch scheduling problem. The objective function of the problem is to minimize the make span. The problem is a NP-hard problem. First, we present two lower bounds for this problem, and prove the validity of the lower bound. Secondly, we put forward some constructive heuristic algorithm from a new angle. In the formulation of batch decision-making, the processing time and arrival time are two contradictory factors. This is also a difficult problem in this research. Therefore, the existing the algorithm in batch process often only consider the influence of one factor. However, our proposed algorithm attempts to balance the processing time and arrival time of the two factors in batch. First, we propose a distance matrix 姒傚康錛氱浜，

本文編號(hào)：1603442