限位排序和單機(jī)工件運(yùn)輸排序的若干結(jié)果.pdf

1、商，面畫授予單位代碼：!Q!i!研究生學(xué)號：Q!Q!!Z密級：——鄭州大學(xué)碩士學(xué)位論文論文題目：限位排序和單機(jī)工件運(yùn)輸排序的若干結(jié)果作者姓名：學(xué)科門類：專業(yè)方向：導(dǎo)師姓名、職稱：陳友軍理學(xué)運(yùn)籌學(xué)與控制論林詒勛教授二零零五年四月摘要在本文中，我們研究了兩種排序模型：(1)工件具有位置約束的限位排序問題(2)工件先加工后運(yùn)送到顧客的單機(jī)排序問題(1)工件具有位置約束的限位排序問題在限位排序中『1，61，我們有n個工件J1，如，，厶和m個工件

2、族五，磊，，，m且五n乃=O(i≠』)，它們是工件集以，J2，，厶)的一個劃分每個工件Jj有一個加工時間p，，權(quán)“，，到達(dá)時間q和一個工期出，每個族氕有一個位置允許集＆∈1，2，，n)，％=1，2，一，m對于i≠J來說，&與昂可以相交在文獻(xiàn)中，這個問題被記為IlPRIf，其中，=c矗一∑G，∑q弓，∑q％，∑％Q這個問題(IIPRIf)最早由林詒勛和原晉江提出，我們知道11『∑q島可以按照Smith。s規(guī)則獲得最優(yōu)解，1IlL。ax可以

3、按照EDD規(guī)則獲得最優(yōu)解，11I∑wj叻和11I∑w3Tj都是NP困難的但是IIPRI∑功G的復(fù)雜性仍是未知的我們通過考慮此間題的特殊情形，給出了一些多項(xiàng)式可解的例子，接著考慮了—個關(guān)于平行機(jī)排序問題(2)工件先分批加工后運(yùn)送到顧客的單機(jī)排序問題在一般的單機(jī)排序和工件運(yùn)輸問題模型中，我們有n個工件以，也，，^，它們先分批后在一臺機(jī)器上NZ_，然后被一個有容量限制的汽車運(yùn)送給兩個顧客每個工件^有一個加工時間pj和—個尺寸s，，在這里sj代

4、表工件如被裝到汽車中所要占的空間大小僅僅有一輛汽車去運(yùn)送所有的工件，它有一個容量限制z目標(biāo)是尋找一個工件加工和運(yùn)輸?shù)呐判?，使得所有工件被加工完畢并運(yùn)送給顧客的時間達(dá)到最小本文考慮的是在2T1≥T3限制下的問題根據(jù)Lee和Chen[15l的記號，這個問題被記為1一D，k=2m。1，c=：，2T1≥T3IC。。，這里“1一D，k=2”表示工件首先在一臺機(jī)器上加工，然后被運(yùn)送給兩個顧客；“v=1，c=z”表示僅僅有一輛汽車去運(yùn)送所有的工件，并

5、且汽車的容量為#工件加工和運(yùn)輸?shù)呐判騿栴}已經(jīng)成為在近十幾年里最重要的被廣泛研究的課題之一Ahmadi17]等人研究了兩臺機(jī)器(一臺單機(jī)和一臺隨后的分批加工機(jī)器)的flowshop排序問題，目標(biāo)是最小化最大完工時間與完工時間總和Iterrmann和Lee【l4]，Yuanf19]，Chen【9]1Yang[18]和Cheng【11lg筍人考慮了帶有工期相關(guān)指標(biāo)的分批排序問題Lee和Chen『151根據(jù)運(yùn)輸時間和汽車容量，而不管運(yùn)送費(fèi)用，考