부분 조정 및 완화 확산 기법을 통한 프로젝트 스케줄링에서의 부하평준화

Abstract

프로젝트 스케줄링은 조선 및 건설 산업, R&D 관리, S/W 개발 등의 현업에서 중요한 문제이다. 이외에도 make-to-order나 project-to-order의 업태를 갖는 분야에서도 효율적 생산 관리를 위해 프로젝트 스케줄링 문제는 중요하다. 그런데 프로젝트 스케줄링은 문제의 특성 상 높은 계산 비용을 요구한다. 이에 따라 크기가 큰 프로젝트 스케줄링 문제의 경우에는 현업에 적용 가능한 계산 속도를 보이는 알고리즘 개발이 쉽지 않다. 본 연구에서는 크기가 큰 문제를 작은 부분 문제로 나누어서 푸는 프로젝트 스케줄링 해법을 제시한다. 부분 조정 기법은 큰 전체 문제를 작은 부분 문제로 나눈 뒤 부분 문제에 대해 해결을 도모한다. 부분 조정 기법이 단순한 지역 탐색 기법과 다른 점은 병렬 처리를 도모한다는 점이다. 병렬 처리를 통해 전체 문제를 여러 지점에서 다발적으로 푸는 것이 가능하다. 병렬 처리를 골자로 하는 부분 조정 기법은 필연적으로 동시성 제어를 포함해야 한다. 본 연구는 프로젝트 스케줄링 문제에 범용적으로 적용 가능한 동시성 제어 기법을 제시한다. 이를 통해 병렬 처리뿐만 아니라 다수 컴퓨터를 이용한 분산 처리도 가능하다. 또한 부분 조정 기법의 평준화 모듈로서 작동하는 완화 확산 기법 또한 소개한다.

Project scheduling is a critical issue in industries, such as shipbuilding, construction, research and development management, and software release management. Efficient production management under make-to-order or project-to-order environment has to be based on efficient project scheduling. Project scheduling, however, consumes heavy computational cost. Thus it is very hard to develop solving algorithm which is applicable to industry situation if project scheduling problem is large. In this research, I propose algorithms that insensitive to size of problem. The algorithm, named partial adjustment method, extracts small but reasonable size of partial problem from large problem and solve the partial problem in parallel. Partial adjustment method consists of five modules: pre-processing, control, divide, solving, and analyze module. After pre-process, control module is activated in background and manages parallel processes. With control module, one or more parallel process(es) of divide and solving modules are executing. Divide module, core part of partial adjustment method, formulates partial problem and sets up system, locking and flag, for concurrency control. Solve module attempts to solve partial problem and analyze module, finally, updates level parameters for algorithm status and strategy. Solve module in this research uses diffusional relaxation method while solve module in partial adjustment method is replaceable with the other algorithms. Diffusional relaxation method is basically local search heuristics based on randomness. It increases the level of relational constraints relaxation as trial goes on. Therefore, it solves the partial problem in a short but reasonable time on early stage, and attains solutions of better quality on latter stage.