兰州大学机构库 >数学与统计学院
一类排序问题的近似算法
Alternative TitleApproximation 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 AbstractScheduling 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学位论文
Identifierhttps://ir.lzu.edu.cn/handle/262010/224467
Collection数学与统计学院
Recommended Citation
GB/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.
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.