带有固定工作和工件运输时间的单机排序问题

带有固定工作和工件运输时间的单机排序问题

论文摘要

排序问题有着深刻的实际背景和广阔的应用前景,一直受到国际学术界的重视。本文主要研究了带有固定工件和工件运输时间的单机排序问题。固定工件是一类特殊的工件,它们的开工时间和完工时间都是预先确定的,在时间轴上占据着一些互不相交的区间。在整个加工过程中,工件不允许中断。每个工件有一个运输时间,我们假定在工件加工完后有足够多的卡车运输。论文共分两章。第一章(概述)主要介绍了排序的背景、发展、基本概念及排序模型的记法。第二章主要讨论了四个排序模型的复杂性、拟多项式时间算法和近似算法。用三参数法表示我们的模型即是:本文主要结果如下:(1)问题1|FB(F),qj|Lmax、1|FB(F)|maxwjGj和1|FB(F)|∑wjCj是NP-困难的,问题1|FB,qj|Lmax是强NP-困难的。(2)问题1|FB(F),qj|Lmax、1|FB(F)|maxwjCj和1FB(F)∑wjCj是拟多项式时间可解的。(3)对于问题1|FB,qj|Lmax给出了最坏性能比为2的近似算法,并证明这是最好可能的多项式时间近似算法;对于问题1|FB(1),qj|Lmax给出了最坏性能比为3/2的多项式时间近似算法;对于问题1|FB(1)|maxwjCj给出了最坏性能比为2的多项式时间近似算法,在为常数的情况下我们得到了PTAS算法。并证明除非P=NP,对于问题1|FB(2)|maxwjCj,不存在常数界的多项式时间近似算法。

论文目录

  • 摘要
  • Abstract
  • 第一章 概述
  • §1.1 排序论介绍
  • §1.2 基本概念
  • §1.3 排序的记号
  • 第二章 带有固定工件和工件运输时间的单机排序问题
  • §2.1 引言
  • §2.2 复杂性
  • §2.3 动态规划算法
  • §2.4 近似算法
  • 后记
  • 参考文献
  • 致谢
  • 相关论文文献

    标签:;  ;  ;  ;  ;  

    带有固定工作和工件运输时间的单机排序问题
    下载Doc文档

    猜你喜欢