Please wait a minute...
浙江大学学报（理学版）
浙江大学学报（理学版）
数学与计算机科学     
单位加工时间入树约束Open Shop 问题的多项式时间算法
浙江大学玉泉校区数学系，浙江 杭州 310027
A Polynomial Algorithm for the Open Shop Problem with Unit Processing Times and Intree Constraints
Dept. of Applied Mathematics, Zhejiang Univ., Hangzhou 310027,China
 全文: PDF(48 KB)  
摘要： 本文研究具有单位加工时间及入树约束的Open Shop问题，提出了一个多项式时间算法，该算法根据入树约束的层次结构分批安排加工，使每批加工解除约束的工件数最多。文章证明，算法的计算量为O(n2)。
关键词： 自由作业车间;  入树;  多项式时间算法     
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.
Key words: open shop problem;intree    unit processing times    polynomial algorithm
收稿日期: 1998-10-25 出版日期: 2017-11-10
CLC:  O212  
作者简介: 杨启帆，(1944-)，男，浙江杭州人，浙江大学副教授，从事组合优化研究。
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
杨启帆

引用本文:

杨启帆. 单位加工时间入树约束Open Shop 问题的多项式时间算法[J]. 浙江大学学报（理学版）, .

YANG Qi-fan . A Polynomial Algorithm for the Open Shop Problem with Unit Processing Times and Intree Constraints. Journal of Zhejiang University (Science Edition), .

链接本文:

https://www.zjujournals.com/sci/CN/    或    https://www.zjujournals.com/sci/CN/Y1999/V26/I4/46

[1] 潘水洋, 刘俊玮, 王一鸣. 基于神经网络的股票收益率预测研究[J]. 浙江大学学报（理学版）, 2019, 46(5): 550-555.
[2] 傅可昂, 丁丽, 李婷, 陈豪, 何文凯. GRCA(1)模型中误差方差自加权估计的渐近分布[J]. 浙江大学学报（理学版）, 2019, 46(4): 416-421.
[3] 赵　霞　周观珍. 随机删失场合基于 Synthetic Data 的回归 函数核估计的强相合性 [J]. 浙江大学学报（理学版）, 1998, 25(4): 1-6.
[4] 徐明民　晏晓林　于朝江 . 多人有误检查的参数估计 [J]. 浙江大学学报（理学版）, 1998, 25(4): 28-34.
[5] 沈杭燕　唐新硕 . TiO2 粉末催化剂光催化降解室内 空气中有机污染物 [J]. 浙江大学学报（理学版）, 1998, 25(4): 55-58.
[6] 潘建敏，张　奕. NA 序列回归函数核估计的强相合性[J]. 浙江大学学报（理学版）, 1998, 25(3): 32-37.
[7] 欧阳资生. 固定设计下权函数估计的相合性[J]. 浙江大学学报（理学版）, 1998, 25(2): 1-7.
[8] 徐明民,晏晓林. 三参数威布尔分布有替换定时截尾试验的极大似然估计[J]. 浙江大学学报（理学版）, 1998, 25(2): 24-29.
[9] 潘建敏. 随机删失场合半参数回归模型参数估计的重对数律‘[J]. 浙江大学学报（理学版）, 1997, 24(2): 108-114.
[10] 王洪春. N A随机变量的指数不等式和一个强大数律 [J]. 浙江大学学报（理学版）, 2000, 27(1): 20-25.
[11] 郑海应鸟 1,黄柏琴2 . 矩阵损失下多维几何分布均值 的线性估计可容许性 [J]. 浙江大学学报（理学版）, 2000, 27(2): 171-174.
[12] 张子方，徐明民. 双因素不完全配对模型和分离聚类法[J]. 浙江大学学报（理学版）, 1999, 26(2): 19-24.
[13] 徐明民，于朝江. 服从正态分布的强度变量在多个独立应力作用下的结构可靠性估计[J]. 浙江大学学报（理学版）, 1999, 26(1): 36-41.