具有学习效应且工件可拒绝单机排序问题探讨.docx

具有学习效应且工件可拒绝单机排序问题探讨摘要：文章对工件具有与已加工工件有关的安装时间且工件的加工时间具有学习效应的工件可拒绝的排序问题进行了研究；对目标函数为极小化最大完工时间与总拒绝费用之和以及极小化完工时间和与总拒绝费用之和分别给出了一个动态规划算法。关键词：单机排序；学习效应；工件可拒绝；动态规划算法；目标函数文献标识码：A中图分类号：O223文章编号：1009-2374（2015）29-0078-02DOI：10.13535/ki.11-4406/n.2015.29.039具有学习效应的排序问题首先由Biskup提出他假设工件的加工时间随着熟练程度的提高而越来越短即工件越往后加工所需的时间将减少。随后Mosheiov和Sidney、Biskup和Simons、Koulamas和Kyparisis等进行了相关的研究。更多相关研究可参考文献[5]至参考文献[9]。王吉波研究了工件的加工时间与已加工工件有关的学习效应的排序问题并指出最小化最大完工时间、完工时间和以及完工时间平方和是多项式时间可求解的而最小化加权完工时间和、最大延误在一定条件下是多项式时间可求解的。工件可拒绝的排序模型首先由Y.Bartal等提出他们分别研究了离线情形和在线情形下的的排序模型。S.S.Selden等探讨了极小化总拒绝费用和最大完工时间之和的可中断平行机模型。Y.He和X.Min研究了两台同类机以及三台同类机可拒绝的排序的一个特殊情形。D.Engels等证明了是NP-困难的并给出了伪多项式时间的动态规划算法和FPTAS算法。S.Sengupta对目标函数为极小化总拒绝费用与最大延迟/延误的可拒绝排序模型进行了研究。本文在参考文献[10]的模型的基础上研究了工件可拒绝的排序问题对原有理论进行了扩展。1问题假设有一工件集需要在一台机器上加工机器一次只能加工一个工件且工件加工不可中断。工件排在第个位置加工的实际加工时间为其中为工件的正常加工时间为排在第个位置的工件的正常加工时间为常数。任一工件在加工前有一安装时间第个位置的工件的安装时间为且有其中为常数为排在第个位置工件的实际加工时间。以下将这类安装时间简记为。工件在加工过程中由于有的工件加工时间非常长或费用很大因此采取不加工此工件而是通过支付一定的费用后送到外面去“外加工”或购买更合算。假设工件的拒绝费用为表示加工工件的集合表示拒绝工件的集合所研究问题用参数法表示为：2的动态规划算法引理：问题存在一个最优序在该序中工件按的非降序排列。在这个动态规划算法中我们需要计算个的值其中计算每个值需要的时间所以这个动态规划算法的计算复杂性为。4结语本文对可拒绝加工的一类排序问题进行了研究其中工件的加工时间具有学习效应安装时间与已加工工件有关对两类目标函数分别给出了动态规划算法。读者可以继续研究多机环境下相关的问题。参考文献[1]BisupD.Singlemachineschedulingwithlearningconsiderationgs[J].EuropeanJournalofOperationalResearch1999115（1）.[2]MosheiovG.SidneyJB.Schedulingwithgeneraljob-dependentlearningcurve[J].EuropeanJournalofOperationalResearch2003147（3）.[3]BisupDSimonsmonduedateschedulingwithautonomousandinducedlearning[J].EuropeanJournalofOperationalResearch2004159（3）.[4]KoulamasCKyparisisGJ.Single-machineandtwo-machineflowshopschedulingwithgenerallearningfunctions[J].EuropeanJournalofOperationalResearch2007178（2）.[5]KuoWHYangDL.Singlemachineschedulingwithpastsequence-dependentsetuptimesandlearningeffects[J].InformationProcessingLe