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

一类平行机和批处理机组成的二阶段柔性流水作业问题

作　者: 何龙敏
导　师: 孙世杰
学　校: 上海大学
专　业: 运筹学与控制论
关键词: 排序 柔性流水作业 复杂性 算法 性能比
分类号: O223
类　型: 博士论文
年　份: 2006年
下　载: 119次
引　用: 0次
阅　读: 论文下载
 

内容摘要


本文考虑m台同型机（专用机）与一台批处理机组成的二阶段柔性流水作业问题。全文分六章： 第一章简述排序与复杂性理论，介绍FSMP（Flow Shop with Multiple Processors）型问题F2‖f和BI（Burn In）型问题1|BI|f的各自研究成果，进而引出本文所研究的F2（·．·）|BI|Cmax型问题、记号及其结论（参考1．3节的表1．1～表1．4）等。 第二章讨论阶段1由m台同型机组成、阶段2仅有一台批处理机M的极小化最大完工时间(Cmax)的流水作业问题。其中，相应工件Jj在阶段1加工时间aj三a（j∈N={1，2，…，n}）的情况在max{O（n log n），O（nB）}时间内获最优解；相应工件Jj在阶段2加工时间bj≡b（j∈N）的情况，除b≥an（a1≤a2≤…≤an）和B≤m＜n时可在O（n log n）时间内获最优解外，对其余情况及一般情况（aj（?）a和bj（?）b（j∈N））均指出或证得为（强）NP-hard的，并给出各自对应情况的近似算法及其性能比分析（参考1．3节的表1．1）。 第三章讨论阶段1由m台专用机组成、阶段2仅有一台批处理机M并以Cmax为目标函数的流水作业问题。其中，相应工件Jij在阶段2加工时间bij≡b（i=1，2，…，m；j=1，2，…，ni）的情况在多项式时间内获最优解；对一般情况(aij（?）a和bij（?）b（i=1、2，…，m；j=1，2，…，ni）)给出其强NP-hard性、近似算法及其性能比分析（参考1．3节的表1．2）。 第四（五）章讨论第二（三）章的对称情况。即：原第二（三）章阶段1的m台同型机（专用机）改为一台批处理机M，而阶段2的一台批处理机M改为m台同型机（专用机），其余假设同第二（三）章（参考1．3节的表1．3和表1．4）。 第六章在总结的基础上指出拟进一步可讨论研究的内容。

全文目录


答辩委员会签名  2-3
原创性声明、本论文使用授权说明  3-4
学位论文题目  4-5
学位论文题目(英文)  5-6
摘要、关键词  6-7
Abstract,Key words  7-9
目录  9-12
第一章 引言  12-28
  1.1 排序问题及复杂性理论简介  12-16
    1.1.1 排序  12-14
      1.1.1.1 排序问题  12-13
      1.1.1.2 排序类型  13
      1.1.1.3 排序问题的简短发展史  13-14
    1.1.2 复杂性理论简介  14-16
      1.1.2.1 复杂性  14-15
      1.1.2.2 复杂性与排序  15-16
  1.2 本文所研究的问题  16-23
    1.2.1 背景和综述  16-20
      1.2.1.1 FSMP问题  16-18
      1.2.1.2 BI问题  18-20
    1.2.2 本文所研究的问题  20-21
    1.2.3 复杂性  21-23
    1.2.4 记号和定义  23
  1.3 本文所获得的结论  23-28
第二章 问题F2(m,B)|unfixed,BI|C_(max)  28-78
  2.1 问题F2(m,B)|unfixed,BI,a_j≡a|C_(max)的最优算法  28-31
  2.2 问题F2(m,B)|unfixed,BI,b_j≡b|C_(max)  31-56
    2.2.1 b≤a_1,m≤B＜n  38-40
    2.2.2 b≤a_1,B＜m＜n  40-42
    2.2.3 b≤a_1,B≥n  42-44
    2.2.4 b≥a_n,m＜B＜n  44-47
    2.2.5 b≥a_n,B≤m＜n  47
    2.2.6 b≥a_n,B≥n  47-48
    2.2.7 a_1≤b≤a_n,m=B＜n  48-51
    2.2.8 a_1≤b≤a_n,m＜B＜n  51-54
    2.2.9 a_1≤b≤a_n,B＜m＜n  54-56
    2.2.10 a_1≤b≤a_n,B≥n  56
  2.3 问题F2(m,B)|unfixed,BI|C_(max)  56-78
    2.3.1 m=B=2  56-73
    2.3.2 max{m,B}＜n  73-76
    2.3.3 B≥n  76-78
