关键词: 资源受限项目调度, 排序优化, 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. The RCPSP is NP-hard in the strong sense， and current research mainly focuses on the global problem in which all activities are constrained by resource constraints during the whole project process. However， following the development of productivity， enlargement of project size， and diversification and complication of resource capacities， etc.， the “local resource-constrained” has been a more significant feature of resource capacities for projects. For example， most time the capacities of common resources could be guaranteed， but the capacities of scarce and expensive resources are constrained and restrict partial related activities requiring them. The recent extensions of RCPSP also reflect the “locality” features of “resource-constrained”， such as reactive RCPSP， RCPSP with resource capacities and requests varying， and multi-RCPSP. However， due to the lack of exploration for the “locality” feature， the computations for the optimal solutions of the above problems are inefficient. In this paper， these RCPSP with the “locality” feature are summarized as local RCPSP， and a typical sub-problem of the local RCPSP is studied， that is， a local RCPSP with “parallel structure” （the activities are parallel to each other）. Many other types of scheduling problems， such as the waterway ship scheduling problem， are also equivalent to RCPSPs with “parallel structure”.First， a new perspective for the deterministic local RCPSP is proposed. 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 “local resource-constrained” is considered and the related activities are adjusted for minimum lengthen of project duration under the resource constraints. In this representation， the scheduling is to sequence the initial n parallel activities as a sequential activity-chain in order to satisfy the resource constraints.Second， the work of exploring the “locality” of the considered local RCPSP is started. The project under finish-to-start-type precedence relations can be represented as a CPM network. The activity time parameters are studied and the considered local RCPSP itself is examined from the angle of the CPM network paths. The relations between the “local scheduling” and the “global optimization” are discovered， which is formulated using activity parameters. This discovery enlightens and helps to draw out the “locality” of the local RCPSP， and the formulations help to compute the project makespan determined by the local scheduling. The formulations are the keys to solving the problem， and result in the considerable reduction of the difficulty of the combinatorial optimization problem.Third， based on the above relations and formulations， 0-1 mixed linear programming models for the local RCPSP are formulated. The models only cover the “local scheduling activities” but could globally optimize the project scheduling problem， therefore have competitiveness compared to the usual formulation models.The competitiveness of the proposed models is evaluated by comparing with current models， and the proposed models are much more competitive to compute tie optimal solutions of medium- and large-size instances. For example， considering instances that arrange 1 renewable resource to execute some 10 parallel activities in a project including 120 activities， computational experiments test that the CPU times for computing the optimal solution using the proposed models and CPLEX solver are over tens of thousands of times faster than the usual models. And furthermore， considering instances that arrange 1 renewable resource to execute some 300 parallel activities in each project including 9000 activities， computational experiments test that the average CPU times for computing the optimal solutions is 236.16 using the proposed models.The works of exploring the “locality” of the local RCPSP， the relations between “local scheduling” and “global optimization”， and the methods of modelling， are foundations to explore more effective algorithms for the larger- or super large-size problem instances. Furthermore， these works， theories， modelling， and algorithms are also helpful to solve other types of local RCPSP， or even the general RCPSP， which can be extended for application to these problems， and may enlighten ideas and theoretical tools to improve current approaches and explore new ones.The problem statement is the following（1） For the project structure， a project constituting of activity-set V=\left\{\mathrm{0,1},\mathrm{2},\dots ,M,M+\mathrm{1}\right\} is represented by a topologically ordered acyclic activity-on-node （AoN） network G=\left(V,A\right)， in which the set A is used to represent the minimum finish-start precedence relations between activities with a time-lag of zero and the set V represents the activities of the project， embodied by the nodes in the graph. The activities are numbered from a dummy start node \left(\mathrm{0}\right) to a dummy end node \left(M+\mathrm{1}\right)， such that there are M non-dummy nodes. The dummy nodes have a duration of zero and no resource usage. （2） For the resource restraints， the activities （amount of n， n?M） in subset V^{\mathrm{*}}?V are executed by one resource. There are no precedence relations between these activities so that they are named as “parallel activities”. The resource is renewable and masters skills required by each activity i\in V^{\mathrm{*}}， and can only be assigned to one activity i at each time instead of more activities simultaneously. The goal is to generate a baseline schedule， with starting times s_i and finishing times f_i， and to assign the resource to each activity i\in V^{\mathrm{*}}， while minimizing the project makespan. Although the scheduling is “local”， the number of schemes for it reaches n！， and the systematic project causes the local scheduling to be “far-reaching”， and the problem may yield to no problems of global scheduling.

Key words: resource-constrained project scheduling, sequence optimization, 0-1 mixed linear programming, network planning technology, project duration