柔性Flow shop启发式调度算法的渐近最优分析

摘要

调度问题在柔性制造系统、现代物流、计算机科学等领域中非常重要，但绝大多数调度问题是NP-hard问题，几乎不可能有多项式时间复杂度的最优求解算法，大量研究工作主要集中在近似算法的设计和分析。而调度问题的规模一般较大，分析其近似算法的绝对性能比往往很困难，有时甚至不可行。因此，研究近似算法的渐近性能比就显得很有必要。 对于目标函数为作业加权完成时间和的单机、平行机、flowshop、jobshop调度问题，可以基于加权最短处理时间的启发式算法获得渐近最优解。本论文的目的就是研究这种渐近最优的简单经验规则是否也适合更复杂的调度问题。首先，本论文研究了同速处理机中心的柔性Flowshop加权完成时间调度问题。针对该问题的每个子问题，本文研究了两个基于瓶颈处理机中心的(有效作业)加权最短处理时间的启发式算法，并使用机器模型分组和概率分析方法，证明了它们是渐近最优的。 其次，本论文研究了恒速处理机中心的柔性Flowshop加权完成时间调度问题。针对该问题的每个子问题，本文研究了两个基于瓶颈处理机中心的(有效作业)加权最短处理时间需求的启发式算法，并使用单机松弛和概率分析方法，证明了它们是渐近最优的。 再次，本论文研究了恒速处理机中心的随机柔性Flowshop加权完成时间调度问题。针对这个问题，本文研究了基于瓶颈处理机中心的加权最短期望处理时间需求的启发式策略，并再次使用单机松弛和概率分析方法，证明了该策略是渐近最优的。 最后，在总结全文的基础上，对今后的研究提出了建议和展望。

目录

文摘

英文文摘

第一章绪论

1.1调度问题概念

1.2算法性能比

1.3研究问题

1.3.1同速处理机中心的柔性Flow shop加权完成时间调度问题

1.3.2恒速处理机中心的柔性Flow shop加权完成时间调度问题

1.3.3恒速处理机中心的随机柔性Flow shop加权完成时间调度问题

1.4研究现状

1.4.1确定性调度问题

1.4.2随机性调度问题

1.5本论文的研究动机、研究结果、结构

1.5.1研究动机和结果

1.5.2论文结构

第二章 同速处理机中心的柔性FLOW SHOP加权完成时间调度问题的研究

2.1同速处理机中心的柔性Flow shop调度问题的研究

2.1.1问题模型

2.1.2问题的启发式算法

2.1.3计算举例

2.1.4渐近最优定理及其证明

2.2有作业到达时间的同速处理机中心的柔性Flow shop调度问题的研究

2.2.1问题模型

2.2.2问题的启发式算法

2.2.3渐近最优定理及其证明

2.3同速处理机中心的并行抢占式柔性Flow shop调度问题的研究

2.3.1问题模型

2.3.2渐近最优定理及证明

2.4讨论与拓展

第三章 恒速处理机中心的柔性Flow shop加权完成时间调度问题的研究

3.1恒速处理机中心的柔性Flow shop调度问题的研究

3.1.1问题模型

3.1.2问题的启发式算法

3.1.3计算举例

3.1.4渐近最优定理及证明

3.2作业有到达时间的恒速处理机中心的柔性Flow shop调度问题的研究

3.2.1问题模型

3.2.2问题的启发式算法

3.2.3渐近最优定理及证明

3.3恒速处理机中心的并行抢占式柔性Flow shop调度问题的研究

3.3.1问题模型

3.3.2渐近最优定理及其证明

3.4讨论与拓展

第四章 恒速处理机中心的随机柔性Flow shop 加权完成时间调度问题的研究

4.1恒速处理机中心的随机柔性Flow shop调度问题的研究

4.1.1问题模型

4.1.2随机问题的启发式算法

4.1.3渐近最优定理及证明

4.2讨论与拓展

第五章 结束语

参考文献

致谢

读博期间发表和录用的论文以及参加的研究项目