Abstract Generated abstract
This paper formulates a resource allocation problem for network planning with discrete time, multiple target events, directive completion dates, noninterchangeable and nonstorable resources, and noninterruptible activities. It shows that the direct schedule formulation leads to an integer nonconvex piecewise-linear programming problem of large dimension, while an alternative formulation with binary start-time variables makes the problem convex piecewise-linear only by greatly increasing dimensionality. Since exact and generally bounded approximate methods are judged impractical for such cases, the paper argues for heuristic procedures that exploit two structural features: the recurrent form of precedence constraints under topological ordering and the separability of resource constraints. A general scheme is proposed in which activity start times are fixed successively, resource inequalities are reduced accordingly, and calendar feasibility is controlled through equivalent upper-bound constraints.
Full Text
UDC 51.330.115
CYBERNETICS AND CONTROL THEORY
L. Ya. LEIFMAN
ON A PROBLEM OF RESOURCE ALLOCATION IN NETWORK PLANNING
(Presented by Academician V. M. Glushkov on 5 IX 1966)
1. Let a network graph (project) \(G(E; W)\) be given, where \(E\) is the set of events (vertices), and \(W\) is the set of activities (arcs). Connectedness of the network graph and uniqueness of the input or output are not assumed. Each activity is specified by its initial event \(x\) and terminal event \(y\) and is denoted by \((x,y)\). Discrete time is considered on the interval \((0,M]\), where \(0\) is the moment of the start of the project, and \(M\) is a prescribed number, called the calendar length.
Denote by \(E^f\) the set of all events that are outputs of the graph \(G(E; W)\); we shall call them the target events of the network graph. For each \(e \in E^f\) an integer \(t_e^{\mathrm{dir}} > 0\) is prescribed—the directive date for the occurrence of this event \(\bigl(\max \{t_e^{\mathrm{dir}} : e \in E^f\} \equiv T^{\mathrm{dir}} < M\bigr)\). Thus the general scheme includes single-theme, multi-theme, and multi-target projects.
All resources \(P_j\) used in the project are numbered by ordinal numbers \(j: 1 \leqslant j \leqslant n\). For uniformity, concerning activities that require no resources, we shall say that resource \(P_0\) is used on them with intensity \(f_0(x,y)=0\). For each resource \(P_j\) \((1 \leqslant j \leqslant n)\) and each unit of time \(m \in (0,M]\), a number \(h_j^m \geqslant 0\) is given—the available amount of the indicated resource in this unit of time.
For each activity \((x,y) \in W\) the following information is specified: \(J(x,y) \neq \varnothing\)—the set of indices \(j\) of resources used (consumed) on this activity; moreover, if \(0 \in J(x,y)\), then \(\{1,2,\ldots,n\} \cap J(x,y)=\varnothing\); \(f_j(x,y) \geqslant 0\)—the intensity of use (consumption) of the \(j\)-th resource (i.e., the amount of the resource used or consumed per unit time) for each \(j \in J(x,y)\), with \(f_j(x,y)=0\) only for \(j=0\); \(\tau(x,y) \geqslant 0\)—the duration of performing the activity (in integer units), with \(\tau(x,y)>0\) if \(0 \notin J(x,y)\).
The starting moment of activity \((x,y)\) will be denoted by \(\alpha(x,y)\). The notation \(x \prec\!\prec y\) means the existence of an activity \((x,y) \in W\), while \(z \succ\!\succ y\) means the existence of an activity \((y,z) \in W\).
The following assumptions are postulated:
\(1^\circ\). Each activity \((x,y) \in W\) is performed on the time interval \((\alpha(x,y), \alpha(x,y)+\tau(x,y)]\) of length \(\tau(x,y)\) without interruptions.
\(2^\circ\). No two resources \(P_j\) and \(P_{j'}\), with \(j \neq j'\), are interchangeable.
\(3^\circ\). The resources \(P_j\) are nonstorable, i.e., the amount of a resource that was available but remained unused in some unit of time cannot be used in any other unit of time.
It is required to find, for each activity \((x,y) \in W\), such integer values \(\alpha(x,y)\) that the network constraints* be satisfied:
\[ \alpha(x,y) \geqslant \max_{z \prec\!\prec x}\{\alpha(z,x)+\tau(z,x)\} \quad \text{for all } (x,y)\in W; \tag{1} \]
* We adopt the convention that \(\max \{f(x): x \in \varnothing\}=0\).
constraints imposed by the length of the calendar:
\[ \max_{(x,y)\in W}\{\alpha(x,y)+\tau(x,y)\}\equiv \max_{e\in E^f}\left\{\max_{x\prec e}\{\alpha(x,e)+\tau(x,e)\}\right\}\leq M, \tag{2} \]
and the resource constraints:
\[ \sum_{(x,y)\in W(j)} f_j^m(\alpha(x,y))\leq h_j^m \quad (1\leq j\leq n;\quad 0<m\leq M), \tag{3} \]
where \(W(j)\) is the set of all activities using resource \(P_j\):
\(W(j)=\{(x,y):(x,y)\in W,\ j\in J(x,y)\}\), and \(f_j^m(\alpha(x,y))\) is the intensity of use of resource \(P_j\) in the \(m\)-th unit of time for performing activity \((x,y)\), provided that its execution begins at time \(\alpha(x,y)\):
\[ f_j^m(\alpha(x,y))= \begin{cases} f_j(x,y), & \text{if } m\in(\alpha(x,y),\,\alpha(x,y)+\tau(x,y)],\\ 0, & \text{if } m\in(0,M]\setminus(\alpha(x,y),\,\alpha(x,y)+\tau(x,y)]. \end{cases} \tag{4} \]
At the same time, the functional
\[ F(A)=\max_{e\in E^f}\left\{\max_{x\prec e}\{\alpha(x,e)+\tau(x,e)\}-t_e^{\mathrm{dir}}\right\}, \tag{5} \]
must attain its minimum, where \(A=\{\alpha(x,y)\}\) is the vector of values \(\alpha(x,y)\), with the number of components equal to \(w\), the number of activities in \(W\) (we shall call this vector the schedule).
The formulated problem may be regarded as a mathematical programming problem in the \(w\)-dimensional space of schedules with \(w+nM+1\) inequality-type constraints. In this problem the functional (5) is convex piecewise-linear, and constraints (1)—(2) define a convex piecewise-linear region. However, constraints (3), owing to the nonconvexity of the functions (4), define a nonconvex region (also piecewise-linear). Thus we have obtained an integer problem of nonconvex piecewise-linear programming. To give an idea of the size of the problem, let us indicate the order of magnitude of the quantities occurring in real problems:
\[ w\approx 10^4,\qquad n\approx 10^2,\qquad M\approx 10^2. \tag{6} \]
This gives a problem with \(2\cdot 10^4\) constraints in a \(10^4\)-dimensional space.
- Passing from the space of schedules to another space by introducing, instead of \(\alpha(x,y)\), new variables:
\[ \xi^m(x,y)= \begin{cases} 1, & \text{if } \alpha(x,y)=m-1,\\ 0, & \text{otherwise}^{*}, \end{cases} \]
one can formulate the problem under consideration as an integer problem of convex piecewise-linear programming in a \(wM\)-dimensional space with \(2w+nM+wM+1\) constraints. For the numerical values of the problem parameters (6), this would be a problem in a \(10^6\)-dimensional space with \(10^6+3\cdot 10^4\) constraints—the passage from the nonconvex problem to a convex one is achieved at the price of a considerable increase in the problem’s dimensionality. This dimensionality increases even more substantially if one passes in the usual way from the convex problem of piecewise-linear programming to an integer linear-programming problem.
- Since, for the exact solution of problems of this kind, at present it is impossible to indicate methods amenable to numerical implementation even on the most powerful computers, it is necessary to seek approximate methods for their solution. However, universal approximate methods with error estimates for problems of this class also cannot yet be constructed. Therefore, using the specificity of the problems and their structural features, one has to construct approximate solution methods,
* The idea of introducing these variables belongs to L. T. Petrova.
which have come to be called heuristic. The main fundamental differences of each such method from the approximate methods usual in computational mathematics consist in the fact that for it: 1) the domain of its applicability is not defined (even in the sense of sufficiency); 2) there is no estimate of the error or, if the process is infinite, no proof of convergence. These two “nots,” while depriving heuristic methods of rigor, nevertheless do not prevent them in many cases from giving good results.
The structural features of the problem under consideration which should be used in constructing solution methods are the following two properties:
a) The system of inequalities (1) is recurrent in the sense that, if the inequalities (1) are written in such an order that the jobs in the left-hand sides of the inequalities form a topologically ordered list (in this case we shall call the system (1) topologically ordered), then the right-hand side of each inequality will depend only on the left-hand sides of preceding inequalities and will not depend on any of the left-hand sides of the subsequent inequalities of this system.
b) The inequalities (3) are separable—the right-hand side is constant, and each term of the left-hand side depends only on one job \((x, y)\), on which the other terms of this inequality do not depend. Therefore, when the values \(\alpha(x, y)\) are fixed for one or several jobs, the system (3) is reduced to a smaller number of dimensions by simple subtraction of the numbers \(f_j^m(\alpha(x, y))\) from both sides of the corresponding inequalities.
These two properties make it possible to reduce substantially the enumeration of variants through the successive selection and fixing of the values \(\alpha(x, y)\) in the topologically ordered system of inequalities (1) and the corresponding reduction of the system (3). The schedule \(A\) found by construction will satisfy the systems (1) and (3), and substitution into inequality (2) checks the admissibility of schedule \(A\). If it is admissible, then we accept it as an approximate solution of the problem. In order to control the fulfillment of inequality (2) in the process of choosing the values \(\alpha(x, y)\), one may replace (2) by the equivalent system of \(w\) inequalities
\[ \alpha(x, y) \leq M - \rho_2(y) - \tau(x, y), \tag{7} \]
where
\[ \rho_2(y) = \max_{z > y} \{\rho_2(z) + \tau(y, z)\}. \]
It is easy to see that the right-hand sides of all inequalities (7) are constant numbers.
Within the framework of the indicated general scheme, various concrete methods can be constructed for solving the posed problem. These methods will differ from one another in: 1) the ways of topologically ordering the list of jobs; 2) the ways of dividing the ordered list into groups of jobs for which the values \(\alpha(x, y)\) will be chosen simultaneously; 3) the ways of constructing the schedule for the next group of jobs. One of such methods is described by the author in (¹).
CITED LITERATURE
¹ L. Ya. Leifman, DAN, 175, No. 2 (1967).