내 신청현황
종류	모집공고명	진행상태
신청내용이 없습니다.

알림마당

home

고정기간 일정계획: 모델, 응용, 계산상의 복잡도 및 알고리즘

전문가 제언: ○ 일정계획은 어떤 사업(project)의 시발점부터 종착점까지의 단위사업 또는 작업에 대한 원활한 배분과 최적의 순서를 계획하는 사업평가 모형의 하나이다. 사업평가 모형에서는 단위사업과 단위사업 네트워크가 분석되고 그 결과에 따라 일정계획을 수립하게 된다. 일정계획에는 보통 작업내용, 작업시간기간 및 작업 배분의 문제가 발생하고 최적의 배분이 계획되고 평가된다.

○ 고정기간 일정계획 문제의 특징은 각 작업이 유한개의 고정된 처리기간을 갖는 것이다. 작업은 이용 가능한 기계 중 하나에서 처리되거나 전혀 처리되지 않을 수도 있다. 따라서 고정기간 일정계획은 처리될 작업과 처리기간의 배분에 대하여 이루어진다. 고정기간 일정계획 문제는 여러 가지 운영계획 상황에서 발생된다. 이를테면, 선적과 하역 터미널에의 수송차의 배분, 개인 작업 계획수립, 통신 채널의 주파수 대역폭 배당, 인쇄 회로기판 공정 및 유전자 확인과 실험용 컴퓨터 메모리 구조 등이 여기에 속한다.

○ 이 논문에서 Mikhail 등은 고정기간 일정계획 문제의 일반적인 성격과 그래프 이론과 기간과의 접목, 문제에 대한 다섯 가지의 유형들을 조사 분석하고 이들 유형별로 기존의 개발된 알고리즘과 계산상의 복잡도의 결과들을 개관한다. 여기서는 기존의 그래프 이론에서 다루지 않았던 개념들을 정의하고 이들이 어떻게 고정기간 일정계획 해결에 이용되는 가를 보인다.

○ 일정계획 문제는 사업 평가 모형인 CPM과 PERT에서 사용되고 여기에는 필연적으로 네트워크 이론이 뒷받침된다. 그러나 시간기간에 관계없이 기간을 고정시킴으로 특히 그래프 이론으로 해결하는 방안이 연구되어 오고 있음을 발견하게 된다. 최적이론의 한 분야로서 일정계획 문제는 건설을 비롯한 대형 사업에 필수적인 요소이므로 OR을 비롯하여 최적이론을 연구하는 분들에게 좋은 참고자료가 되리라고 본다. 특히 그래프 이론과 일정계획과의 융합으로 문제를 해결하는 발전과정을 개관할 수 있음은 다행한 일이다.

저자: Kovalyov, MY; Ng, CT; Cheng, TCE; AF Kovalyov, Mikhail Y.; Ng, C. T.; Cheng, T. C. Edwin
자료유형: 학술정보