| 一类工件带有优先约束的分批排序问题 |
| |
| 引用本文： | 乔梓.一类工件带有优先约束的分批排序问题[J].枣庄师专学报,2009,26(2):33-36. |
| |
| 作者姓名： | 乔梓 |
| |
| 作者单位： | 曲阜师范大学运筹与管理学院日照广播电视大学财经系,山东,日照,276800
|
| |
| 基金项目： | 国家自然科学基金，山东省自然科学基金 |
| |
| 摘 要： | 本文对工件带有“扩充链”优先约束的分批排序问题进行了研究，其目标函数为最大完工时间．优先约束为：在一个扩充链上包含有n个工件，另外有m个孤立点工件（即工件之间无任何优先约束）．讨论了时问题的最优算法，把这一问题多项式转化成了组合优化中求解非二部图赋权匹配问题，并相应地给出了一个运算次数为的多项式算法．
|
| 关 键 词： | 排序 批处理机 扩充链 算法复杂性 |
A Kind of Batching Schedule Problem with Chain Precedence Constraints |
| |
| QIAO Zi.A Kind of Batching Schedule Problem with Chain Precedence Constraints[J].Journal of Zaozhuang Teachers' College,2009,26(2):33-36. |
| |
| Authors: | QIAO Zi |
| |
| Institution: | QIAO Zi (1. College of Operations Researth and Management Science,Qufu Normal University;2. Finance and Economics Department , Rizhao Radio and TV University, Rizhao 276826, China) |
| |
| Abstract: | The problem of scheduling jobs with chain precedence constraints is considered. The target function is minimizing the makespan. Precedence constraints include： there are one chains of extension with n jobs in it, and m isolated jobs （ i e： there are no precedence constraints among the m jobs ）, where m is an arbitrary number. There are a number of interesting special cases which can be solved in polynomial time. We discuss the problem of B = 2. |
| |
| Keywords: | schedule batching machine chain of extension the complexity of algorithm |
| 本文献已被 维普 万方数据 等数据库收录！ |
