작업자 공유가 가능한 라인밸런싱 문제에 대한 유전 알고리즘 응용

Abstract

본 연구에서는 작업, 작업자의 Station 할당이 고정되어 있지 않고 필요에 따라 작업 혹은 작업자가 Station을 이동하는 것이 가능한 DLB(Dynamic Line Balancing) 문제를 다룬다.

본 연구에서 고려하는 직렬 라인에서는 Station이 모두 직렬로 연결 되어있고 각 Station에도 작업이 이미 할당되어 있는 상태를 가정한다 그리고 작업의 부하가 걸린 Station으로 이전 Station의 작업자들이 이동하여 부하를 줄이고 작업이 완료된다면 다시 원래 Station으로 돌아오는 작업자 공유가 가능한 문제의 상황을 가진다. 각 Station에서는 작업가능한 인원의 수와 전체 라인에서 가용 가능한 총 작업자의 수가 제한되어 있다. 이전 Station의 작업자가 다음 Station으로 가서 협업을 진행하기 때문에 첫번째 Station의 작업자들은 도움을 받지 못하여, 첫번째 Station의 작업자들은 스스로 첫번째 Station의 업무를 완성해야 한다. 또한 마지막 Station의 작업자들은 다음 Station이 없기 때문에 이전 Station에게만 도움을 받을 뿐 도움을 주지 못한다.

첫번째 Station의 작업자들과 마지막 Station의 작업자들을 제외한 Station들의 작업자들은 3가지의 업무를 Cycle Time내에서 실행하게 되는데 본인의 Station의 작업을 스스로 하는 경우, 이전 Station의 작업자들이 도움을 주러 와서 협업을 진행하는 경우 마지막으로 다음 Station으로 작업을 이동하여 다음 Station의 작업자와 작업을 협업하는 경우이다. 본 연구의 목적은 각 Station에서의 발생하는 세가지의 시간의 합을 각 Station에서 일하는 작업자의 Cycle Time으로 지정하고 이 값들 중 최대값을 최소화하는 전체 Line Cycle Time를 찾는 것을 목적함수로 설정하는 수리모형을 제시하였다.

본 연구는 수리모형의 구조가 NP-Hard에 속하는 문제이므로 이를 풀기 위해 유전 알고리즘을 방법론으로 채택하여 Station에 할당된 일을 마치는데 걸린 시간에 대한 작업함수의 형태에 따라 실험을 실행하였다. 알고리즘의 성능을 비교 분석하기 위해 수리모형을 통해 만든 하한 값을 기존 연구의 정리를 변형하여 2가지의 형태로 만들고 이를 {\mathrm{LB}}^1과 {\mathrm{LB}}^2로 정의하고 GA 결과 값과 비교 분석을 진행하였다. 실험 에서는 작업자수에 대한 작업시간의 함수가 선형인 경우, concave인 경우, convex인 경우에 GA와 하한과의 오차율을 계산하였다. 그 결과 각각의 경우에서 Station의 수가 작은 경우에 {\mathrm{LB}}^2와의 오차율이 6.64%, 17.73%, 30.68%로 나타났다. Station 수가 큰 경우에 대한 오차율은 각각 10.14%, 21.03%, 33.37%로 나타났다. 즉 station의 수가 적고 작업시간 함수가 선형 혹은 concave인 경우에 GA가 더 잘 작동하는 것으로 나타났다.