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

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

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

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

4、表工件如被裝到汽車(chē)中所要占的空間大小僅僅有一輛汽車(chē)去運(yùn)送所有的工件，它有一個(gè)容量限制z目標(biāo)是尋找一個(gè)工件加工和運(yùn)輸?shù)呐判颍沟盟泄ぜ患庸ね戤叢⑦\(yùn)送給顧客的時(shí)間達(dá)到最小本文考慮的是在2T1≥T3限制下的問(wèn)題根據(jù)Lee和Chen[15l的記號(hào)，這個(gè)問(wèn)題被記為1一D，k=2m。1，c=：，2T1≥T3IC。。，這里“1一D，k=2”表示工件首先在一臺(tái)機(jī)器上加工，然后被運(yùn)送給兩個(gè)顧客；“v=1，c=z”表示僅僅有一輛汽車(chē)去運(yùn)送所有的工件，并

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