关键词: 资源受限项目调度, 工序网络, 排序, 0-1规划, 项目工期

Abstract: Resource constraints are often broadly impacting, unavoidable impediments in project execution procedures. A number of recent, topical project management issues, such as the resource-constrained project scheduling problem (RCPSP), have their roots in the resource constraint problem. It is NP-hard in the strong sense. Current research on the RCPSP mainly focuses on the global problem in which all activities are constrained by resource constraints during the whole project process. Considering practical projects requiring numerous types of resources, the "resource constrained" designation may be for limited types of resources or during partial project processes. The partial "resource-constrained" designation may constrain activities in a part of the project such that only a portion of activities need arrangement under resource restriction.The above representation denotes the partial RCPSP.In this paper, a typical sub-problem of the partial RCPSP is studied.
The problem statement is the following:In an engineering project, if n unit resources are assigned to complete 2n activities, and each unit resource can complete two activities, it must be determined how to arrange these activities to minimize the lengthening of the project duration. The problem (referred to as the pairing of parallel activities) is popular in practice but very difficult to solve because the number of schemes for it reaches (2n)!/n!.
Characteristics of the deterministic RCPSP are analyzed, and the problem could be represented in another way. First "resource-unconstrained" is assumed and an initial schedule for the project is proposed such as scheduling each activity to start at its earliest start time. Then "resource-constrained" is considered and activities are adjusted to minimum impact on project duration under the resource constraints. In this representation, the scheduling is to sequence initial parallel activities to sequential ones in order to satisfy the resource constraints. The fewer activity overlaps is essential to lower consumption of resources at certain times.Therefore, the RCPSP is particular to sequencing parallel activities, and the fundamental issues include scheduling several parallel activities to one or more activity chains and activity pairs.From the perspective of sequencing, the partial RCPSP aims to adjust only partial parallel activities to sequential ones under the partial "resource-constrained", that is, partial sequencing parallel activities.
A project under finish-to-start-type precedence relations can be represented as a CPM network. The activity time parameters are studied and the problem itself is examined from the angle of the path. The relations between the two are discovered. This discovery is the key to solve the problem. Consequently, the impact of sequencing parallel activities on project duration is indicated only requiring two types of time parameters, thereby the difficulty of the combinatorial optimization problem is considerably reduced.Finally, a 0-1 formulation modelfor the problem is presented, which has competitiveness compared to the usual formulation models.Computational experiments test that 0.2605 (10.66) seconds average is required for disposing 100 (500) parallel activities.
The relations between activity time parameters and impact on project duration of sequencing parallel activities may help solve other similar types of sequence problems. For example, for a general problem of sequencing n parallel activities as m (m < n) sequential activity chains with a minimal impact on project duration, which is important for productive practice but very difficult to effectively solve,the above relations can be extended for application to these problems, and they may enlighten ideas and theoretical tools to improve existing approaches and design new ones.

Key words: resource-constrained project scheduling, activity network, sequence, 0-1 formulation, project duration