期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

匹配算法在带链优先约束的分批排序中的应用

下载PDF
导出
摘要 本文首次就带有链优先序的分批排序问题进行了讨论.优先约束是:包含有n个工件的一条链,另外有m个孤立点工件(即工件之间无任何优先约束).根据B与m的大小关系,分别讨论了它们的最优算法.优先约束为:工件之间有m条链T1,…,Tm,并且每条链是满足一致的.则对于B=2的情形,我们把这一问题多项式转化成了组合最优化中求解非二部图赋权匹配问题,并相应地提出了一个运算次数为O(n4)的多项式算法.
作者 邹娟
机构地区 曲阜师范大学数学科学学院
出处 《赤峰学院学报（自然科学版）》 2008年第7期6-10,共5页 Journal of Chifeng University(Natural Science Edition)
关键词 排序 批处理机 链优先约束 算法复杂性
分类号 O223 [理学—运筹学与控制论]
  • 相关文献

参考文献1

二级参考文献7

  • 1P.Brucker, A.Gladky, C.N.Potts, H.Hoogeveen, M.Y.Kovalyov, T.Tartenhahn, S.L.Van Ce Velde. Scheduling a batching machine. Journal of Scheduling, 1998, 1: 31-57.
  • 2C.N.Potts, M.Y.Kovalyov. Scheduling with batching: A review. European Joural of Operational Research, 2000, 120: 228-249.
  • 3Xiaotie Deng, Yuzhong Zhang. Approximation algorithms in batch processing. Journal of Combinatorial Optimization, 2003, 7: 247-257.
  • 4J.Du, J.Y.-T.Leung, G.H.Young. Scheduling chain-structured tasks to minimize makespan and mean flow time. Information and Computation, 1991, 92: 219-236.
  • 5W.Kubiak, B.Penz, D.Trystram. Scheduling chains on uniform processors with communication delays. Journal of Scheduling, 2002, 5: 459-476.
  • 6P.Brucker, J.Hurink, W.Kubiak. Scheduling identical jobs with chain precedence constraints on two uniform machines. Mathematical Methods of Operations Research, 1999, 49: 211-219.
  • 7Papadimitrion C.H, Steiglitz K. Combinatorial Optimization: Algorithms and Complexity.New Jersey: Prentice-Hall Inc, 1982, 298.

共引文献5

赤峰学院学报（自然科学版）
2008年 第7期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部