具有相容约束条件的单机平行分批排序问题

论文摘要

平行分批排序问题是排序问题的重要组成部分。本论文主要考虑的是在工件具有相容性约束条件下工件如何分批排序而使问题的目标函数达到最小。这里的目标函数主要是最大完工时间,也略微考虑了完工时间和的情形,而且完工时间和在这里分批的完工时间和与工件的完工时间和两种情形。工件的相容性约束的二元关系可以通过一个图来描述,也就是说,我们把工件集看作是图的顶点集合,而图的边集合是通过工件间的关系来体现:如果两个工件有相容关系,则就在这两个顶点工件间连条边。这样在相容约束条件下的分批问题就转化为图的团问题。当我们把图限制为不同的特殊图类时,就对应了不同情况下的排序问题。具体说来,给定n个工件J1,J2,…,Jn,这些工件间有的工件是可以在一个批中同时加工,而有的则不能在同一个批中加工。我们把这些工件分别对应与图G中不同的顶点,如果工件是相容的,则对应于图C中对应的顶点间就可以连边,否则就不连边。通过这一转换,我们就把工件的相容性约束通过图论中具体的团问题来刻画,从而使解决相容性约束条件下的排序问题显得更加具体直观。既然相容性约束条件可以用图类刻画,不同的约束条件对应于不同的图类,那我们就把考虑的模型记为 1|p-batch;C|f 其中,图G就是代表我们所讨论的工件相容性条件,用一个简单图来表示;而f是指排序问题的正则目标函数。本论文主要就以下方面的问题进行了研究: 1.目标函数是最大完工时间情形,即 1|p-batch;G|Cmax在这一部分,当图G是一般图时,我们给出了排序问题是NP-困难问题的证明;并且当把图限定为一些特殊图的情况下,我们试图找出排序问题的好的算法。具体说来,当图G是一般二部图、完全二部图、完全m部图、直

论文目录

• 第一章 概论
• §1.1 排序论学科的发展概况
• §1.2 问题的提出
• 第二章 目标函数为最大完工时间的一些结果
• §2.1 预备知识
• §2.2 NP完全性证明
• §2.3 一般二部图的情形
• §2.4 完全二部图的情形
• §2.5 完全m部图的情形
• §2.6 直径不超过4的树的情形
• §2.7 分裂图的情形
• 第三章 目标函数为完工时间和的一些结果
• §3.1 预备知识
• §3.2 批的完工时间和的情形
• 后记 进一步的研究
• 致谢
• 参考文献