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

发布时间：2020-04-18 15:19

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

第二章 占线策略与订单加工序列的基本性质研究如图 2-1 所示，每个矩形的宽度代表对应订单的长度，高度代表订单完工收益，如图中右上角所示。其中，由粗线围成的每个矩形分别代表一个被 A启动加工的订单，矩形的虚线部分表示该订单与 A加工的下一个订单的相交区域，表明前一个订单不能被 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 孙伟,刘晓冰,徐中;大规模客户化生产模式的实施策略及产品设计技术研究[J];大连理工大学学报;2000年02期

2 谢辉,唐莉;具有惩罚因子的合同加工排序问题研究[J];系统工程;1996年01期

3 刘朝晖;极小化延误工件个数的单机分组排序问题[J];华东理工大学学报;1997年05期

4 朱志军,徐寅峰,徐维军;局内租赁问题的风险补偿模型及其竞争分析[J];管理科学学报;2004年03期

5 吴士亮,薛恒新,韦东方;基于GT-ERP的面向大规模定制的客户订单管理[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