含有维护的单机与平行机调度问题研究

《含有维护的单机与平行机调度问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、研究生毕业论文（全日制学术型硕士申请学位）论文题目含有维护的单机与平行机调度问题研究学位申请人王宇盛专业方向运筹学与控制论研究方向调度指导教师徐德华副教授2016年6月20日ResearchonsinglemachineandparallelmachineschedulingproblemswithmachinemaintenancerequirementsDissertationsubmittedtoEastChinaUniversityofTechnologyInFulfillmentoftheRequirementFortheDeg

2、reeofMasterofScienceMasterCandidate:YushengWangMajor:OperationalResearchandCyberneticsStudyOrientation:SchedulingDissertationSupervisor:DehuaXuJune,2016Nanchang,P.R.China学位论文独创性声明：本人所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工作的同事对

3、本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。如不实，本人负全部责任。论文作者（签名）：年月日关于论文使用授权的说明本学位论文作者完全了解东华理工大学有关保留、使用学位论文的规定：东华理工大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。作者签名：导师签名：日期：年月日摘要毕业论文题目：含有维护的单机与平行机

4、调度问题研究运筹学与控制论专业2013级硕士生姓名：王宇盛指导教师（姓名、职称）：徐德华副教授摘要调度问题是一类资源优化配置问题，它广泛应用于工程、计算机和管理等诸多领域，尤其在制造业和服务业中扮演着重要的角色。在当前的竞争环境中，科学合理的调度不仅可以帮助企业充分利用已有的资源，还可以提高企业的生产率，进而为企业在市场竞争中占有有利地位提供强有力的技术支持。近年来，对调度问题的研究越来越多，新模型也不断涌现。其中含有维护的调度问题已成为调度领域里的一个研究热点。本文主要研究了两个含有维护的调度问题。第一个问题是维护时长依赖于机器负载和机

5、器空闲的单机调度问题。我们考虑了一个含有单次维护的单机调度问题，其中工件不可中断，维护的开始时刻给定但维护时长是维护之前机器负载和机器空闲时长的线性增函数，目标是最小化时间表长。我们分三种情况进行讨论，对前两种情况分别给出了一个多项式时间最优算法，对最后一种情况分析了经典的LPT算法的性能并给出了通过经典背包问题的任意一个FPTAS来获得该情况的一个FPTAS的方法。第二个问题是含有特殊工件和机器维护的混合型平行机调度问题。我们考虑了两台机器的情况，其中一台机器需要周期维护，另一台需要工具更换维护。工件包含特殊工件和普通工件，特殊工件只能

6、在周期维护的机器上加工。工件不可中断。目标是最小化时间表长。我们基于LPT算法提出了启发式算法LPTS算法，并给出了最优调度方案的一个下界。数值实验表明，LPTS算法的平均误差小于10%。关键词：调度，维护，时间表长，特殊工件，算法设计与分析IABSTRACTTHESIS：ResearchonsinglemachineandparallelmachineschedulingproblemswithmachinemaintenancerequirementsSPECIALIZATION:OperationalResearchandCyber

7、neticsPOSTGRADUATE:YushengWangMENTOR:DehuaXuABSTRACTSchedulingproblemsareatypeofresourceoptimalconfigurationproblems.Theyarewidelyusedinthefieldsofengineering,computers,management,andsoon.Particularly,theyplayimportantrolesinmanufacturingindustryandserviceindustry.Inthecu

8、rrentcompetingenvironment,scientificandreasonableschedulescannotonlyhelpcompaniesusetheirresourc