单机上的几类Pareto最优排序问题研究

《单机上的几类Pareto最优排序问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Master’SThesis，ZhengzhouUniversity,No．201112141601ResearchonSeveralKindsofParetoOptimizationSchedulingProblemsonaSingleMachineCandidate"翰anGaoSupervisor：Prof．JinjiangYuanSpeciality：OperationsResearchandCyberneticsSchoolofMathematicsandStatistics，ZhengzhouUniver

2、sityZhengzhou，450001，P．R．ChinaMay,2014原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体己经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体，均己在文中以明确方式标明。本声明的法律责任由本人承担。学位论文作者：高1蜀日期：20Jq，年F月学位论文授权使用声明本人在导师指导下完成的论文及相关的职务作品，知识产权归属郑州大学。根据郑州大学有关保留、使用学位论文的规定，同意学校

3、保留或向国家有关部门或机构送交论文是复印件和电子版，允许论文被查阅和借阅；本人授权郑少l'l大学可以将本学位论文的全部或部分编入有关数据库进行检索，可以采用影印、缩印或者其他复制手段保存论文和汇编本学位论文。本人离校后发表、使用学位论文或与该学位论文直接相关的学术论文或成果时，第一署名单位仍然为郑州大学。保密论文在解密后应遵守此规定。学位论文作者：高园日期：207牛年亨月摘要在经典排序问题中人们主要研究一个目标函数．然而在实际应用中，我们往往需要综合考虑多个性能指标，并在这些性能指标之间进行折衷．此时，最理想的情形就

4、是找出所有的Pareto最优点．生产管理者可以根据这些Pareto最优点制定合理的生产计划．利用三参数法，最小化两个目标函数．，和9的Pareto最优排序问题可表示为1

5、

6、(，'9)．排序丌的目标函数向量记为(，(丌)，9(丌))．若不存在其他排序口使得(，(口)，夕(盯))S(，(丌)，夕(丌))，并且f(a)<，(丌)和9(a)<夕(丌)这两个严格不等式至少有一个成立，则称7r是一个Pareto最优排序，并称(，(丌)，9(霄))是相应于排序丌的Pareto最优点．Pareto最优排序问题的求解目标是找出所有的P

7、areto最优点以及相应于每一个的Pateto最优点的Pareto最优排序．本文分两部分研究单机上两个目标的Pareto最优排序问题．第一部分研究单代理的Pareto最优排序问题．第二部分研究具有两个代理的Pareto最优排序问题．在第二章，我们研究了下述两个单代理的Pareto最优排序问题，并分别给出了多项式时间算法：·工件有位置限制的Pazeto最优排序问题：1l口(如)≤砖I(∑警1q，丘。)，其中盯(以)≤七，表示工件Jj只能在前如个位置进行加工，丘ax表示工件的最大排序费用．·在gdd假设下的Pareto最

8、优排序问题：1gddl(∑警1Tj，Ymax)，其中Cdd表示将孔个给定的工期dl≤d2墨⋯≤d。按照工件的完工顺序分配给工件．在第三章，我们研究了下述三个具有两个代理的Pareto最优排序问题，并分别给出了多项式时间算法：·工件有位置限制的Pareto最优排序问题：1『盯(掣)≤醪，仃(芦)冬七尹l(∑骂@，感0)，其中仃(∥)s硭表示A一工件J2只能在前矽个位置进行加工，盯(蜉)s婷表示B工件即只能在前婷个位置进行加工，．患，表示B-X件的最大排序费用．·在gdd(A)假设下的Pareto最优排序问题：1gdd(

9、A)}(∑驾掣，盘)，其中gaa(A)表示将礼A个给定的工期d1≤d2≤⋯≤dn。按照A工件的完工顺序分配给A工件．·在gdd(B)假设下的Pareto最优排序问题：1lgGd(B)【(∑翟1甜，L忽)，其中gda(S)表示将几B个给定的工期dl≤d2≤⋯≤如。按照口工件的完工顺序分配给B一工件．关键词：两个目标；单代理；两个代理；Pareto最优；工件位置限制；gdd假设；多项式时间AbstractIntheclassicalschedulingproblems，peoplemainlystudyoneobject

10、ivefunction·However，intheDracticalapplications，weusuallyconsidermultipleperformanceindicators：andtaketrade—offbetweenthem．Inthiscane，theidealsituationistofindallParetooDtima