【摘要】：排序論是運(yùn)籌學(xué)中最重要的分支之一.在多種機(jī)器環(huán)境、限制條件、目標(biāo)函數(shù)下的大量排序模型已經(jīng)被學(xué)者們廣泛研究.本學(xué)位論文考慮了兩臺(tái)流水作業(yè)(flow-shop)機(jī)器環(huán)境下工件可拒絕的兩階段生產(chǎn)加工與運(yùn)輸?shù)募膳判騿栴}.為了節(jié)省成本或者使得生產(chǎn)耗時(shí)最小化,工件可拒絕的生產(chǎn)和運(yùn)輸?shù)膮f(xié)調(diào)排序問題已經(jīng)在文獻(xiàn)中被廣泛研究.通常的運(yùn)輸有工件未加工完階段間的運(yùn)輸和工件完成加工之后的運(yùn)輸.本文我們主要考慮的是工件未加工完階段間的運(yùn)輸.針對(duì)運(yùn)輸機(jī)有不同的數(shù)量限制和容量限制,我們?cè)谖闹袑⒎智樾斡懻?本文的結(jié)構(gòu)和主要結(jié)果如下:·在第一章,我們介紹了問題背景、常用排序記號(hào)、文獻(xiàn)綜述以及排序論中一些的基本結(jié)果和算法.·在第二章,我們研究了兩階段之間存在充足的運(yùn)輸機(jī)的排序問題TF2 | rej,v ≥ n |Cmax+ ∑ej給出了一個(gè)運(yùn)行時(shí)間為O(n(?)(p2j+t)max{Plj+t})的動(dòng)態(tài)規(guī)劃算法,一個(gè)2-近似算法和一個(gè)全多項(xiàng)式時(shí)間近似方案.·在第三章,我們研究了工件具有相同大小的排序問題TF2 | rej,sj=1 | Cmax +∑ej,給出了一個(gè)最壞性能比為2的啟發(fā)式算法.·在第四章,我們研究了工件具有不同大小的排序問題TF2| rej,sj|Cmax + ∑ ej,給出了一個(gè)最壞性能比為11/5的啟發(fā)式算法.·在第五章,我們研究了工件在第一臺(tái)機(jī)器上具有相同的加工時(shí)間時(shí)并且運(yùn)輸機(jī)數(shù)量固定的排序問題TF2 |rej,P1j=p1j=p1,v,sj Cmax + ∑ej,給出了一個(gè)運(yùn)行時(shí)間為O(cv+2vv+3n2v+1p1(?)p2j)的動(dòng)態(tài)規(guī)劃算法.
[Abstract]:Sequencing theory is one of the most important branches of operational research. In a variety of machine environments, constraints, objective functions under a large number of sorting models have been widely studied. In this dissertation, we consider the problem of integrated scheduling of two stages of production, processing and transportation, which can be rejected by two flow operations (flow-shop) machines. In order to save cost or minimize the production time, the coordinated scheduling of production and transportation of rejected jobs has been extensively studied in the literature. The usual transportation includes the transportation between the unprocessed stage of the workpiece and the transportation of the workpiece after the completion of the processing. In this paper, we mainly consider the transportation of the workpiece during the unfinished stage. In view of the different quantity and capacity limitation of transport aircraft, we will discuss the case in this paper. The structure and main results of this paper are as follows: in the first chapter, we introduce the background of the problem, common sort notation, literature review and some basic results and algorithms of sorting theory. In this paper, we study the ordering problem of sufficient transport planes between two stages. TF2 rej,v 鈮，

本文編號(hào)：2389430