同型机和批处理机组成的三阶段混合流水作业问题

发布时间：2017-09-03 19:04

  本文关键词：同型机和批处理机组成的三阶段混合流水作业问题

  更多相关文章： 排序 混合流水作业 同型机 批处理机 性能比 数值模拟分析

【摘要】：本文讨论一类三阶段流水作业的问题,第一阶段由m台同型机组成,第二阶段和第三阶段均为1台批处理机,目标函数为最小加工全程??maxC.全文分六章:第一章简述排序及其相关的基本概念、本文研究的问题和结论.第二章讨论工件在同型机和两台批处理机上工件的加工时间分别相同情况下,利用已有的动态规划构造了一般情况的??1O n B算法和几类特殊情况的O?n?算法.第三章讨论工件在同型机上具有任意加工时间但在两台批处理机上的加工时间分别相同的情况.其中:复杂性给出除4类情况?2类O?nlogn?2可解,类open?外,其余情况均为NP-hard的结论;对一般情况给出max?O?nlogn?,???1O n B的近似算法H3.1且性能比H 3.1R?2,对13种特殊情况分别给出O?nlogn?的2个最优算法和性能比不超过?2?1 m?的4个近似算法.第四章讨论工件在同型机和第一台批处理机上的加工时间分别相同但在第二台批处理机上具有任意加工时间的情况下,先分3类情况进行讨论(前2类情况为多项式时间可解,第3类情况给出一多项式时间近似算法并进行性能比和数值模拟的分析),然后给出本问题性能比小于等于2的多项式时间近似算法.第五章讨论工件在同型机和第二台批处理机上的加工时间分别相同但在第一台批处理机上具有任意加工时间的情况下,给出两个多项式时间的近似算法并进行性能比和数值模拟的分析.第六章总结了本文所得的结论.
【关键词】：排序 混合流水作业 同型机 批处理机 性能比 数值模拟分析
【学位授予单位】：上海大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：O223
【目录】：

• 摘要6-7
• Abstract7-9
• 第一章 绪论9-19
• §1.1 排序、算法和计算复杂性的简介9-11
• §1.2 本文研究的问题11-16
• §1.3 本文所获得的结论16-19
• 第二章 F3(m,B_1,B_2)|a_j≡a,b_(1j)≡b_1,b_(2j)≡b_2|C_(max)的最优算法19-37
• §2.1 F3(m,B_1,B_2)|a_j≡a,b_(1j)≡b_1,b_(2j)≡b_2|C_(max)的动态规划解法19-26
• §2.2 F3(m,B_1,B_2)|a_j≡a,b_(1j)≡b_1,b_(2j)≡b_2|C_(max)的另一最优算法26-37
• 第三章 F3(m,B_1,B_2)|b_(1j)≡b_1,b_(2j)≡b_2|C_(max)的复杂性、优势序和算法37-62
• §3.1 F3(m,B_1,B_2)|b_(1j)≡b_1,b_(2j)≡b_2|C_(max)的复杂性和优势序37-48
• §3.2 F3(m,B_1,B_2)|b_(1j)≡b_1,b_(2j)≡b_2|C_(max)的算法48-62
• 第四章 F3(m,B_1,B_2)|a_j≡a,b_(1j)≡b_1|C_(max)的优势序和算法62-77
• §4.1 F3(m,B_1,B_2)|a_j≡a,b_(1j)≡b_1|C_(max)的优势序62-69
• §4.2 F3(m,B_1,B_2)|a_j≡a,b_(1j)≡b_1|C_(max)的算法69-77
• 第五章 F3(m,B_1,B_2)|a_j≡a,b_(2j)≡b_2|C_(max)的优势序和算法77-86
• §5.1 F3(m,B_1,B_2)|a_j≡a,b_(2j)≡b_2|C_(max)的优势序77-79
• §5.2 F3(m,B_1,B_2)|a_j≡a,b_(2j)≡b_2|C_(max)的两算法79-86
• 第六章 结论与讨论86-87
• 参考文献87-90
• 作者在攻读硕士期间已投稿的论文90-91
• 致谢91

【参考文献】

中国期刊全文数据库 前2条

1 何龙敏;孙世杰;罗润梓;;带成组加工的二阶段柔性流水作业问题[J];工程数学学报;2008年05期

2 越民义,韩继业;n个零件在m台机床上的加工顺序问题(Ⅰ)[J];中国科学;1975年05期

，

本文编号：786770