The Planning Investment Project with Identical Independent Jobs ? Kseniya A. Chernykh and Vladimir V. Servakh Sobolev Institute of Mathematics, Novosibirsk, Russia ksesha2909@gmail.com, svv usa@rambler.ru Abstract. In the article, the investment project scheduling problem with identical technologically independent jobs is considered. The pro- cessing 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 offered. Keywords: Project scheduling · NP-hardness · Pseudo-polynomial al- gorithm 1 Introduction The project scheduling problem with limited resources is NP-hard in the strong sense [1]. There are few cases when the problem is polynomially solvable. This problem of minimization of the common runtime of the project in restriction for resources only the stored type [2]. But even if the resources are stored, and as criterion mean time of completion of jobs or the net present value is used, then the problem becomes strongly NP-hard [5]. Problem with the credits, when there are practically no restrictions on re- sources, but their using has to be paid, was considered in [3]. In [4] the strongly NP-hard of this problem was proved. The problem of finding the maximum clique in the graph was reduced to its. The proof relies heavily on the type of technological dependence of the jobs. From this fact follows that the difficulty of the problem is connected, first of all, with the partial order of performing the jobs. In such a situation, the question of the complexity of the problem with an empty partial order, when all the jobs are independent, attracts interest. At present, the computational complexity of the task of maximizing project profit at technologically independent jobs remains open. ? The work was supported by the program of fundamental scientific researches of the SB RAS N I.5.1., project N 0314-2016-0019. 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 Planning Investment Project with Identical Independent Jobs 83 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 sufficiently 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 offered, 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 financial. 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 different 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 financing. 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 profit 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. Let Ft is income by the time of t, t = 0, 1, . . . , T . Originally F0 = K0 . For t = 0, 1, . . . , T − 1 the value of income of Ft+1 is calculated recurrently. P If there isn’t enough cash of Ft on the current investments, for the amount of kj −Ft j∈Nt we take the credit under rate of r, and, therefore X X Ft+1 = (Ft − kj )(1 + r) + cj , j∈Nt j∈Nt 84 K. Chernykh, V. Servakh P otherwise reserve cash in the amount of Ft − kj is placed at the rate of r0 j∈Nt X X Ft+1 = (Ft − kj )(1 + r0 ) + cj . j∈Nt j∈Nt 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 FT N P V (S) = − K0 , (1 + r0 )T which needs to be maximized on a set of all schedules of performance of jobs. Thus, it is required to find 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. c Statement 1.1. Jobs j are performed only under the condition kjj ≥ 1 + r0 . cj Really, if kj < 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 imple- mentation will postpone for an indefinitely long term. Statement 1.2. To execute a project, it is necessary and sufficient that c either K0 > 0, or there exists j ∈ {1, 2, . . . , N }, for which kjj > 1 + r. The proof of necessity is obvious, if there is no start-up capital and perfor- mance of job at the expense of credit leads to a negative result, then a positive balance will never be achieved. The sufficiency 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. c Because of the kjj > 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 profitability at least of one job was above a credit rate. In this case, the profitability of all jobs must be higher than the rate r0 . 3 Continuous Case The continuous case for the purpose of identification of the structure of an op- timal solution, research of dependence of this structure from the initial capital, the profitability of jobs and a rate of liquidity will consider. We will assume that all jobs are identical and N → ∞. In this situation the schedule is understood as a vector (x0 , x1 , . . . , xT −1 ), where xt is the share TP−1 of the jobs starting in t instant. The following relation is executed xt = 1. t=0 Without loss of generality, we denote by k is the common investments, and by Planning Investment Project with Identical Independent Jobs 85 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 profit 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) ε NPV = t+1 = · (c − k(1 + r)). (1 + r0 ) (1 + r0 )t+1 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 finding 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: c − kr − k c − kr − k x0t = k2 r kt r =  , c 1 − kr − − . . . − 1−( kc )t c c2 ct c 1 − kr · c k 1− c and we will calculate the fractions starting from the moment t = T − 1, then t = T − 2 and until the time t = 1 according to the following rule: c − kr − k xT −1 =  , 1−( kc )T −1 c 1 − kr c · 1− k c c − kr − k xT −2 =   · (1 − xT −1 ), 1−( kc )T −2 c 1 − kr c · 1− k c c − kr − k xT −3 =   · (1 − (xT −1 + xT −2 )), 1−( kc )T −3 c 1 − kr c · 1− k c .. . T −1 c − kr − k X x1 = · (1 − xt ), c 1 − kr  c t=2 For time point of t = 0 share of jobs is calculated by the formula: T −1 k X x0 = · (1 − xt ). c − kr t=2 86 K. Chernykh, V. Servakh The Net Present Value of the entire project have calculated by the formula: c · xT −1 NPV = . (1 + r0 )T −1 TP We will denote by a = kc . As xt = 1, the objective function takes the form t=0 c 1 − a(1 + r) NPV = ·   → max . (1 + r0 )T 1 − ar · 1−aT −1 T 1−a We will find the optimal value of this function:  0 c(1 − a(1 + r)) · 1    = 0, T −1 (1 + r0 )T · 1 − ar · 1−a 1−a !0 1 c(1 − a(1 + r)) · T = 0, (1 + r0 )T − ar−a r 1−a · (1 + r0 ) T   T ar T  −[(1 + r0 ) · ln(1 + r0 ) − 1−a · (1 + r0 ) · ln(1 + r0 )]    2 − Tr (1 + r0 )T − ar−a 1−a · (1 + r0 ) T   r T 1−a · (a + ar0 ) ln a(1 + r0 ) −  2  = 0,   Tr (1 + r0 )T − ar−a 1−a · (1 + r0 ) T   ar r (1 + r0 )T · ln(1 + r0 ) · 1 − =− · (a + ar0 )T ln a(1 + r0 ), 1−a 1−a   ar ln(1 + r0 ) · 1−a −1 aT = r . 1−a · ln a(1 + r0 )   (a(1 + r) − 1) · ln(1 + r0 ) T = loga . r · ln a(1 + r0 ) Example 2.1. k = 1 is investments in job, c = 1, 4 is income from job, r = 0, 2 is rate on the credit,r0 = 0, 1 is discount rate. The optimal time of completion of the project is T ≈ 3, 8. Optimal integer value is T ∗ = 4. Optimal solution is (x0 , x1 , x2 , x3 ) = (0, 534; 0, 107; 0, 150; 0, 209) Value of profit T =1 T =2 T =3 T∗ = 4 T =5 0, 182 0, 193 0, 199 0,200 0, 197 Planning Investment Project with Identical Independent Jobs 87 The solution looks like this: Share of jobs 0.4 0.2 1 2 3 4 Year Example 2.2. k = 2 is investments in job, c = 2, 4 is income from job, r = 0, 15 is rate on the credit, r0 = 0, 05 is discount rate. The optimal time of completion of the project is T ≈ 12, 6. The solution looks like this: 0.3 Share of jobs 0.2 0.1 0 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 c k → 1 + r, for which T ∼ ∞. Proof. The completion time of the project is calculated by the formula   (a(1 + r) − 1) · ln(1 + r0 ) T = loga , r · ln a(1 + r0 ) 88 K. Chernykh, V. Servakh where a = kc . On a theorem condition kc → 1 + r, therefore a = kc → 1+r 1 . Then   (a(1 + r) − 1) · ln(1 + r0 ) lim1 loga = a→ 1+r r · ln a(1 + r0 ) 1 ! ( 1+r · (1 + r) − 1) · ln(1 + r0 ) = lim1 log 1+r 1 1 = lim1 log 1+r 1 0 = ∞, a→ 1+r r · ln 1+r · (1 + r0 ) a→ 1+r 1 as 0 < 1+r < 1. Therefore T ∼ ∞ at kc → 1 + r. 4 Continuous Case with Nonzero Initial Capital In This Section, We Will Consider the Continuous Case When for Implementa- tion of the Project There is an Initial Capital That is Not Equal to Zero. k2 Theorem 3.1. If K ≥ c+k , 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 k Proof. Really, let K = c+k . Then in an initial instant, the share of the performed jobs is equal k2 K k x0 = = c+k = . k k c+k k Income will be c · c+k . It is necessary to execute k c+k−k c x1 = 1 − = = c+k c+k c+k c jobs, investments into which are equal to c+k · k. The net present value of the project k c c · c − c+k ·k c+k · c k2 c2 N P V = −K + c+k + 2 =− + = 1 + r0 (1 + r0 ) c + k (1 + r0 )2 · (c + k) c2 − k 2 (1 + r0 )2 = (c + k) · (1 + r0 )2 2 k Now K > c+k , then x0 = K K k , x1 = 1 − k . The profit of the project in this case will be K K 1− K   k ·c− 1− k ·k k ·c N P V = −K + + = 1 + r0 (1 + r0 )2 −Kk(1 + r0 )2 + Kc(1 + r0 ) − k 2 (1 + r0 ) + Kk(1 + r0 ) + kc − Kc = = (1 + r0 )2 k Planning Investment Project with Identical Independent Jobs 89 k(c − k − kr0 ) − Kr0 (c + k + kr0 ) = (1 + r0 )2 k Thus, it turned out that the proceeds from the sale of the share of jobs com- pleted 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 k If K < c+k , then in an optimal solution for the finding 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 − k − kr x0t =      kt r t−1 kt−1 c 1 − c − . . . − ct + c · kct−1 + . . . + kc + 1 + Kr kr K c · 1 + . . . + ct−1 or K + Kr + c − k − kr x0t =  1−( kc )t 1−( kc )t−1  c 1 − kr c · 1− k + K c · (1 + r) · 1− k c c and we will calculate the fractions starting from the moment t = T − 1, then t = T − 2 and until the time t = 2 according to the following rule: K + Kr + c − k − kr xT −1 =  k T −1 , kr 1−( c ) 1−( kc )T −2 c 1 − c · 1− k + Kc · (1 + r) · 1− k c c K + Kr + c − k − kr xT −2 =  k T −2  · (1 − xT −1 ), kr 1−( c ) 1−( kc )T −3 c 1 − c · 1− k + Kc · (1 + r) · 1− k c c K + Kr + c − k − kr xT −3 =  k T −3  · (1 − (xT −1 + xT −2 )), kr 1−( c ) 1−( kc )T −4 c 1 − c · 1− k + Kc · (1 + r) · 1− k c c .. . T −1 K + Kr + c − k − kr X x2 =  · (1 − xt ), 1−( kc )2  c 1 − kr K c · 1− k + c · (1 + r) t=3 c For time point of t = 1 and time point of t = 0 share of jobs is calculated by the formulas: −1 −1 T !   T ! k − K − Kr X k − K − Kr X x0 = · 1− xt , x 1 = 1 − · 1− xt . c − kr t=2 c − kr t=2 The net present value of the entire project is calculated by the formula c · xT −1 NPV = − K. (1 + r0 )T 90 K. Chernykh, V. Servakh K + Kr + c − k − kr xT −1 =  k T −1 1−( kc )T −2  1−( c) c 1 − kr c · 1− k + K c · (1 + r) · 1− k c c We will denote by a = kc , b = Kc . Then b(1 + r) + 1 − a(1 + r) xT −1 =  T −1 T −2 . 1 − ar · 1−a 1−a + b(1 + r) · 1−a 1−a −1 TP As xt = 1, the objective function takes the form t=0 c 1 + (b − a)(1 + r) NPV = · T −1 T −2 − K → max . (1 + r0 )T 1 − ar · 1−a 1−a + b(1 + r) · 1−a 1−a T We note that this formula holds for T ≥ 2. We will find the optimal value of this function:  0 c · 1 + (b − a)(1 + r)    = 0, T 1−aT −1 1−aT −2 (1 + r0 ) · 1 − ar · 1−a + b(1 + r) · 1−a !0 1 Tr 1−aT −2 = 0, (1 + r0 )T − ar−a T 1−a · (1 + r0 ) + b(1 + r) · 1−a · (1 + r0 )T  h i  T ar T − (1 + r 0 ) ln(1 + r0 ) − 1−a · (1 + r 0 ) ln(1 + r 0 ) 2  −    T T −2 (1 + r0 )T − ar−a r T 1−a · (1 + r0 ) + b(1 + r) · 1−a 1−a · (1 + r0 )T   r T b(1+r) T · (a + ar0 ) ln a(1 + r0 ) + 1−a · (1 + r0 ) ln(1 + r0 ) −   1−a 2  +   T ar−aT r T 1−aT −2 T (1 + r0 ) − 1−a · (1 + r0 ) + b(1 + r) · 1−a · (1 + r0 )   b(1+r)  T −2 T T −2 T  1−a · a (1 + r0 ) ln a + a (1 + r0 ) ln(1 + r0 ) +  2  = 0,   T ar−aT r T 1−aT −2 T (1 + r0 ) − 1−a · (1 + r0 ) + b(1 + r) · 1−a · (1 + r0 )   T ar b(1 + r) b(1 + r) T (1+r0 ) ln(1+r0 )· 1 − + = 2 a (1+r0 )T ln a(1+r0 )− 1−a 1−a a (1 − a) r − aT (1 + r0 )T ln a(1 + r0 ), 1−a   ln(1 + r0 ) · 1 − 1−a ar + b(1+r) 1−a aT = b(1+r) , r 2 a (1−a) ln a(1 + r0 ) − 1−a · ln a(1 + r 0 )   (1 − (a − b)(1 + r)) · ln(1 + r0 ) T = loga a2 · = (b(1 + r) − a2 r) · ln a(1 + r0 ) Planning Investment Project with Identical Independent Jobs 91   ((a − b)(1 + r) − 1) · ln(1 + r0 ) = 2 + loga . (a2 r − b(1 + r)) · ln a(1 + r0 ) The presented continuous solution sets the general character of the investor’s behavior at the exercise of the project. Example 3.1. k = 2 is investments in job, c = 2, 4 is income from job, r = 0, 15 is rate on the credit, r0 = 0, 05 is discount rate, K = 0, 1 is starting capital. The optimal time of completion of the project is T ≈ 4, 97. The solution looks like this: 0.6 Share of jobs 0.4 0.2 1 2 3 4 5 Year 5 Discrete Case 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) = max {(R(t, n − xt ) − kxt )(1 + s) + cxt }, xt =0,1,...,n 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 92 K. Chernykh, V. Servakh N P V = 6, 5. If completely to execute all five jobs during the first period of time at the expense of the credits, profit 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 → ∞ the discrete decision converges to the continuous optimum which is analyti- cally 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 k c r T 100 5 6 + 10−1 0,2 14 −2 100 5 6 + 10 0,2 25 −3 100 5 6 + 10 0,2 39 100 5 6 + 10−4 0,2 50 100 5 6 + 10−5 0,2 64 −6 100 5 6 + 10 0,2 76 −7 100 5 6 + 10 0,2 87 100 5 6 + 10−8 0,2 94 −9 100 5 6 + 10 0,2 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. References 1. Garey, M.R., Johnson, D.S.: Complexity result for multiprocessor scheduling under resource constraints. SIAM J. Comput. 4(4), 397–411 (1975) 2. Gimadi, E.H., Zalyubovsky, V.V., Sevastyanov, S.V.: Polinomial’naya razreshi- most’ zadach kalendarnogo planirovaniya so skladiruyemymi resursami i direk- tivnymi srokami (Polynomial solvability of scheduling tasks with storege resources and due dates). Discretnyy analiz i issledovanie operatsiy. Novosibirsk. Ser. 2, 7(1), 9–34 (2000), (in Russian) 3. Martynova, E.A., Servakh, V.V.: On scheduling credited projects. Automation and Remote Control 73(3), 508–516 (2012) 4. Kazakovtseva, E.A. Servakh, V.V.: Complexity of the Project Scheduling Problem with Credits. Journal of applied and industrial mathematics 9(4), 489–496 (2015) Planning Investment Project with Identical Independent Jobs 93 5. Servakh, V.V., Shcherbinina, T.A.: O slozhnosti zadachi kalendarnogo planirovaniya proyektov (Complexity of some project scheduling problem with non- renewable resources). Vestnik Novosibirskogo Gosudarstvennogo Univiversiteta, Seriya Matematika Mekhanika Informatika 8(3), 105–112 (2008), (in Russian)