论文部分内容阅读
现代企业制定生产计划的主要依据是客户订单,如何对订单进行合理排序从而获得更大收益成为企业在竞争中获胜的关键。论文针对到达时间具有动态特征的订单排序问题,运用占线问题与竞争策略理论和方法进行研究。剖析占线策略与订单加工序列的基本性质,并给出确定性策略执行效果的分析思路;同时,根据订单组成因素的不同特征建立几种排序模型、设计占线策略并证明其竞争性能。论文的主要工作与创新点归纳为以下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。论文的最后指出在占线订单排序问题的后续工作中,有待于进一步深入开展的一些研究方向。