具有指数和位置学习效应的机器排序问题

《具有指数和位置学习效应的机器排序问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第20卷第2期2011年4月运筹与管理OPERATl0NSRESEARCHANDMANACEMENTSCIENCEV01．20，No．2Apr．2011具有指数和位置学习效应的机器排序问题张新功1’3，严广乐1，唐国春2，唐海波1(1．上海理工大学管理学院上海200093；2．上海第-'I业大学管理工程研究所。上海201209；3．重庆师范大学数学学院，重庆400047)摘要：本文考虑指数学习效应和位置学习效应同时发生的新的排序模型。工件的实际／j口-r时间不仅依赖于已经加工过工件正常加工时间之和的指数函数，而且依赖于该工件所在的位置。单机排序情形下，对于最大

2、完工时间和总完工时间最小化问题给出多项式时间算法。此外某些特殊情况下，总权完工时间和最大延迟最小化问题也给出了多项时间算法。流水机排序情形，对最大完工时间和总完工时间最小化问题在某些特殊情形下给出多项时间算法。关键词：排序；单机排序；流水机排序；学习效应中图分类号：0223文章标识码：A文章编号：1007—3221(2011)02-0097—05SomeSchedulingProblemsWithPosition．basedExponentialTime-dependentandLearningEffectZHANGXin．gon91，YANGuang．1e1

3、，TANGGuo．chun2，TANGHai．b01(1．BusinessSchool，UniversityofShanghaiforScienceandTechnology，Shanghai200093，China；2．ManagementEngineerInstitute，ShanghaiSecondpolytechnicUniversity，Shanghai201209，China；3．CollegeofMathematicsSci-ence，ChongqingNormalUniversity，Chongqing400047，China)Abstract

4、：Inthispaper，weintroduceanewschedulingmodelinwhichbothexponentialtime—dependentlearningeffectandposition—basedlearningeffectexistsimultaneously．Theactualprocessingtimeofajobdependsnoton—lyonanexponentfunctionofthetotalnormalprocessingtimeofthealreadyprocessedjobsbutalsoonitssehed·ul

5、edposition．Forthesingle—machinecase。wederivepolynomial—timeoptimalsolutionsfortheproblemstomini—mizemakespanandthetotalcompletiontime．Inaddition，Wealsoshowthatthetotalweightedcompletiontimeproblemandthemaximumlatenessproblemcanbesolvedinpolynomialtimeundercertainconditions．Forthecas

6、eofm—machinepermutationflowshop．wepresentpolynomial-timeoptimalforsomespecialcasesoftheprob-lemstominimizemakespanandthetotalcompletiontime．Keywords：scheduling；single—machine；flowshop；learningeffect0引言在经典的排序问题中，工件的加工时间通常认为是一个常数。然而在一些实际的生产过程中并非如此，事实上重复加工相同或相似的工件或操作进程会提高工件的加工速度，从而减少工件

7、的加工时间，这个现象被Pinedo⋯称为学习效应。Biskup‘21研究了工件的加工时间是其位置递减函数的单机排序问题，讨论目标函数是共同工期偏差和总完工时间问题，证明两个问题是多项式时间可解的。利用相似的方法，收稿日期：2009．11-07基金项目：上海市重点学科(S30504)．中港联合科研基金(20710015)．上海市研究生教育创新计划资助(删CXSLl001)作者简介：张新功(1979-)．男，河南项城人．博士研究生．研究方向：组合优化，排序理论。98运筹与管理2011年第20卷Mosheiov"1考虑工件加工时间是其位置递减函数的单机排序问题，利用

8、SPT序规则可以多项式时间内得到最大完