第三章 问题F2(m,B)|fixed,BI|C_(max)  78-86
  3.1 问题F2(m,B)|fixed,BI,b_(ij)≡b|C_(max)的最优算法  78-82
    3.1.1 b_(ij)≡b,B≥n  78
    3.1.2 b_(ij)≡b,B＜n  78-82
  3.2 问题F2(m,B)|fixed,BI|C_(max)  82-86
    3.2.1 算法  83-84
    3.2.2 定理  84-86
第四章 问题F2(B,m)|BI,unfixed|C_(max)  86-106
  4.1 问题F2(B,m)|BI,unfixed|C_(max)的对称模型及其性质  86-87
  4.2 问题F2(B,m)|BI,unfixed,a_j≡a|C_(max)的最优算法  87-88
  4.3 问题F2(B,m)|BI,unfixed,b_j≡b|C_(max)  88-99
    4.3.1 b≤a_1,m≤B＜n  89-90
    4.3.2 b≤a_1,B＜m＜n  90-93
    4.3.3 b≤a_1,B≥n  93-94
    4.3.4 b≥a_n,m＜B＜n  94-95
    4.3.5 b≥a_n,B≤m＜n  95-97
    4.3.6 b≥a_n,B≥n  97-98
    4.3.7 a_1≤b≤a_n,max{m,B}＜n  98
    4.3.8 a_1≤b≤a_n,B≥n  98-99
  4.4 问题F2(B,m)|BI,unfixed|C_(max)  99-106
    4.4.1 m=B=2  99-102
    4.4.2 max{m,B}＜n  102-104
    4.4.3 B≥n  104-106
第五章 问题F2(B,m)|BI,fixed|C_(max)  106-111
  5.1 问题F2(B,m)|BI,fixed,b_(ij)≡b|C_(max)的最优算法  106-107
    5.1.1 算法  106
    5.1.2 定理  106-107
  5.2 问题F2(B,m)|BI,fixed|C_(max)  107-111
    5.2.1 算法  107-109
    5.2.2 定理  109-111
第六章 总结与讨论  111-113
参考文献  113-119
作者在攻读博士学位期间公开发表及完成的论文  119-120
致谢  120

相似论文

  1. 基于差分进化算法的JSP环境下成套订单研究,F273
  2. 基于图的标志SNP位点选择算法研究,Q78
  3. 高灵敏度GNSS软件接收机的同步技术研究与实现,P228.4
  4. 天然气脱酸性气体过程中物性研究及数据处理,TE644
  5. 基于Thermo-Calc三元共晶合金凝固路径的耦合计算,TG111.4
  6. 压气机优化平台建立与跨音速压气机气动优化设计,TH45
  7. 多导弹协同作战突防效能评估及组合优化算法研究,TJ760.1
  8. 基于感性负载的车身网络控制系统,U463.6
  9. 基于蚁群算法的电梯群优化控制研究,TU857
  10. 高精度激光跟踪装置闭环控制若干关键问题研究,TN249
  11. 半导体激光器热电控制技术研究,TN248.4
  12. AES算法及其DSP实现,TN918.1
  13. 基于UWB脉冲信号的测距定位技术,TN929.5
  14. 基于TS101的DFT输出子集算法研究及软件实现,TN911.72
  15. 高光谱图像空—谱协同超分辨处理研究,TN911.73
  16. DBF接收机用于二维测向算法的研究,TN851
  17. 电视制导系统中视频图像压缩优化设计及实现研究,TN919.81
  18. IEEE802.16e信道编译码算法研究,TN911.22
  19. LDPC码译码算法的研究,TN911.22
  20. 频繁图结构并行挖掘算法的研究与实现,TP311.13
  21. 基于人眼检测的驾驶员疲劳状态识别技术,TP391.41

中图分类: > 数理科学和化学 > 数学 > 运筹学 > 统筹方法
© 2012 www.xueweilunwen.com