In the article, the investment project scheduling problem with identical technologically independent jobs is considered. The processing time of any job is a unit. A use of credit is allowed. In research of structure of the optimal solution, the continuous approximation of a problem is used. The result can then be presented in analytical view. Also, in the article, the algorithm of the solution of a problem in discrete case is o ered.
The project scheduling problem with limited resources is NP-hard in the strong
sense [
Problem with the credits, when there are practically no restrictions on
resources, but their using has to be paid, was considered in [
Copyright c by the paper's authors. Copying permitted for private and academic purposes. In: S. Belim et al. (eds.): OPTA-SCL 2018, Omsk, Russia, published at http://ceur-ws.org
In this article, to investigate the structure of the solution of the problem assigned, the case of identical technologically independent jobs of unit duration is considered. In the assumption that the number of jobs is su ciently large, the schedule can be set not by the number of jobs performed at any time, but by the fraction from their total number. Such a continuous approximation allows us to obtain analytical formulas and understand the structure of the optimal solution of the problem. In the conclusion of the article, a discrete version of the problem is considered, the pseudo-polynomial algorithm of its decision is o ered, the convergence of this decision to the continuous decision experimentally is established with an increase in the number of jobs. 2
Problem Formulation There are N technologically independent jobs of unit duration, and the only type of a resource is nancial. For each job of j = 1; 2; : : : ; N are set necessary capital investments of kj . Cash is invested in the moment of the beginning of the performance of a job. Upon completion of the job, we receive an income of cj . The investor possesses an initial capital in the amount of K0. There is a possibility of crediting at the rate of r for the unit period of time. Reserve cash is placed on the market under an alternative risk-free rate of r0. For comparison of cash at di erent times, we use discounting operation. It is required to draw up the schedule of execution of jobs in which the net present value of the entire project will be maximum.
We will give an interpretation of this problem. The investor owns a plot of land on which he wants to build a cottage village of N houses. Each house is built independently of others, and the beginning of its construction depends solely on nancing. If cash is available that materials can be bought, workers can be employed. Upon completion of construction, the house is for sale. The cash received from the sale can be invested in the construction of other houses. Use of the credits is possible. It is necessary to determine the start time of the construction of houses at which the general pro t of all project will be maximum.
With single job durations, there is a schedule in which all jobs begin and end at integer instants of time. Then the schedule is determined by the sets of jobs Nt, the execution of which begins at time t, t = 0; 1; : : : ; T 1. T is the completion time of the entire project, which must also be found. we take the credit under rate of r, and, therefore otherwise reserve cash in the amount of Ft P kj is placed at the rate of r0 j2Nt The income FT discounted to the initial moment of time. Subtracting the initial capital investments of K0 we will receive value of the net present value of N P V (S) =
FT (1 + r0)T
K0; which needs to be maximized on a set of all schedules of performance of jobs. Thus, it is required to nd the time of completion of the project and the partition of the set of all jobs into a sequence of subsets (N0; N1; : : : ; NT 1).
We will write out some conditions of implementation of the project and its separate jobs.
Statement 1.1. Jobs j are performed only under the condition kcjj 1 + r0.
Really, if kcjj < 1 + r0, then the shift at the beginning of job j for a later period increases the net present value of the entire project. Therefore, its implementation will postpone for an inde nitely long term.
Statement 1.2. To execute a project, it is necessary and su cient that either K0 > 0, or there exists j 2 f1; 2; : : : ; N g, for which kcjj > 1 + r.
The proof of necessity is obvious, if there is no start-up capital and performance of job at the expense of credit leads to a negative result, then a positive balance will never be achieved. The su ciency follows from the assumptions of the model in question about investing reserve capital under the rate r0. If K0 > 0, then this cash is placed under the rate r0, and through a certain period of time, we receive the necessary sum for a performance of the project's jobs. Under the second condition, we perform the job j at the initial instant of time. Because of the kcjj > 1 + r, we will gain income which can also be placed at a rate of r0 and after a while to receive the necessary sum of cash.
Thus, to start a project, you either need the existence of seed capital or that the pro tability at least of one job was above a credit rate. In this case, the pro tability of all jobs must be higher than the rate r0. 3
The continuous case for the purpose of identi cation of the structure of an optimal solution, research of dependence of this structure from the initial capital, the pro tability of jobs and a rate of liquidity will consider.
We will assume that all jobs are identical and N ! 1. In this situation the schedule is understood as a vector (x0; x1; : : : ; xT 1), where xt is the share T 1 of the jobs starting in t instant. The following relation is executed P xt = 1. t=0 Without loss of generality, we denote by k is the common investments, and by c is the total income. Then the investments in the year t will be k xt, and the corresponding receipts in the year t + 1 will be c xt. The schedule for which the pro t is led to the initial moment it will be maximum is required to be found.
Theorem 2.1. If kc > 1 + r, then the shift of the part of the job performed at the expense of the credit at an earlier time increases the NPV.
Proof. Suppose that at the moment t a credit is taken +"k, at the next moment of time t + 1 there is an income +c" from the sale, part of which is to repay the loan taken at the previous time, namely, "k(1 + r). Then c k(1 + r) > 0, because kc > 1 + r. Therefore, if you take the credit at an earlier moment of time, then the NPV will increase at kc > 1 + r.
Corollary. In an optimal solution, we take the credit only at the initial time.
For the nding of a share of jobs which need to be executed in time points of t = 1; 2; : : : ; T 1, we will use an auxiliary formula: x0t = c 1 kr c c kr k2r c2 k : : : ktr ct = c 1 c kr k kr 1 ( k )t ; c 1 ckc and we will calculate the fractions starting from the moment t = T t = T 2 and until the time t = 1 according to the following rule: The Net Present Value of the entire project have calculated by the formula:
a(1 + r)) c(1
a(1 + r)) 0 s b 0:4 o j f o e r a h
S 0:2 The solution looks like this: 1 2 3 4 5 6 7 8 9 10 11 12 13
Year
Statement 2.1. There will be such values of variables c; k; r provided that kc ! 1 + r, for which T 1.
Proof. The completion time of the project is calculated by the formula T = loga where a = kc . On a theorem condition kc ! 1 + r, therefore a = kc ! 1 +1r . Then lim loga
1 a! 1+r In This Section, We Will Consider the Continuous Case When for Implementation of the Project There is an Initial Capital That is Not Equal to Zero.
Theorem 3.1. If K ck+2k , then in initial time jobs is made at the expense of the tentative capital and all of the remaining jobs is due to reinvestment of income. At the same time, all project will manage to be realized in two years.
2
Proof. Really, let K = ck+k . Then in an initial instant, the share of the performed jobs is equal
Income will be c c+kk . It is necessary to execute x0 =
K = ck+2k = k k
k c + k
: c jobs, investments into which are equal to c+k
The net present value of the project N P V =
k K + c+k c c+c k 1 + r0 k +
c+c k c (1 + r0)2 =
k2 c + k +
c2 (1 + r0)2 (c + k) = = c2 k2(1 + r0)2 (c + k) (1 + r0)2 2
Now K > ck+k , then x0 = Kk ; x1 = 1 case will be K . The pro t of the project in this k N P V =
K c K + k
1 1 + r0
K k k + 1 Kk (1 + r0)2 c = =
Kk(1 + r0)2 + Kc(1 + r0)
k2(1 + r0) + Kk(1 + r0) + kc (1 + r0)2k
Kc = = k(c k
Thus, it turned out that the proceeds from the sale of the share of jobs completed at the initial time are equal to the investments in the remaining jobs. Thus, there will be enough starting capital to realize the project in two years without taking of the credit.
2
If K < ck+k , then in an optimal solution for the nding of a share of jobs which need to be executed in instants t = 2; 3; : : : ; T 1 we use an auxiliary formula:
K + Kr + c : : : kcttr + Kc kctt 11 + : : : + kc + 1 + Kr c
1 + : : : + kctt 11 k k kr kr
K + Kr + c kcr 11 ( kckc)t + Kc (1 + r) 1 ( k )t 1
c 1 kc and we will calculate the fractions starting from the moment t = T t = T 2 and until the time t = 2 according to the following rule: x0t = or
K + Kr + c kcr 1 (1kc )kcT 1 + Kc k
kr (1 + r) 1 ( kc )T 2 ;
1 kc
K + Kr + c kcr 1 (1kc )kcT 2 + Kc
K + Kr + c kcr 1 (1kc )kcT 3 + Kc k kr
kr (1 + r) k (1 + r)
T 1 X xt); t=3 For time point of t = 1 and time point of t = 0 share of jobs is calculated by the formulas: x0 = k c K kr
Kr 1
T 1 ! X xt ; x1 = t=2 1 k c K kr
Kr 1
T 1 ! X xt : t=2 The net present value of the entire project is calculated by the formula c xT 1 (1 + r0)T
K: We will denote by a = kc ; b = Kc . Then 0 b(1+r) + B 1 a
@ (1 + r0)T (1+r0)T ln(1+r0) 1 10 A = 0; !0 = 0; 1 1 r a (a + ar0)T ln a(1 + r0) + b(1+r) (1 + r0)T ln(1 + r0)
1 a ar1 aaT r (1 + r0)T + b(1 + r) 1 1aTa 2 (1 + r0)T aT 2(1 + r0)T ln a + aT 2(1 + r0)T ln(1 + r0) ar1 aaT r (1 + r0)T + b(1 + r) 1 1aTa 2 (1 + r0)T aT = 1 ar a + b(11 +ar)
r 1 a aT (1 + r0)T ln a(1 + r0); T = loga a2 (1(b(1(+a r) b)(1 + r)) ln(1 + r0) a2r) ln a(1 + r0) = ab2((11+ ra)) aT (1+r0)T ln a(1+r0) ; = = 2 + loga ((a (a2r Now we will return to an initial problem, in which there are N identical works of unit duration. Investments in each job will be k, and receipts will be c.
We use the scheme of dynamic programming. To implement the scheme, it is necessary to construct an upper estimate of the completion time of the project. On condition of kc > 1+r it is enough to take Tmax = N . R(t; n) is the maximum income received by the moment t, if by that time n jobs were completed. The variable xt designates quantity of jobs which begin realization during t. We will write down the Bellman's equation
R(t + 1; n) = xt=m0;a1;x:::;nf(R(t; n xt) kxt)(1 + s) + cxtg; where s = r, if R(t; n xt) kxt < 0, and s = r0 otherwise.
For realization of an algorithm for each n = 1; 2; : : : ; N we establish starting conditions of R(1; n) = (K0 nk)(1 + s) + nc, and we will organize a double cycle concerning t = 1; 2; : : : ; Tmax and n = 1; 2; : : : ; N , we calculate the value R(t; n) on the recursion formula which is written out above.
For the following values of the project N = 5; k = 3; c = 5; r = 0; 2; r0 = 0; 1; K0 = 0, the optimal solution is reached in T = 3 and quantity of the executed jobs (x0; x1; x2) = (3; 1; 1). The net present value of such a project is N P V = 6; 5. If completely to execute all ve jobs during the rst period of time at the expense of the credits, pro t will be 6,36 units.
The complexity of an algorithm does not exceed O(N 3) of operations. We note that this algorithm is a pseudo-polynomial as the problem entrance in a case with jobs of unit duration has a logarithmic dependence on N .
The program was written. The experimental calculations show that at N ! 1 the discrete decision converges to the continuous optimum which is analytically received above.
Statement 3.1. There will be such values of variables c; k; r provided that kc ! 1 + r, for which T N .
The illustration is given in the table:
N 100 100 100 100 100 100 100 100 100 k 5 5 5 5 5 5 5 5 5
c 6 + 10 1 6 + 10 2 6 + 10 3 6 + 10 4 6 + 10 5 6 + 10 6 6 + 10 7 6 + 10 8 6 + 10 9 r 0,2 0,2 0,2 0,2 0,2 0,2 0,2 0,2 0,2
T 14 25 39 50 64 76 87 94 95 Thus, we receive that at N = 100; r = 0; 2; k = 5; c = 6 + "; " ! 0; T N .
In connection with a statement 3.1, existence of a polynomial algorithm for problem with identical jobs under doubt, since the output of the problem (x0; x1; : : : ; xT 1) longwise is comparable with N and from the length of the input this dependence is pseudo-polynomial. The problem of the complexity of the problem with arbitrary kj and cj remains open.