一类排序问题的近似算法 Alternative Title Approximation Algorithum of a Scheduling Problems 贺玉鉴 Thesis Advisor 王海明 2015-05-12 Degree Grantor 兰州大学 Place of Conferral 兰州 Degree Name 学士 Keyword 排序问题 最大延误 分枝定界法 近似算法 Abstract 排序是一类重要的组合最优化问题，广泛应用于管理科学，计算机科学和工程技术等很多领域。本文主要研究任务具有不同准备时间，加工过程不能被中断的单机排序问题 ，这是一类最大延误问题，与任务的工期有关，本文通过利用分枝定界法对问题给出了算法。 第一章我们简要介绍了排序问题的三参表示法和分类，以及我们所要重点研究的单击排序问题中的最大延误问题。 第二章对没有准备时间的最大延误问题 给出EDD法则，然后研究有不同准备时间，加工过程可以中断的问题，根据EDD规则给出最优多项式算法。最后，我们在前两种问题的基础上提出出问题（2.3）的一种近似算法——分枝定界法。 第三章我们对问题（2.3）的分枝定界算法进行算法设计，并对其证明得到最优排序，举例实现。 Other Abstract Scheduling problem is a kind of important combinatorial optimization problem, which are widely used in management science, computer science and engineering technology and so on many fields. This article mainly research scheduling on a single machine with different release time and the processing cannot be interrupted .It can be represented by 1 .This is a kind of maximum lateness minimization problem which associated with the due date of tasks, we solve the problem with the branch and bound method in this article. In the first chapter, we briefly introduced the three representation and classification of the scheduling problem, and we focus on the single machine maximum lateness minimization problem. In the second chapter, firstly, giving the EDD rule for a single machine maximum lateness minimization problem without release time . Secondly, research the scheduling on a single machine with different release time and the processing can be interrupted which can be represented by 1 , we can obtain the optimal polynomial algorithm according to the rules of EDD. Finally, on the base of the first two questions we give a kind of approximate algorithm -- branch and bound method for problem(2.3). The third chapter we design algorithm for the branch and bound algorithm of the problem (2.3) and prove it, giving a example for it. URL 查看原文 Language 中文 Document Type 学位论文 Identifier https://ir.lzu.edu.cn/handle/262010/224467 Collection 数学与统计学院 Recommended CitationGB/T 7714 贺玉鉴. 一类排序问题的近似算法[D]. 兰州. 兰州大学,2015.
 Files in This Item: There are no files associated with this item.
 Related Services Recommend this item Bookmark Usage statistics Export to Endnote Altmetrics Score Google Scholar Similar articles in Google Scholar [贺玉鉴]'s Articles Baidu academic Similar articles in Baidu academic [贺玉鉴]'s Articles Bing Scholar Similar articles in Bing Scholar [贺玉鉴]'s Articles Terms of Use No data! Social Bookmark/Share
No comment.