| 机器带不可用约束和任务带运输时间的排序 |
| 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 Citation
GB/T 7714 |
陈伯龙. 机器带不可用约束和任务带运输时间的排序[D]. 兰州. 兰州大学,2009.
|
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
