资源描述:
《具有学习效应和安装时间的流水作业排序问题》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、具有学习效应和安装时间的排序问题摘要工件排序问题一直是运筹学、系统工程以及自动化管理领域中一个十分活跃的研究课题,同时也是在实际中应用最广的运筹学分支之一,特别是对于在现有资源条件下提高工作效率和经济效益有重要的作用。工件排序是解决按时间的先后,将有限的人力物力资源分配给不同的工作任务,使预定的目标最优或近似最优的问题。首先介绍了排序问题的定义及三参数表示方法,以及具有学习效应的排序问题和具有安装时间的排序问题的研究现状。然后分别对具有学习效应(与工件在排序中的位置有关)的排序问题和同时具有学习效应(与已加工工件的加工时间和工件在排序中的位置有关)和安装时间的排序问题进行了讨
2、论。第二章主要讨论了两台机器流水作业排序问题。首先讨论问题F2
3、LE
4、∑Cj,证明了SPT算法(工件按照工件加工时间的非降排序)的界不超过2。然后讨论了两种特殊情况:情况1:工件在第二台机器上的加工时间相同。情况2:j≤bj,(j=1,2,,n)且当aj≤ak时,bj≤bk,(j,k∈(1,2,,n)),对这两种特殊情况,利用SPT算法得到最有排序。第三章讨论了同时讨论了具有安装时间和学习效应的单机排序问题及流水作业排序问题。安装时间设定为与已加工工件的实际加工时间相关的函数,即p-s-d。学习效应为与已加工工件的加工时间及工件的位置有关的函数。证明了目标函数为极小化最大完工
5、时间和总完工时间的单机排序问题按照SPT规则排列可得到最优排序。同时还讨论了其它目标函数的单机排序问题。并且对流水作业排序问题中的两种特殊情况进行讨论,给出了多项式算法。关键词:排序,单机,流水作业,学习效应,安装时间a,SchedulingproblemwithlearningeffectandsetuptimesAbstractJobschedulingproblemhasalwaysbeenaveryactivefieldinoperationresearch,systemsengineeringandautomatedmanagement,butalsoamostex
6、tensiveoneinpracticalapplicationofoperationresearchbranch.JobSchedulingproblemistoresolvethesequenceofthelimitedhumanandmaterialresourceswhichallocatedtodifferenttasks,sothattheobjectiveofthefunctionwillbebestorapproximatebest.Firstintroducethedefinitionoftheschedulingproblemandthethreepara
7、meters,aswellastheschedulingproblemwithlearningeffectandtheschedulingproblemwithsetting-uptimes.Thenseparatelydiscusstheschedulingproblemwithlearningeffect(relatedtothelocationofthejobinthescheduling)andtheschedulingproblemsimultaneouslywiththelearningeffectandsetuptimes(relatedtotheoperati
8、ontimeoftheprocessedworkandthelocationofthejobinthescheduling).Chaptertwoistodiscussthetwomachineflowshopschedulingwithalearningeffect.Theobjectiveistominimizethetotalcompletiontime.ThisproblemisNP-hard.Accordingtotheanalysisoftheproblem,wefirstproveSPTalgorithmwithworst–caseboundisnomoreth
9、an2.Analysistwospecialcases,forbothofthespecialcases,SPTalgorithmisanoptimalschedule.Chapterthreeisdiscussingthesingle-machineandflowshopschedulingproblemwithsetuptimesandlearningeffectThesetuptimesareproportionaltothelengthofthealreadyprocessedjobs,T.e.