This thesis deals with an investment scheduling problem for maximal net present value of dividend with reinvestment allowed, where each investment has certain capital requirement and deterministic positive profit. Deterministic profits are assumed to occur at completion of each investment and are divided into two parts, including dividend and reinvestment, at each predetermined reinvestment time point. The objective is to make optimal scheduling of investments over a fixed planning horizon which maximizes total sum of the net present values of dividends subject to investment precedence relations and capital limits but with reinvestment allowed. The proposed investment scheduling problem is transformed to a kind of parallel machine scheduling problem and formulated as an Integer Programming which is proven to be NP-complete in this thesis. Thereupon, a depth-first branch-and-bound algorithm is derived. To test the effectiveness and efficiency of the proposed algorithm, computational experiments are performed with some numerical instances. The experimental results show that the algorithm solves the problem relatively faster than the commercial software package (CPLEX 8.1), and optimally solves instances with up to 30 investments within a reasonable time limit.
기업이 보다 다양한 투자자들에게 노출되면서, 기업운영에 대한 투자자들의 영향력이 크게 증가하고 있다. 그러므로 투자자들에게 기업의 현황과 향후 계획을 보다 정확히 전달 함으로서, 기업의 가치를 올바르게 평가 받아 자금 조달을 원활히 하기 위한 Investor Relation (IR)이 중요시 되고 있다.
본 논문에서는 투자유치를 받기 위한 IR의 일환으로서, 앞으로의 계획을 투자자에게 보고하기 위해 풀어야 하는 투자계획문제를 다루고 있다. 투자자는 배당을 받음으로써 그 이윤이 발생하기 때문에, 배당의 현재가치를 극대화 시켜주는 향후 투자를 계획할 필요가 있는데, 각 회계연도에서 이루어지는 이윤배당과 그 나머지의 재투자가 고려된 자본제약 하에서 최적해를 찾는 것이 목적이다. 이 투자계획문제는 병렬 머신 스케쥴링 (Parallel Machine Scheduling)문제로 재해석되어, 브랜치 앤 바운드 구조 (Branch-and-Bound schemas)를 이용하여 최적해를 찾는 알고리즘이 구현되었다. 이 알고리즘을 다양한 문제에 대하여 실험하고 평가한 결과, 제안된 알고리즘이 효율적으로 작동하여 30개 투자대상까지의 문제를 수긍할 만한 시간 안에 풀 수 있다는 것을 보여주었다.
