오픈숍 일정계획 문제의 다항시간 알고리즘 (A Polynomial Time Algorithm for Open Shop Scheduling Problem)

서지정보

· 발행기관 : 한국정보기술학회
· 수록지 정보 : 한국정보기술학회논문지 / 12권 / 4호 / 105 ~ 115페이지
· 저자명 : 이상운

초록

본 논문은 다항시간 알고리즘이 알려져 있지 않아 NP-완전 (NP-complete) 문제로 분류된 오픈숍 일정계획 문제의 근사 해를 구하는 다항시간 알고리즘을 제안하였다. 오픈숍 일정계획은 개의 기계와 개의 작업이 존재하고, 개 공정의 수행시간이 주어진 상태에서 총 작업수행시간을 최소로 하도록 작업의 공정 순서와 기계에 투입되는 순서 모두를 결정하는 문제이다. 본 논문에서는 모든 작업은 공정수행시간이 최대인 공정을 우선하여 동시에 시작되며, 이후부터는 가장 먼저 시작할 수 있는 공정을 먼저 수행하는 방법을 적용하였다. 또한, 특정 조건을 만족하는 경우에 한해 임계경로 상의 공정 위치 변경으로 총 작업수행시간을 최소로 하는 해를 개선하였다. 6개의 데이터에 제안된 알고리즘을 적용한 결과 4개 데이터는 해 개선 과정을 수행하지 않았으며, 2개 데이터만 해 개선 과정을 수행하여 최적 해를 구하였다.

영어초록

This paper proposes a polynomial time algorithm designed to obtain near-optimal solution to NP-complete open shop scheduling problem. The open shop scheduling problem is a scheduling problem where given machines, jobs, and processing time, job orders and input sequence are determined in such a way that the processing time is minimized. The algorithm proposed in this paper commences simultaneous execution of all jobs while that of those with the maximum processing time shall be a priority, after which remaining jobs are executed in an order. This paper also improves on the makespan minimizing solution by switching job location on a critical path when certain criteria are met. When applied to 6 data, the proposed algorithm has executed optimization process on two of them in order to derive the optimal solutions.

참고자료

· 없음