关键词: 项目计划, 时间复杂度, 区间数, 时长变动幅度, 顺序强度

Abstract: In this paper, the model of interval project scheduling problem is described, and a new algorithm to assert activity criticality is introduced, in which criticality of activities is asserted by the combination of polynomial algorithms and path enumeration. With the adoption of this algorithm, a series of hypotheses concerning the relationships among network order strength, activity duration change and other parameters, as well as their integrated impact on computation time are proposed and tested by a series of experiments. The conclusion is that activity duration change and order strength of network have a positive impact on the computation time. In practice project planning, planners must limit the order strength of project network and activity duration change as strictly as possible to finish project planning smoothly.

Key words: project scheduling, time complexity, interval, duration excursion, order strength