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

不相容工件族的平行批序的一些结果

作　者: 石忠和
导　师: 原晋江
学　校: 郑州大学
专　业: 运筹学与控制论
关键词: 平行批排序不相容工件族加权总完工时间误工个数动态规划
分类号: O223
类　型: 硕士论文
年　份: 2008年
下　载: 1次
引　用: 0次
阅　读: 论文下载

内容摘要

排序就是在一定的约束条件下对工件和机器按时间进行分配和安排加工次序,使一个或多个目标达到最优.平行批排序是发展比较迅速的现代排序模型.工件分族排序则是平行批排序中的新概念.本文主要对于同一族内加工时间等长的不相容工件族平行批排序进行了研究,作了以下两方面的工作:（1）同一族内工件加工时间相同时不相容工件族的平行批加权总完工时间问题;（2）同一族内工件加工时间相同时不相容工件族的误工总数问题.平行批排序是指一台机器可以同时加工多个工件,每批包含的工件同时开工且同时完工,批的加工时间是这批工件中加工时间的最大者.一旦一批工件开始加工就不能被中断,其他工件也不能加入该批.本文中研究的问题可描述如下:有n个工件J₁, J₂,…,J_n,它们被分成m个不同的工件族F₁,F₂,…,F_m.不同族的工件是不能在同一批加工的.工件是成批被加工处理的.这里的一批是指工件的一个子集.这些批（子集）构成了工件集的一个划分.我们称此排序模型为平行批排序问题,记为这里f为Σw_jC_j或ΣU_j.本文的主要结果如下:（1）同一族内加工时间相同的不相容工件族的单机平行批加权总完工时间问题.基于对平行批加权总完工时间问题最优解性质的分析,我们提出了工件分批的最优性质,对同一族内加工时间相同的批容量有界情形和无界情形分别给出了最优排序规则,当工件有常数个到达时间时,我们分别对批容量有界和无界情形提出了两种启发式算法,并给出其算法复杂性.（2）同一族内加工时间相同的不相容工件族的误工总数问题.对r和d一致及p与d一致的情形,文中给出了最优解的一些性质,并分别给出了时间界为0（?）的动态规划算法.当m为固定常数时,此算法是多项式时间的.对同一族内工件的工期相同时的特殊情形,给出了一种拟多项式时间算法.

全文目录

摘要  4-6
Abstract  6-9
第一章引言  9-20
  1.1 排序的介绍  9-14
  1.2 平行批排序问题  14-16
  1.3 排序的记号  16-18
  1.4 已知结果及本文主要结果  18-20
第二章同一族内加工时间相同时不相容工件族的平行批加权总完工时间问题  20-30
  2.1 相关介绍  20-21
  2.2 到达时间相同时的情形  21-27
  2.3 k个到达时间的情形  27-30
第三章不相容工件族的分批排序的误工总数问题  30-41
  3.1 预备知识  30-31
  3.2 r和d一致时的情形  31-37
  3.3 p和d一致时的情形  37-41
参考文献  41-44
致谢  44

不相容工件族的平行批序的一些结果

内容摘要

全文目录

相似论文