=Paper=
{{Paper
|id=Vol-2098/paper7
|storemode=property
|title=The Planning Investment Project
with Identical Independent Jobs
|pdfUrl=https://ceur-ws.org/Vol-2098/paper7.pdf
|volume=Vol-2098
|authors=Kseniya A. Chernykh, Vladimir V. Servakh
}}
==The Planning Investment Project
with Identical Independent Jobs==
https://ceur-ws.org/Vol-2098/paper7.pdf
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)