具有学习效应的总完工时间流水作业问题孙林辉1,2,丹3,王吉波2,3王(1.西安理工大学经济与管理学院,西安710054;2.机械制造系统工程国家重点实验室,西安710054;3.沈阳航空航天大学理学院,沈阳110136)【摘要】研究工件具有学习效应的2台机器流水作业排序问题。工件的学习效应指工件的加工时间为所排位置的指数函数。目标函数为极小化总完工时间。给出该问题的数学规划模型。同时对大规模问题给出3个启发式算法,计算结果表明,用这3个算法解决所研究问题比较有效。中图分类号:O223文献标识码:AFlowshopProblemtoMinimizeTotalCompletionTimewithALearningEffSUNLin2hui1WANGDan3WANGJi2bo2,(1.SchoolofEconomicsandManagement,Xi’anUniversityofTechnology,Xi’an710054,China;2.TheStateKeyLaboratoryforManufacturingSystemsEngineering,Xi’an710054,China;【Abstract】Inthispaperweconsideratwo2machineflowshopschedulingproblemwithalearningeffect.Thelearningeffectofajobisassumedtobeanexponentfunctionofitsposition.Theobjectiveistofindasequencethatminimizesthetotalcompletiontime.Amathematicalprogrammingmodelisdevelopedfortheproblem.andthreeheuristicalgorithmsareproposedforsolvingtheproblemwithlargescale.Com2puationalresultsshowthattheproposedheuristicalgorithmsareeffectiveinsolvingtheproblem问题。Biskup[2]证明了在工件引入学习效应情况下,目标函数为极小化共同工期偏差与完工时间和的单机排序问题分别是多项式时间可解。Cheng等[3]研究了工件加工时间具有学习效应的单机排序问题,其中,工件的学习效应模型为一个分片线性加工时间函数,目标函数为极小化最大延误时间。他们证明了此问题是强NP2难的,并给出了2个多项式时间可解的特殊情况。同时,他们还提出了2个启发式算法,并分析了它们的最坏情况界。随后,Mosheiov[4]研究了另外一些单机排序问题。证明利用最小加工时间优先规则(SPT)能得到最大完工在制造业系统中,排序问题是一类重要的问题,多年来人们一直致力于该问题的研究。在大多数排序问题中,工件的加工是一个独立的且与加工位置无关的常数。然而,在一些实际排序问题中,由于工人(机器)在长时间加工相同或类似的工件时,加工效率有可能逐渐提高,使后加工的工件的加工时间变小,这种现象被称为具有学习效应[1]。Biskup等[223]首先研究了具有学习效应的单收稿日期:2008211221修订日期:2010204202基金项目:国家自然科学基金资助项目(11001181)作者简介:孙林辉(19772),男,博士,讲师。研究方向为工业工程与行为运筹学。E2mail:dfishwang@hotmail.com---本文来源于网络，仅供参考，勿照抄，如有侵权请联系删除---权完工时间和、极小化最大延误及极小化误工工件数问题,经典排序中的结论不再成立。Mosheiov[5]又研究了具有学习效的平行机排序问题,证明了极小化完工时间和问题存在多项式时间最优算法,但是,算法复杂性远比经典问题复杂。Mosheiov等[6]研究了工件具有一般学习曲线的排序问题,即每个工件的学习率不同的情况。Mosheiov等[7]研究了所有工件都有共同学习率的极小化最大误工工件数问题。Bachman等[8]研究了2种学习曲线模型,即线性模型与多项式模型,并给出了一些性质,还对以前的成果进行了总结。Wang等[9]研究了具有学习效应的流水作业排序问题,对目标函数分别为最大完工时间与完工时间和问题分别给出了近似算法,并分析了最坏情况界。Wang[10]针对文献[9]中同样的问题,提出了把经典的Johnson规则作为一个启发式算法来解决2台机器的最大完工时间问题。他也对极小化加权总完工时间与最大延误问题的几种多项式时间可解的特殊情况进行了讨论。Wang等[11]进一步研究了具有一般性学习效应的单机排序问题,证明了最大完工时间问题与完工时间和问题都是多项式时间可解的,还证明了几类多目标排序问题也是多项式时间可解的。Chen等[12]研究了具有学习效应的流水作业排序问题,其中,目标函数为总完工时间与最大延误的加权和的双目标函数。他们对此问题给出了一些性质和算法。Wang[13]研究了工件同时具有学习效应与恶化效应的单机与流水作业排序问...