兰州大学机构库 >数学与统计学院
机器带不可用约束和任务带运输时间的排序
Alternative TitleScheduling with Machine has Non-availability Constraint and Jobs has Delivery Times
陈伯龙
Thesis Advisor王海明
2009-06-02
Degree Grantor兰州大学
Place of Conferral兰州
Degree Name硕士
Keyword不可用约束 运输时间 最坏例子比 近似算法 动态规划 混合整数规划
Abstract本文考虑了机器带有一个已知的固定的不可用约束区间,任务的加工是不可中断的机器排序问题, 同时任务带有一个运输时间,在其加工完后需要送到客户手中。 首先,我们考虑了两台平行机问题,其中一台机器带有一个固定的不可用约束区间, 而另一台机器是连续可用的,目标函数是最小化最大运输完工时间,该问题是$NP$-难的。我们提出一个$8/5$ 的多项式近似算法,并指 出这个界是紧界, 同时还用动态规划方法和整数规划模型求解该问题。 其次,我们考虑了机器带有一个固定的不可用约束区间的单机排序问题,目标函数是最 小化最大加权运输完工时间。这个问题也是$NP$-难的。我们用动态规划方法和整数规划模型求解该问题。 同时就$q_i=q_o$的特殊情形提出了 最坏例子比为2和1+$\varepsilon$ 的两个多项式近似算法。 最后,我们同样考虑了机器带有一个固定的不可用约束区间的单机排序问题,目标函数是最 小化最大加权总运输完工时间。这个问题同样是$NP$-难的.我们用动态规划方法和整数规划模型求解了该问 题。
Other AbstractIn this paper,we consider the non-resumable case of the machine scheduling problem with a non-availability constraint interval,which is fixed and known in advance .And the job have a delivery time has been delivered to customers after completion. First,we consider the problem of two parallel machines where one has a fixed non-availability constraint interval and the other available all time. the objective is to minimize the time by which all jobs have been delivered.The problem is NP-hard.We propose a polynomial approximation algorithm with a worst-case performance ratio of 8/5, and show that the bound is tight. At the same time we present a dynamic programming method and mixed integer programming model to solve this problem. Secondly,we consider a single-machine problem with an non-availability constraint. The objective is to minimize the largest weighted time by which all jobs have been delivered. this problem is NP-hard too.We solved the problem using dynamic programming method and mixed integer programming model. We also propose two polynomial approximation algorithms under the case of $q_i=q_o$ with a worst-case performance ratio of 2 and 1+$\varepsilon$, respective. Thirdly,we also consider a single-machine problem with an non-availability constraint. The objective is to minimize the weighted sum of time by all jobs have been delivered. this problem is also NP-hard .We solving it with dynamic programming method and mixed integer programming model.
URL查看原文
Language中文
Document Type学位论文
Identifierhttps://ir.lzu.edu.cn/handle/262010/225268
Collection数学与统计学院
Recommended Citation
GB/T 7714
陈伯龙. 机器带不可用约束和任务带运输时间的排序[D]. 兰州. 兰州大学,2009.
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.