【摘要】：現(xiàn)代企業(yè)制定生產(chǎn)計(jì)劃的主要依據(jù)是客戶訂單,如何對(duì)訂單進(jìn)行合理排序從而獲得更大收益成為企業(yè)在競(jìng)爭(zhēng)中獲勝的關(guān)鍵。論文針對(duì)到達(dá)時(shí)間具有動(dòng)態(tài)特征的訂單排序問題,運(yùn)用占線問題與競(jìng)爭(zhēng)策略理論和方法進(jìn)行研究。剖析占線策略與訂單加工序列的基本性質(zhì),并給出確定性策略執(zhí)行效果的分析思路;同時(shí),根據(jù)訂單組成因素的不同特征建立幾種排序模型、設(shè)計(jì)占線策略并證明其競(jìng)爭(zhēng)性能。論文的主要工作與創(chuàng)新點(diǎn)歸納為以下4個(gè)部分: 1.對(duì)加工長(zhǎng)度不同的占線訂單排序進(jìn)行研究。對(duì)于訂單完工收益與加工長(zhǎng)度無關(guān)的情形,設(shè)計(jì)出綜合完工收益、加工長(zhǎng)度及交貨期限三個(gè)因素的占線策略TAR ,并證明其競(jìng)爭(zhēng)比優(yōu)于策略ACE (Fung, 2005)和LWF (Chan, 2004)。例如,當(dāng)最長(zhǎng)與最短訂單長(zhǎng)度之比△取值1、5時(shí),TAR策略具有競(jìng)爭(zhēng)比4.56與11.11,而ACE競(jìng)爭(zhēng)比為5.0與11.47, LWF對(duì)應(yīng)值為5.0與21.0。同時(shí),證明該情形下確定性策略的競(jìng)爭(zhēng)比下界為(?)(△/log△),改進(jìn)現(xiàn)有下界△~(1/2)。對(duì)于Y=2、10等取值較小時(shí)進(jìn)一步給出下界為4.25、5.87等;對(duì)于完工收益與加工長(zhǎng)度相關(guān)的情形,分析指出兩種常見的定價(jià)策略,據(jù)此給出比現(xiàn)有研究更貼切的收益函數(shù)。針對(duì)函數(shù)特征設(shè)計(jì)訂單長(zhǎng)度中斷策略LAS ,并證明其競(jìng)爭(zhēng)比為Y + 2 Y+ 2,其中Y = 1 +c2 (c 1(1+a))且c1、c2與a均為收益函數(shù)的系數(shù)。 2.對(duì)加工長(zhǎng)度相等的三種占線訂單排序情形進(jìn)行研究。對(duì)于完工收益賦任意值的情形,證明確定性策略競(jìng)爭(zhēng)比下界為4,改進(jìn)已有的下界值2.59。結(jié)合TAR策略在△=1時(shí)的競(jìng)爭(zhēng)比4.56,論文將競(jìng)爭(zhēng)比上下界距離從當(dāng)前的( 5-2.59=) 2 .41縮小到( 4 .56- 4=) 0 .56;對(duì)于完工收益相等的情形,證明FCFS、PFCFS策略在有交貨期限約束時(shí)分別是不可中斷、可中斷—重啟兩種模型的最優(yōu)占線策略。有交貨期限的假設(shè)比現(xiàn)有研究無交貨期限或存在最早交貨時(shí)間限制的假設(shè)更加貼近于實(shí)際;第三,Chan等人提出了待處理訂單可撤銷的排序情形,并給出具有競(jìng)爭(zhēng)比5的占線策略。論文證明出相吻合的競(jìng)爭(zhēng)比下界,表明Chan等人給出的已是最優(yōu)占線策略。 3.結(jié)合訂單包含違約條款的特點(diǎn),主要對(duì)具有單倍違約懲罰的占線訂單排序進(jìn)行探究。對(duì)于完工收益與加工長(zhǎng)度無關(guān)的情形,證明常見的兩種收益貪婪策略WSPT (Smith, 1956)與LWF分別具有競(jìng)爭(zhēng)比O (△~2)與8△+3/2。進(jìn)而設(shè)計(jì)雙因素中斷策略BAC ,該策略在△ 9時(shí)具有競(jìng)爭(zhēng)比3? + o(△)。同時(shí),證明? = 1與△ 1時(shí)確定性策略的競(jìng)爭(zhēng)比下界分別為6.33與1 .366△+0.366;對(duì)于完工收益與加工長(zhǎng)度相關(guān)的情形,證明LAS策略在具有單倍違約懲罰時(shí)的競(jìng)爭(zhēng)比為3Y + 2+22Y2 +3Y。比較它在沒有違約懲罰時(shí)的競(jìng)爭(zhēng)比Y + 2 Y+ 2,說明懲罰因子使得LAS策略的競(jìng)爭(zhēng)性能顯著下降。此外,證明該情形下確定性策略的競(jìng)爭(zhēng)比下界等于Y +2。 4.對(duì)具有預(yù)知信息且加工長(zhǎng)度相等的半占線排序進(jìn)行研究。對(duì)于訂單完工收益具有上下界M與1的情形,證明策略LWF的競(jìng)爭(zhēng)比為4[ 1-(1/2)~k],其中k = logM。針對(duì)完工收益有界這一特征設(shè)計(jì)啟發(fā)式策略VAR并證明其競(jìng)爭(zhēng)比為c~*,它是一個(gè)與M大小相關(guān)的正數(shù)。比如M =23、21 0時(shí), c *= 2.93、3.75,而LWF對(duì)應(yīng)競(jìng)爭(zhēng)比為3.5、3.94。同時(shí),證明c*是確定性策略的競(jìng)爭(zhēng)比下界。對(duì)于預(yù)知有限時(shí)間段內(nèi)訂單到達(dá)信息的情形,分析指出有限預(yù)知信息無法改善確定性策略的競(jìng)爭(zhēng)性能,進(jìn)而設(shè)計(jì)隨機(jī)策略RLL。該策略在預(yù)知時(shí)間長(zhǎng)度為1、1/2時(shí)分別具有競(jìng)爭(zhēng)比3與7/2,突破確定性策略的競(jìng)爭(zhēng)比下界4。 論文的最后指出在占線訂單排序問題的后續(xù)工作中,有待于進(jìn)一步深入開展的一些研究方向。
【圖文】：

