学位论文 > 优秀研究生学位论文题录展示

带有拒绝费用的机器排序问题

作　者: 张利齐
导　师: 原晋江
学　校: 郑州大学
专　业: 运筹学与控制论
关键词: 排序拒绝费用平行批 NP-困难的近似算法全多项式时间近似方案
分类号: O223
类　型: 硕士论文
年　份: 2008年
下　载: 33次
引　用: 2次
阅　读: 论文下载

内容摘要

在最近的50年中,机器排序已经成为组合最优化中最重要和最活跃的研究课题之一.在大多数经典的排序文献中,所有的工件都必须安排在机器上加工.也就是说,我们不允许拒绝任何工件.然而,为了获得最大的利润,生产决策者经常会拒绝一些加工时间较长且利润较小的工件.在本文中,我们主要考虑了下面两个带有到达时间和拒绝费用的排序问题.（1）带有到达时间和拒绝费用的单机排序问题带有到达时间和拒绝费用的单机排序问题可以描述如下:有一台机器和n个工件J₁…,J_n.每个工件J_j有一个加工时间p_j和一个拒绝费用w_j.工件J_j或者被拒绝并支付一个确定的拒绝费用w_j;或者被接收并安排在机器上加工.目标是最小化被接收工件的最大完工时间与被拒绝工件的全部拒绝费用之和.我们定义R为所有被拒绝工件的集合。采用Graham等人[12]提出的排序问题的一般记号,这个问题记为1|r_j,reject|C_max+∑₍J_j∈R^w_j.首先,我们证明了这个问题是NP-困难的.其次,对这个问题,我们给出了两个拟多项式时间算法.特别地,当工件有相同的加工时间或者拒绝费用时,由上述拟多项式时间算法,这个问题是多项式时间可解的.最后,我们还给出了一个2-近似算法和一个全多项式时间近似方案.（2）带有到达时间和拒绝费用的无界平行批排序问题带有到达时间和拒绝费用的无界平行批排序问题可以描述如下:有一台机器和n个工件以J₁,…J_n.每个工件J_j有一个加工时间p_j和一个拒绝费用w_j.工件J_j或者被拒绝并支付一个确定的拒绝费用w_j;或者被接收并安排在机器上分批加工.其中每个批的加工时间等于该批中工件的最长加工时间.目标是最小化被接收工件的最大完工时间与被拒绝工件的全部拒绝费用之和.我们定义R为所有被拒绝工件的集合.采用Graham等人[12]提出的排序问题的一般记号,这个问题记为1|p-batch,r_j,reject|C_max+∑_{J_j}∈R^w_j.首先,我们证明了这个问题是NP-困难的.其次,对这个问题,我们给出了一个拟多项式时间算法.特别地,当工件有相同的拒绝费用时,由上述拟多项式时间算法,这个问题是多项式时间可解的.最后,我们还给出了一个2-近似算法和一个全多项式时间近似方案.

全文目录

摘要  3-5
Abstract  5-8
第一章绪论  8-15
  §1.1 排序问题介绍  8-10
  §1.2 排序问题记号  10-11
  §1.3 相关文献综述  11-13
  §1.4 本文主要结果  13-15
第二章带有到达时间和拒绝费用的单机排序问题  15-24
  §2.1 相关介绍  15-16
  §2.2 NP-困难性证明  16-17
  §2.3 动态规划算法  17-21
  §2.4 近似算法  21-24
第三章带有到达时间和拒绝费用的无界平行批排序问题  24-34
  §3.1 相关介绍  24-25
  §3.2 NP-困难性证明  25-28
  §3.3 动态规划算法  28-31
  §3.4 近似算法  31-34
参考文献  34-36
致谢  36

带有拒绝费用的机器排序问题

内容摘要

全文目录

相似论文