| 单位加工时间入树约束Open Shop 问题的多项式时间算法 |
| |
| 引用本文： | 杨启帆. 单位加工时间入树约束Open Shop 问题的多项式时间算法[J]. 浙江大学学报(理学版), 1999, 26(4): 46-49 |
| |
| 作者姓名： | 杨启帆 |
| |
| 作者单位： | |
| |
| 摘 要： | 本文研究具有单位加工时间及入树约束的Open Shop问题，提出了一个多项式时间算法，该算法根据入树约束的层次结构分批安排加工，使每批加工解除约束的工件数最多。文章证明，算法的计算量为O(n2)。
|
| 关 键 词： | 自由作业车间 入树 多项式时间算法 |
| 收稿时间： | 1998-10-25 |
A Polynomial Algorithm for the Open Shop Problem with Unit Processing Times and Intree Constraints |
| |
| YANG Qi-fan. A Polynomial Algorithm for the Open Shop Problem with Unit Processing Times and Intree Constraints[J]. Journal of Zhejiang University(Sciences Edition), 1999, 26(4): 46-49 |
| |
| Authors: | YANG Qi-fan |
| |
| Affiliation: | Dept. of Applied Mathematics, Zhejiang Univ., Hangzhou 310027,China |
| |
| Abstract: | This paper proposes the problem O/Pij=1, intree/∑Ci where Ci is the completion time of job Ji. The complexity of this problem was open. A polynomial algorithm which decomposes the jobs into layers according to the intree structure and assigns them to be processed layer by layer is presented. |
| |
| Keywords: | open shop problem intree,unit processing times,polynomial algorithm, |
| 本文献已被 维普 万方数据 等数据库收录！ |
| 点击此处可从《浙江大学学报(理学版)》浏览原始摘要信息 |
|
点击此处可从《浙江大学学报(理学版)》下载全文 |