第二章 占線策略與訂單加工序列的基本性質(zhì)研究如圖 2-1 所示，每個(gè)矩形的寬度代表對(duì)應(yīng)訂單的長(zhǎng)度，高度代表訂單完工收益，如圖中右上角所示。其中，由粗線圍成的每個(gè)矩形分別代表一個(gè)被 A啟動(dòng)加工的訂單，矩形的虛線部分表示該訂單與 A加工的下一個(gè)訂單的相交區(qū)域，表明前一個(gè)訂單不能被 A完成；帶填充陰影的矩形表示加工子序列的最后一個(gè)訂單mJ ，它將被 A 完成；由細(xì)虛線圍成的每一個(gè)矩形分別代表OPT 所啟動(dòng)的一個(gè)訂單。從圖 2-1 中可以看出，OPT 所啟動(dòng)的每個(gè)訂單都是 1 個(gè)單位長(zhǎng)度，而 A所啟動(dòng)的訂單iJ 可能具有不同加工長(zhǎng)度，從而相應(yīng)的*|| ||iS 可能不相等。比如，在圖 2-1 中，，*1|| S ||= 1且*2|| S ||= 2。根據(jù)定理 2-4 知道*iS 中每個(gè)訂單的完工收益嚴(yán)格小于1( )iw J+，所以，細(xì)虛線矩形的高度均小于它右邊相鄰的粗線矩形。

西安交通大學(xué)博士學(xué)位論文如果 A在階段 1、2 分別選擇行動(dòng)1mS 、2mS ，則敵手將在階段 1 之后單輸入序列。敵手在某個(gè)階段能夠終止一個(gè)輸入序列的前提條件是列截至當(dāng)前階段已經(jīng)使得OPT 的收益達(dá)到 A的 c倍收益。當(dāng)階段一個(gè)階段）結(jié)束之后，對(duì)于 A的各種選擇，敵手都將終止訂單輸入
【學(xué)位授予單位】：西安交通大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2006
【分類號(hào)】：F224.3;F272

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 孫偉,劉曉冰,徐中;大規(guī)�？蛻艋a(chǎn)模式的實(shí)施策略及產(chǎn)品設(shè)計(jì)技術(shù)研究[J];大連理工大學(xué)學(xué)報(bào);2000年02期

2 謝輝,唐莉;具有懲罰因子的合同加工排序問題研究[J];系統(tǒng)工程;1996年01期

3 劉朝暉;極小化延誤工件個(gè)數(shù)的單機(jī)分組排序問題[J];華東理工大學(xué)學(xué)報(bào);1997年05期

4 朱志軍,徐寅峰,徐維軍;局內(nèi)租賃問題的風(fēng)險(xiǎn)補(bǔ)償模型及其競(jìng)爭(zhēng)分析[J];管理科學(xué)學(xué)報(bào);2004年03期

5 吳士亮,薛恒新,韋東方;基于GT-ERP的面向大規(guī)模定制的客戶訂單管理[J];計(jì)算機(jī)工程;2004年23期

6 李仁旺,祁國(guó)寧,顧新建,謝銀軍,吳昭同;大批量定制生產(chǎn)方式及其實(shí)施方法研究[J];機(jī)械工程師;1999年03期

7 陳礴;A Review of On-Line Machine Scheduling:Algorithms and Competitiveness[J];數(shù)學(xué)理論與應(yīng)用;1999年03期

8 張峰,陳德伍;最小化延誤工序的單機(jī)限期批處理問題(英文)[J];數(shù)學(xué)理論與應(yīng)用;1999年03期

9 堵丁柱;k車服務(wù)問題與競(jìng)爭(zhēng)算法[J];數(shù)學(xué)的實(shí)踐與認(rèn)識(shí);1991年04期

10 徐寅峰,王刊良;局內(nèi)出租車調(diào)度與競(jìng)爭(zhēng)算法[J];西安交通大學(xué)學(xué)報(bào);1997年S1期

本文編號(hào)：2632232