资源描述：
《局内故障产品处理问题与竞争算法ξ》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第21卷第3期(总第117期)系统工程Vol.21,No.32003年5月SystemsEngineeringMay.,2003文章编号:100124098(2003)0320095206X局内故障产品处理问题与竞争算法辛春林,崔文田,徐寅峰(西安交通大学管理学院,陕西西安710049)摘要:提出和研究局内故障产品处理问题。该问题是故障产品序列如何以局内方式(即在未知故障产品损坏程度的状况下)进行处理(返修还是报废),使得处理故障产品的损失最小。设计解决该问题的竞KK争算法,证明采用优先返修策略É(PRRSÉ),竞争比为2-·;采用优先返修策略Ê(PRRSÊ),CX1K
2、K竞争比为2-·;最后,对局内故障产品处理问题的两种算法做出了比较并相应的给出了比G+KX1较结果。关键词:局内问题;故障产品;返修优先策略;竞争算法中图分类号:C931.1文献标识码:A本文研究故障产品处理问题与竞争算法。企业的质量目标是生产顾客满意的产品,追求产品质量的零缺陷。但在企业实际生产中产品质量事故是在所难免的,处理这些带有质量故障的产品(以下简称为故障产品),一般来讲,企业会把这些故障产品返修成合格产品,再出售给顾客。但是如果故障产品存在的问题太大,返修的成本太高,这时就应该将故障产品报废。如果事先知道每件故障产品的损坏程度,则决定该产品返修还是报废是显而
3、易见的事。由于事先不知道每件故障产品的损坏程度,所以就很难做出最优决策。以往的优化理论是建立在确定的已知条件的基础上来求出最优解,但这种静态分析不能代表动态的现实情况,实际上在某一条件下得出的最优解有可能是另一条件下的最劣解。我们把这种缺乏将来信息的问题称之为局内问题。局内问题是依次接收输入,在未知将来情况下,每个输入相应地产生输出。竞争分析是局内竞争算法A与最优的局外算法OPT的比值。最优的局外算法是事先已知整个输入序列且能最优处理。任意给定一个输入序列R,令CA(R)和COPT(R)分别表示局内竞争算法A和最优的局外算法OPT对应的解,若存在常数A和B且对所有序列R
4、满足CA(R)≤AõCOPT(R)+B则称竞争算法A具有A竞争比。若B=0,则称局内算法为严格的A2competitive.在过去的十几年中,局内问题和竞争算法已经吸引了人们浓厚的研究兴趣。人们通过比较局内算法与最优的局外算法来进行竞争分析,竞争分析已经成功地应用于许多领域。在20世纪80年代后期90年代初期,人们围绕着三个基本的局内问题展开研究,即页面调度,k2服务问题和度量任务系统。除此以外,在一些领域,如数据结构、分布式数据管理、调度与负载平衡、行程安排、机器人技术、金融博弈、图论和计算机系统的许多方面,该理论有着广[1-7]阔的科研和应用前景。在国际上实际已经有
5、很多这方面的研究成果,目前国内也在积极探索这方面的研[8-11]究。X收稿日期:2002211224基金项目:国家自然科学基金资助项目(B类70028102)作者简介:辛春林,男,西安交通大学管理学院研究生;崔文田,男,西安交通大学管理学院管理科学系副教授;徐寅峰,男,西安交通大学管理学院管理科学系主任,教授,博士生导师。96系统工程2003年1故障产品处理问题(1)问题的描述故障产品处理问题的实际背景是一家加工型企业生产出一批不合格零件R=(R1,R2,⋯,Rk),这些不合格零件经过返修可以成为合格零件。如果返修成本过高,大于生产成本,返修就是一种得不偿失的策略。如果
6、这些不合格零件存在的问题不大,报废实在又太可惜了。因此,公司要决策这些故障产品到底是返修还是报废。在本文中讨论的零件均指不合格零件。假设返修不合格零件是在一条零件返修流水生产线上,零件返修流水线有n道工序t=(t1,t2,⋯,tn),零件在每道工序的返修成本都不同。为研究方便起见,可以简化为以n个顶点代表n道工序,顶点序列为(1,2,⋯,n),相应的n返修成本序列为X=(X1,X2,⋯,Xn),令C=∑Xl,C表示n道工序的返修成本之和。l=1考虑到以下两个问题:①如果事先已知零件序列R中每个零件的损坏情况,选择返修还是报废,处理该零件序列的总损失为多少?②如果事先未知
7、零件序列R中每个零件的损坏情况,又该如何处理,总损失为多少?不合格零件处理问题优化的目标是在未知每件零件的损坏情况的前提下零件何时应返修、何时该报废,使处理零件序列的总损失最少。问题①是局外问题(off2line),由于已知不合格零件序列损坏情况的全部信息,所以很容易找出损失最小的最佳决策。问题②是局内问题(on2line),由于每次给定的零件序列都很可能不同,每一时刻又仅能知道已返修的零件损坏的信息,而无法知道未返修的零件损坏的信息,这种只知道零件序列损坏的部分信息,未知全部信息的性质,就是该问题的局内性。而正是由于该问题为局内问题,使
