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.
杨启帆. 单位加工时间入树约束Open Shop 问题的多项式时间算法[J]. 浙江大学学报（理学版）, 1999, 26(4): 46-49.
YANG Qi-fan . A Polynomial Algorithm for the Open Shop Problem with Unit Processing Times and Intree Constraints. Journal of ZheJIang University(Science Edition), 1999, 26(4): 46-49.