This thesis is concerned with a general class of resource-constrained project scheduling problems. Three resource-constrained project scheduling problems are investigated in consideration of project-dependent associated performance measures.
The first problem considers a generally-classified resource-constrained project scheduling problem with the objective of minimizing the makespan of the project. Various operating modes are allowed to perform each activity in the project under the assumption that all activities are non-preemptive. For the problem, a branch-and-bound algorithm is considered by use of a depth-first search strategy employed for the associated tree search. The solution properties are explored so as to derive a lower bound computation procedure for the algorithm. The computational complexity of the lower bound computation is then investigated. For large-size problems, an efficient heuristic algorithm is also exploited by using partly the branch-and-bound algorithm.
The second problem is a scheduling problem for a project where cash inflows and outflows are given and availability restrictions are imposed on capital and renewable resource. For each activity, various operating modes are allowed. The objective of the problem is to maximize the net present value of the project. By using both left-shift and right-shift mechanisms, a two phase heuristic algorithm is exploited.
The third problem is concerned with a project scheduling problem where multiple objectives are simultaneously considered. Resource leveling criteria are also included in the problem. The problem is formulated as a goal programming (GP) model, where by considering objectives as flexible goals, a decision maker (DM) is able to obtain a satisfactory solution subject to desired requirements. A backtracking procedure is employed as a solution technique for the GP formulation model. An interactive decision is made in the whole solution search procedure such that DM specifies a target level and then selects a preferred solution among alternatives generated at each iteration. Some numerical examples are presented for illustrating the proposed interactive approach and for validating it in comparison with the other known interactive approaches.
프로젝트 추진 일정계획 문제는 제조업체와 서비스 조직에서 일상적으로 취급하는 중요한 의사결정 문제이다. 프로젝트는 수많은 상호 관련된 활동(activity)들로 구성되어 있고 각 활동들은 요구되는 자원들에 의해 주어진 소요시간 만큼 수행되어 진다. 즉, 자원의 제약하에 수행되어진다. 자원이 풍부한 상황하에서는 PERT/CPM 방법에 의해 프로젝트 추진 일정을 통제할 수 있으나, 현실적으로 자원의 제약이 있는 경우에는 효율적인 일정계획을 수립하기가 어렵다.
프로젝트를 추진하기 위해 가용되는 자원의 효율이 서로 다른 경우(resource-duration interactions), 각 활동들을 수행할 수 있는 방법에는 여러가지가 가능하다. 만일 자원의 종류가 인력 (manpower) 이라면, 사용 자원의 숙련도에 따라 활동이 일찍 완료될 수 도 있고, 또한 지연될 수도 있다. 이와같이 각 활동은 여러가지 자원 운용 방식 (operating modes)중 한 가지 방법에 의해 수행되며, 또 일단 수행이 시작되면 완료되기 전까지는 중단될 수 없다 (non-preemptive). 어떤 활동의 수행에 사용되어진 자원은 관련 활동이 완료되면 다른 활동에 다시 투입되어지며 (renewable), 총 프로젝트에 가용한 자원의 양 (resource availability)은 제한 된다.
본 논문에서는 이러한 상황을 고려한 자원 제약 조건(resource-constrained)하 에서의 프로젝트 추진 일정계획 문제를 세가지 형태의 성능 척도 (performance measure)에 대해서 각각 다룬다.
첫 번째 문제는, 총 프로젝트의 완료시간 (project completion time)을 최소화하기 위해 각 활동의 운용방식과 시작시점을 결정하는 문제이다. 최적해가 갖는 성질을 규명하고, 목적함수의 하한값을 계산하는 절차를 제시하며 최적일정계획을 구하는 분지한계법(branch-and-bound)을 소개한다. 또한 규모가 크고 복잡한 프로젝트의 일정 계획 문제를 풀기위해서, 부분적으로 분지한계법을 이용하는 효율적인 해법도 소개한다.
두 번째 문제는, 각 활동의 수행이 현금의 유입과 유출로 표현되고 초기 투자비용과 총 가용 자원의 제약조건이 주어진 상황에서, 프로젝트의 순 현재가(net present value)를 최대화하기위해 각 활동의 운용방식과 시작시점을 결정하는 문제이다. 좌 또는 우로 교체 (left and right shifts) 하는 기법을 사용하여, 효율적인 일정계획을 구하는 해법을 제시한다.
세 번째 문제는 다중의 성능척도(multiobjective)가 동시에 고려되는 경우의 프로젝트 추진 일정계획을 수립하는 문제이다. 여기에는 자원들의 이용율을 평준화(leveling) 하는 척도도 포함된다. 문제는 목적계획법(goal programming) 에 의해 공식화되며, 역추적해법(backtracking procedure)에 의해 가능한 대안이 제시된다. 의사결정자는 만족되지 않은 성능척도에 대해 그 성능의 요구수준을 명시하고, 제안된 여러 대안 중 바람직한 해를 선택하는 상호작용의사결정 절차를 진행함으로써 최종적으로 만족스러운 일정계획을 수립할 수 있다.
제안된 해법들은 다중의 프로젝트를 다루거나, 문제의 상황이 확실히 정해지지 않은 환경과 같은 현실적인 상황에서 발생되는 다양한 형태의 프로젝트 추진 일정계획을 수립하는 데 이용될 수 있다.
