带装载和卸载的平行机调度问题

《带装载和卸载的平行机调度问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、浙江理工大学硕士专业学位论文带装载和卸载的平行机调度问题摘要本文主要研究带服务器的平行机调度问题，服务器负责装载和卸载的操作。对于带服务器的平行机调度问题一般研究的是服务器负责装载的操作，但随着自动化的全面发展，既然在工件加工之前有安装，相应的再将加工完成之后的工件从机器上卸载下来，这在实际的生产操作中也是一个很值得研究的问题。因此，本文的服务器既要负责装载的操作又要负责卸载的操作，即工件在加工之前先由服务器负责把工件装载到机器上，工件加工完成之后再由服务器把它从机器上卸载下来。由于增加了一个操作，在算法的设计上也增加了一定的难度，因此，本文首先研究带单个服

2、务器的可中断的平行机调度问题；其次，再扩展到带两个服务器的不可中断的平行机调度问题；最后应用经典的LPT算法解决有关配送中心包裹的调度问题。通过比较随机算法R的结果、LPT算法的结果以及最优解值，得出LPT算法可以有效地解决包裹的调度问题。本论文分为五章：在第一章中，主要给出调度问题的相关知识以及有关调度问题算法的设计与分析，通过使用最坏情况界（或竞争比）来衡量一个算法的有效性。并介绍本文所要研究的带服务器的调度问题的相关背景、研究现状以及所要研究的问题。在第二章中，研究只带一个服务器的可中断的平行机调度问题，每个工件在加工之前需要服务器先把它装载到两台机器

3、中的一台上去，在加工完成之后再由该服务器把它从机器上卸载下来。该问题装卸载的时间都是单位时间，目标是极小化最大完工时间。本文设计了一个算法OPA来解决该问题，并且证明该算法是最优算法。在第三章中，研究带两个服务器的平行机调度问题。这里的两个服务器，一个负责在工件加工开始之前把工件装载到机器上，另外一个负责在工件加工完成之后把工件从机器上卸载下来。这一章研究的是不可中断的情况，装卸载时间都是单位时间，目标是极小化最大完工时间。本文使用LS算法和LPT算法求解该问题，并证明它们的最坏情况界分别为8=5和6=5。在第四章中，研究配送中心中有关包裹的调度问题。由于每

4、天进入到配送中心的卡车数量比较多，而卸载点相对较少，如果不能对这些进入卡车进行合理的调度安排，就可能导致整个包裹转移网络的拥堵，从而导致更长的操作时间，所以如何对这些进来的卡车进行调度就显得至关重要。合理的调度能够降低操作费用，提高运输系统的可靠性，并且提升配送中心的竞争力。但往往最优的调度安排很难找到，如果找到一个调度，使得它接近I浙江理工大学硕士专业学位论文带装载和卸载的平行机调度问题最优调度，那么这个调度也是合理的。这节就使用LPT算法尝试解决该问题。通过几个具体的实例，分别使用随机算法R和LPT算法来对这些进入到配送中心的卡车进行调度安排，得到进入卡

5、车的调度和相应的包裹流，再把用随机算法R得到的结果和用LPT算法得到的结果与最优解值进行比较，找到最坏情况界，得出LPT算法可以有效地解决该问题。第五章是对全文的总结以及对未来的展望。关关关键键键词词词：：：调度；算法；最坏情况界；最大完工时间；配送中心；包裹运输II浙江理工大学硕士专业学位论文带装载和卸载的平行机调度问题AbstractInthisthesis,westudytheschedulingprobleminwhichjobsareprocessedontwoidenticalparallelmachinesthatshareserverswhi

6、chloadsandunloadsjobsonthem.Forthiskindofproblem,thegeneralresearchisthattheserveronlychargetheloadingoperation.Butalongwiththedevelopmentofautomation,itisworthyofstudyintheactualproductionoperationthateachjobhastobeloadedbyaserverbeforebeingprocessedonthemachineandunloadimmediatel

7、ybyaserverafteritsprocessing.Duetotheincreaseofoneoperation,itisalsoincreasethedifficultyinalgorithmdesign.So,first,westudyapreemptivevariantwithonlyoneserver.Second,westudyanon-preemptivevariantwithtwoservers.Third,weintroduceapracticalapplication:aschedulingproblemaboutparcelsthatis

8、verycommoninthedistributio