We consider a project scheduling problem with multiple resource constraints as well as precedence constraints. For this problem, we apply and compare three popular search methods - Genetic Algorithm (GA), Simulated annealing (SA) and Tabu Search (TS), which have been used for various combinatorial optimization problems. We develop an encoding scheme in which a solution is represented with a string of numbers. Each number of the string denotes priority of each activity. The priority is used to select an activity among competing ones for resource allocation. This encoding method is very flexible, in the sense that problems with objective functions of a general functional form (such as a nonlinear function) and complex constraints from real world can be considered with much difficulty since it does not depend on the network topology. Furthermore, our procedure can be used in project scheduling problems with multiple projects. To evaluate the performance of our procedure, a series of computational test was done on randomly generated problems. The test shows that our procedure outperforms other existing heuristic methods - the minimum slack method, the iterative technique, the SEARCH heuristic.
이 논문은 자원제약이 있는 프로젝트 스케줄링에 대한 문제를 다루고 있다. 프로젝트는 하나가 있는 것으로 가정하고, 자원제약은 시간단위로 재충전이되며, 여러개가 있는 문제를 풀었다. 우리는 이러한 문제뿐만이 아닌, 여러가지 유형의 프로젝트 스케줄링 문제를 광범위하게 접근할수 있는 탐색알고리듬을 사용하였다. 이러한 탐색 알고리듬에서 가장 중요하게 여겨지는 것이 해의 표현방법인데, 이러한 해의 표현 방법으로 '가중치 리스트'를 사용 하였다. 가중치 리스트는 프로젝트의 액티버티에 대해 주어지는데, 이러한 가중치는 자원제약이 문제시될때, 가중치가 높은것을 우선적으로 스케줄하는데 사용된다. 탐색기법으로는 요즈음 많이 각광받고 있는 알고리듬인, 제네틱 알고리듬, 시뮬레이티드 어닐링, 타부 서치 기법을 사용하였다. 이러한 세가지 기법을 각각의 파라미터를 추정해서, 기존의 휴리스틱과 비교를 비교하였다. 다양한 비교를 위해서 여러가지 특성을 지니는 문제를 만들어 테스트해 보았다. 우리의 가중치 리스트를 이용하는 세가지 알고리듬이 기존의 알고리듬보다 좋은 해를 보였다. 우리의 기법은 문제에 특성에 영향을 적게 받으며, 또 다른 여러가지 문제 예를 들면, 현재가를 최대화하는 문제등에 광범위하게 이용될 수 있겠다.
