机器带不可用约束和任务带运输时间的排序 Alternative Title Scheduling 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 Abstract In 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 学位论文 Identifier https://ir.lzu.edu.cn/handle/262010/225268 Collection 数学与统计学院 Recommended CitationGB/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.