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

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

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

【參考文獻】

相關期刊論文 前10條

1 孫偉,劉曉冰,徐中;大規(guī)模客戶化生產模式的實施策略及產品設計技術研究[J];大連理工大學學報;2000年02期

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

3 劉朝暉;極小化延誤工件個數的單機分組排序問題[J];華東理工大學學報;1997年05期

4 朱志軍,徐寅峰,徐維軍;局內租賃問題的風險補償模型及其競爭分析[J];管理科學學報;2004年03期

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

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

7 陳礴;A Review of On-Line Machine Scheduling:Algorithms and Competitiveness[J];數學理論與應用;1999年03期

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

9 堵丁柱;k車服務問題與競爭算法[J];數學的實踐與認識;1991年04期

10 徐寅峰,王刊良;局內出租車調度與競爭算法[J];西安交通大學學報;1997年S1期

本文編號：2632232