占线订单排序问题及其竞争策略研究

论文摘要

现代企业制定生产计划的主要依据是客户订单,如何对订单进行合理排序从而获得更大收益成为企业在竞争中获胜的关键。论文针对到达时间具有动态特征的订单排序问题,运用占线问题与竞争策略理论和方法进行研究。剖析占线策略与订单加工序列的基本性质,并给出确定性策略执行效果的分析思路;同时,根据订单组成因素的不同特征建立几种排序模型、设计占线策略并证明其竞争性能。论文的主要工作与创新点归纳为以下4个部分:1.对加工长度不同的占线订单排序进行研究。对于订单完工收益与加工长度无关的情形,设计出综合完工收益、加工长度及交货期限三个因素的占线策略TAR ,并证明其竞争比优于策略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策略在有交货期限约束时分别是不可中断、可中断—重启两种模型的最优占线策略。有交货期限的假设比现有研究无交货期限或存在最早交货时间限制的假设更加贴近于实际;第三,Chan等人提出了待处理订单可撤销的排序情形,并给出具有竞争比5的占线策略。论文证明出相吻合的竞争比下界,表明Chan等人给出的已是最优占线策略。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。针对完工收益有界这一特征设计启发式策略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。论文的最后指出在占线订单排序问题的后续工作中,有待于进一步深入开展的一些研究方向。

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 研究背景与意义
• 1.2 国内外相关研究综述
• 1.2.1 占线问题与竞争策略理论研究综述
• 1.2.2 离线订单排序问题研究综述
• 1.2.3 占线订单排序问题研究综述
• 1.3 相关理论基础概述
• 1.4 研究内容与研究方法
• 1.4.1 研究内容
• 1.4.2 研究方法
• 第二章 占线策略与订单加工序列的基本性质研究
• 2.1 基本概念预备知识
• 2.2 完工收益与加工长度无关的情形
• 2.2.1 加工序列特征分析
• 2.2.2 占线与离线策略的收益特性分析
• 2.3 完工收益与加工长度相关的情形
• 2.3.1 问题特征分析
• 2.3.2 占线策略的基本性能分析
• 2.4 竞争比下界分析思路
• 2.5 本章小结
• 第三章 加工长度不同的占线订单排序及其竞争策略研究
• 3.1 完工收益与加工长度无关的情形
• 3.1.1 问题描述与建模
• 3.1.2 三因素中断策略（ TAR ）的设计与分析
• 3.1.3 竞争比下界分析
• 3.2 完工收益与加工长度相关的情形
• 3.2.1 收益函数特征刻画
• 3.2.2 不可中断策略的竞争分析
• 3.2.3 订单长度中断策略（ LAS ）的设计与分析
• 3.2.4 竞争比的参数分析
• 3.3 本章小结
• 第四章 加工长度相等的占线订单排序及其竞争策略研究
• 4.1 完工收益赋任意值的情形
• 4.2 完工收益相等的情形
• 4.2.1 不可中断模型的竞争策略分析
• 4.2.2 可中断—重启模型的策略设计
• 4.3 待处理订单可撤销的情形
• 4.3.1 问题建模
• 4.3.2 竞争比的紧下界证明
• 4.4 本章小结
• 第五章 具有违约惩罚的占线订单排序及其竞争策略研究
• 5.1 完工收益与加工长度无关的情形
• 5.1.1 基于收益贪婪策略的竞争分析
• 5.1.2 双因素中断策略（ BAC ）的设计与分析
• 5.1.3 竞争比下界分析
• 5.2 完工收益与加工长度相关的情形
• 5.2.1 订单长度中断策略（ LAS ）的竞争分析
• 5.2.2 竞争比的参数分析
• 5.2.3 竞争比下界分析
• 5.3 本章小结
• 第六章 预知部分信息的半占线订单排序及其竞争策略研究
• 6.1 预知完工收益上下界的情形
• 6.1.1 竞争策略的设计与分析
• 6.1.2 竞争比的紧下界证明
• 6.1.3 数值分析
• 6.2 预知有限时间段内订单到达信息的情形
• 6.2.1 随机策略（ RLL ）及其性质分析
• 6.2.2 策略的竞争性能分析
• 6.3 本章小结
• 第七章 总结与展望
• 7.1 主要工作与创新性成果
• 7.2 需要进一步研究的问题
• 致谢
• 参考文献
• 读博期间发表或被录用文章
• 读博期间参加课题与获奖情况
• 读博期间的获奖情况