单台机器多链时间约束问题的若干新结果(英文)

Some Further Results for One-machine Generalized Precedence Constrained Scheduling Problems

在本文中，我们针对Ｗｉｋｕｍ等人在文［４］中提出的单台机器多链时间 约束问题的若干个公开问题给出了一些新的结果．我们证明了带有延迟时间上界的 ｋ－２－链形结构的排序问题是ＮＰ－困难的，并分别对带有延迟时间上界／下界的 ｋ－（２，１，…，１）－链形结构问题给出了一个拟多项式时间算法．

In this paper, we deal with some open problems for one-machine generalized precedence constrained scheduling problems mentioned in Wikum et al[4]. We prove that the k-2-chains problem with upper bound delays is NP-complete in the strong sense, and propose a pseudo-polynomial algorithm for the k-(2, 1,…, 1)-chains problem with lower/upper bound delays respectively.