具有学习与退化效应的排序问题

论文摘要

排序问题是一类重要的组合优化问题.在经典排序模型中通常假设工件的加工时间为常数.但在许多实际问题中,工件的加工时间可能与其开工时间、所用资源或所处的位置有着某种联系。由此产生一类现代排序问题:具有学习与退化效应的排序问题.例如,产业工人由于连续重复做相似的工作,效率会越来越高,这种现象在文献中称之为“学习效应”;由于机器的老化,会使机器的运行速度慢下来,工件的实际加工时间会变长,这种现象在文献中称之为“退化现象”（Pinedo,2002[31]）.本文研究了具有学习效应与退化现象的排序问题,主要结果如下:1.具有学习与退化效应的单机排序问题,（a）对于问题1|Pj[r]=pjα（t）ra|Cmax,证明了工件按pj非减顺序排列可以得到最优排序（即SPT序）.（b）对于问题（?）,证明当pi≤pj有wj≤wi时,工件按（?）非减的顺序排列可以得到最优序.（c）对于问题1|Pj[r]=pjα（t）ra|Lmax,证明当di≤dj有pi≤pj时,工件按dj非减顺序排列可以得到最优排序.其中退化因子α（t）≥0为t的非减凸函数,r表示工件在序列中所处的位置,a表示学习因子.2.具有学习与退化效应的资源限制排序问题对于问题1|pj[r]=（pj+βt）ra,rj=f（uj）,Cmax≤C|（?）和1|Pj[r]=（pj+βt）ra,rj=f（uj）,（?）≤U|Cmax,分别给出了最优算法,并证明了算法的正确性.其中uj是分配工件Jj的资源量,f是正值严格递减的函数.U是连续可分配的资源总数,C满足（?）的常数.3.具有学习效应的排序问题（a）对于问题（?）给出了最优算法;对于问题（?）在某些特殊情形下给出最优算法.（b）对于排序模型证明了SPT规则能够得到最优序.其中ord表示工件满足下列条件:对任一工件j有aj≤bj,且对于两个工件j,k,若aj≤ak,则有bj≤bk.这里的aj,bj表示工件j的分别在第一台机器和第二台机器上的基本加工时间; prp表示工件满足:bj=caj（这里c≥1是一个常数）.

论文目录

• 摘要
• Abstract
• 第一章 引言
• §1.1 排序的介绍
• §1.2 排序定义与记号
• §1.3 研究概况及本文结果
• 第二章 具有学习与退化效应的单机排序问题
• §2.1 模型介绍及相关引理
• §2.2 单机排序问题的若干结论
• 第三章 具有学习与退化效应的资源限制排序问题
• §3.1 相关介绍
• §3.2 最小化总资源消耗量问题
• §3.3 最小化时间表长问题
• 第四章具有学习效应的排序问题
• §4.1 单机排序问题
• §4.2 一类特殊的流水机排序问题
• 进一步研究
• 参考文献
• 附录:硕士期间完成论文
• 致谢