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

【摘要】：不同于傳統(tǒng)加工機器,批處理機器一次能夠加工一批多個工件(或作業(yè))。批處理機在生產(chǎn)企業(yè)中具有廣泛的應(yīng)用,包括電子芯片廠、鋼鐵企業(yè)、航空工業(yè)等。合理地調(diào)度批處理機的加工任務(wù),能夠有效地提高企業(yè)的生產(chǎn)效率,降低生產(chǎn)成本。因此,研究批處理機調(diào)度(簡稱批調(diào)度)問題不但具有重要的理論價值,還具有迫切的現(xiàn)實意義。不同尺寸的工件(簡稱差異工件)是一個常見于制造車間的現(xiàn)實約束。而早期的研究大都假設(shè)上件具有相同的尺寸(即單位尺寸)。本論文研究不同尺-寸工件機器批調(diào)度問題。相比相同尺寸的情形,本文問題是更一般也更為復雜的調(diào)度問題,它兼具排序問題和裝箱問題的雙重性質(zhì)。本文的主要研究上作和創(chuàng)新點如下：(1)研究了工件具有不同尺寸和任意到達時間的單機批調(diào)度問題。問題的目標函數(shù)為最小化制造跨度。該問題屬于NP-hard問題。首先,我們提出了本問題的兩個下界,并證明了下界的有效性。其次,我們從一種新的角度提出了若干種啟發(fā)式構(gòu)造型算法。在制定分批的決策中,工件的加工時間和到達時間常常是兩個相互矛盾的因素。這也正是研究本問題的一個難點。因此,現(xiàn)有的算法在分批過程中往往只考慮了某一個因素的影響。然而,我們提出的算法在分批時試圖兼顧加工時間和到達時間兩個因素的作用。第一,我們提出了距離矩陣的概念：第二,我們設(shè)計了若干種基于距離矩陣的構(gòu)造型算法,用于將工件分批；然后,我們采用已有的批排序算法ERT規(guī)則,用于安排批在機器上的加工。大量的仿真實驗比較了我們的算法和現(xiàn)有的求解方法。實驗結(jié)果證明了本文下界以及啟發(fā)式算法的有效性。(2)研究了一類兩階段流水車間批調(diào)度問題,考慮不同的工件尺寸、任意到達時間、以及阻塞約束。優(yōu)化目標為最小化制造跨度。首先,我們對這一問題建立了混合整數(shù)規(guī)劃模型。然后,提出了一種混合的離散差分進化算法。在提出的算法中,個體采用離散的工件序列編碼。然后,基于該編碼方式,設(shè)計新穎的變異和交叉算子。接著,我們使用first-fit規(guī)則將工件分批；并提出一種新的最小閑置/阻塞時間算法,用來安排批在車間里的加工次序。為了進一步改進求解質(zhì)量,一種局部搜索算法被集成到差分進化算法當中。仿真實驗證實了所提出算法在解質(zhì)量、魯棒性以及計算時間方面的優(yōu)異性。(3)考察了差異工件兩類批處理機的流水車間調(diào)度問題。兩階段各包含一臺批處理機。第一臺機器為并行批處理機,第二臺為串行批處理機。優(yōu)化口標為最小化制造跨度。我們對該問題建立了混合整數(shù)規(guī)劃模型。然后,我們提出了一種基于種群的進化算法-分布估計算法。在該分布估計算法中,個體被編碼成工件序列。接著,構(gòu)造一種概率模型以抽樣產(chǎn)生新個體,并提出一種增量學習型方法以更新概率模型。我們采用best-fit規(guī)則對工件分批,并提出一種最小閑置/等待時間算法,以排列批的加工次序。為了進一步改進算法的求解質(zhì)量,兩種局部搜索算法被嵌入到該分布估計算法當中。計算機實驗表明了該分布估計算法在解質(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 姒傚康錛氱浜，

本文編號：1603442