资源受限下平行工序顺序对优化的0-1规划模型

资源受限是工程项目时刻都可能面对的挑战。由于资源限制，需要将原项目计划中相互之间无优先关系的平行工序调整为顺序工序。平行工序顺序化可导致项目工期延迟，因此需考虑如何使项目工期延迟最小。该平行工序顺序优化问题是项目调度问题，也是排列组合问题，通常难度很大，包括一些NP-hard问题。本文主要研究该问题的一类典型子问题——平行工序顺序对优化，即如何将项目中某2n个平行工序调整为n个顺序工序对，并且对项目工期的影响最小。该问题的总方案数可达到（2n）!/n!。本文借助工序网络（如CPM网络），运用简单的时间参数量化了平行工序顺序化对项目工期的影响，进而降低问题的求解难度，建立了纯0-1规划模型。实验验证了该模型的求解效率，求解100个平行工序规模的问题平均耗时0.2605秒，而求解500个平行工序规模的问题平均耗时10.66秒。

0-1 Formulation Model for Optimization of Pairing Parallel Activities under Resource-Constrained

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.