[논문]작업조 구성과 작업량 평준화를 고려한 작업할당문제에 관한 연구

심동현; 이영훈

문제 정의

1단계 초기해 구성을 통해 K개의 작업은 I개의 그룹으로 묶이게 되는데, I 개 그룹으로 묶인 작업에 대하여 작업조 변경을 통해 해의 개선을 시도한다. 끝으로, 실행가능성을 유지하는 범위 내에서 작업할당의 변경을 통한 해의 개선을 시도한다. 작업조 변경과 작업할당의 변경을 통해 더 이상 해의 개선이 발생하지 않을 경우 두 번째 발견적 기법의 절차가 종료된다.
본 연구의 문제는 작업조를 구성하고 구성한 작업조에 일정 범위 이내의 작업을 할당하는 3차원의 할당문제이다. 본 논문에서 제시한 혼합정수계획 모형은 NP-Complete의 문제로서, 해를 구하는데 많은 계산시간이 필요하기 때문에 제시한 문제에 대하여 빠른 시간내에 근사해를 구하는 발견적 기법의 알고리즘을 제시하고자 한다.
본 연구에서는 ILOG사의 OPL Studio를 활용하여 최적해를 구한 결과와 근사해를 구하는 알고리즘의 결과를 비교하여 해법의 수행도를 평가하기로 한다. 문제에 대한 최적해와 발견적 기법의 근사해, 발견적 기법으로 산출된 작업조 구성결과를 이용한 최적해를 각각 비교하여 발견적 기법의 성과도를 평가한다.
할당문제와 GAP 및 다차원 할당문제에 대한 종합적인 서베이는 Pentico(2007)를 참조할 수 있다. 본 연구에서는 문제의 유형보다는 균형적인 분배를 얻고자 하는 할당문제에 대한 효율적인 해법 제시에 중점을 두어 고찰하고자 한다.
본 연구에서는 작업조를 구성하고 작업을 할당하면서 불량 비용을 최소화하고 작업조의 작업량을 평준화하는 수리모형과 그 해법 알고리즘을 제안하고자 한다.
본 연구에서는 작업조를 구성할 수 있는 조장과 조원이 있고, 조장-조원-작업의 조합에 따른 불량비용이 다른 상황에서 비용을 최소화하고, 각 작업조의 작업량을 허용편차 이내로 하는 것을 목표로 하는 혼합정수계획 수리모형을 수립하고, 수립한 문제를 해결하기 위한 발견적인 해법 알고리즘을 제안하였다. 제안한 알고리즘은 크게 2단계로 구성되는데 1단계에서 실행 가능한 초기해를 구성하고, 2단계에서는 1단계에서 구한 초기해를 이용하여 해의 개선을 수행한다.
여러 연구를 보면, 효율을 최대화 하거나 비용을 최소화 하도록 작업자에게 작업을 할당하는 문제에 대한 연구는 많이 이루어졌으나, 작업조를 구성하여 작업을 할당하는 문제와 작업량 평준화를 고려한 연구는 거의 없다. 본 연구에서는 조장과 조원, 작업의 조합에 따라 불량비용이 다르게 발생하고 한 작업조가 여러 개의 작업을 수행할 수 있는 상황하에서 각 작업조의 작업량 편차 허용치를 주고 비용의 발생을 최소화하는 수리모형을 제시하고 근사해를 구하는 알고리즘을 제시한다.
본 연구의 문제는 작업조를 구성하고 구성한 작업조에 일정 범위 이내의 작업을 할당하는 3차원의 할당문제이다. 본 논문에서 제시한 혼합정수계획 모형은 NP-Complete의 문제로서, 해를 구하는데 많은 계산시간이 필요하기 때문에 제시한 문제에 대하여 빠른 시간내에 근사해를 구하는 발견적 기법의 알고리즘을 제시하고자 한다.
하나의 작업은 오직 하나의 작업조에 의해 수행되어야 하고, 조장과 조원으로 구성된 작업조는 모든 작업을 수행할 때까지 바꾸지 않는다. 조장과 조원을 짝지어 작업조를 구성하고 모든 작업을 구성한 작업조에게 할당하되 작업수행의 결과로 발생하는 비용을 최소화하는 것을 목표로 한다. 또한, 각 작업조가 할당받은 총 작업량은 평균작업량 대비 편차허용치(α) 범위 이내에 있어야 하는데, 평균작업량(AW : Average Workload)이란 각 작업조가 평균적으로 수행하는 작업량을 의미하는 것으로써 총 작업시간(#)을 작업조의 수(I) 로 나눈 것이다.

가설 설정

이다. 각 작업은 작업조에 의해 수행되는데 작업조는 1명의 조장과 1명의 조원으로 구성되고, 활용가능한 조장과 조원의 수는 각각 I명으로 같다고 가정한다. 불량비용은 조장과 조원, 작업의 조합에 따라 정해지는데 조장 i와 조원 j가 작업 k를 수행할 경우의 비용은 C_ijk라고 정의한다.
본 모형에서는 미리 수립된 생산계획에 의해 수행되어야 할 작업이 총 K개로 정해져 있고, 각 작업에는 작업에 소요되는 작업소요 시간이 정해져 있다고 가정하는데 작업 k의 작업소요시간은 작업하는 작업조에 상관없이 P_k이다. 각 작업은 작업조에 의해 수행되는데 작업조는 1명의 조장과 1명의 조원으로 구성되고, 활용가능한 조장과 조원의 수는 각각 I명으로 같다고 가정한다.

제안 방법

각 실험에서의 편차허용치(α)는 평균작업량의 5%, 10%로 변화시켜 실험을 수행하였다.
본 연구에서는 ILOG사의 OPL Studio를 활용하여 최적해를 구한 결과와 근사해를 구하는 알고리즘의 결과를 비교하여 해법의 수행도를 평가하기로 한다. 문제에 대한 최적해와 발견적 기법의 근사해, 발견적 기법으로 산출된 작업조 구성결과를 이용한 최적해를 각각 비교하여 발견적 기법의 성과도를 평가한다. 실험을 위한 데이터의 조건으로 작업에 소요되는 작업소요시간(P_k)은 [5, 10] 범위의 정수를 무작위로 생성하여 사용하였고, 조장과 조원, 작업의 조합으로 발생하는 불량비용은 [10, 50] 범위의 정수를 무작위로 생성하여 사용하였다.
실험을 위한 데이터의 조건으로 작업에 소요되는 작업소요시간(P_k)은 [5, 10] 범위의 정수를 무작위로 생성하여 사용하였고, 조장과 조원, 작업의 조합으로 발생하는 불량비용은 [10, 50] 범위의 정수를 무작위로 생성하여 사용하였다. 문제의 크기(Size)는 조장, 조원, 작업의 수로서 4-4-10, 6-6-20, 8-8-30, 10-10-40, 12-12-50으로 증가시켜 각 크기별 10회씩 실험을 수행하였다. 실험의 입력변수로 사용한 조장, 조원, 작업의 조합에 따른 불량률과 작업소요시간은 각 실험에 있어 Rando Data를 생성하여 사용하였다.
문제의 크기(Size)는 조장, 조원, 작업의 수로서 4-4-10, 6-6-20, 8-8-30, 10-10-40, 12-12-50으로 증가시켜 각 크기별 10회씩 실험을 수행하였다. 실험의 입력변수로 사용한 조장, 조원, 작업의 조합에 따른 불량률과 작업소요시간은 각 실험에 있어 Rando Data를 생성하여 사용하였다. 각 실험에서의 편차허용치(α)는 평균작업량의 5%, 10%로 변화시켜 실험을 수행하였다.
본 연구에서는 작업조를 구성할 수 있는 조장과 조원이 있고, 조장-조원-작업의 조합에 따른 불량비용이 다른 상황에서 비용을 최소화하고, 각 작업조의 작업량을 허용편차 이내로 하는 것을 목표로 하는 혼합정수계획 수리모형을 수립하고, 수립한 문제를 해결하기 위한 발견적인 해법 알고리즘을 제안하였다. 제안한 알고리즘은 크게 2단계로 구성되는데 1단계에서 실행 가능한 초기해를 구성하고, 2단계에서는 1단계에서 구한 초기해를 이용하여 해의 개선을 수행한다. 제안한 알고리즘은 실험결과에서 보여주듯이 문제의 크기에 상관없이 최적해 대비 높은 성과도의 해를 빠른 시간 내에 구할 수 있었다.
일정한 순서로 조장에 대하여 최상의 조원과 짝짓는 경우 일대일로 할당이 이루어지기 때문에 순서가 나중일수록 최악의 작업조로 구성될 가능성이 높아진다. 최악의 작업조로 구성될 경우의 비용의 증가를 낮추기 위하여 GAP_i를 계산하고 GAP_i가 가장 큰 조장에 대하여 가장 좋은 작업조를 구성할 수 있는 조원으로 작업조를 구성한다. 또한, 작업조를 구성한 조장과 조원은 작업조 구성대상에서 제외하고 A-2, A-3의 절차를 거치면서 모든 조장과 조원이 작업조를 구성하게 된다.

데이터처리

실험결과를 요약하면, 혼합정수계획모형의 특징으로 문제의 크기가 증가함에 따라 최적해를 구하는 계산시간이 급격히 늘어나는 것을 확인할 수 있고, 크기 A5이상의 문제부터 일정 시간내에 최적해를 산출할 수 없어 제한시간내의 가장 좋은 해를 산출하여 발견적 기법의 근사해와 비교하였다. 발견적 기법으로 문제의 크기에 상관없이 1초 미만의 짧은 시간내에 근사해를 구할 수 있었으며, 편차허용치 5%와 10%에서 각각 최적해 대비 평균 12.

성능/효과

제안한 알고리즘은 실험결과에서 보여주듯이 문제의 크기에 상관없이 최적해 대비 높은 성과도의 해를 빠른 시간 내에 구할 수 있었다. 1단계에서 구한 초기해의 결과가 발견적 기법의 성과에 큰 영향을 주었고, 해의 개선단계를 통한 개선은 비교적 작았던 것으로 미루어 볼 때, 해를 개선하는 발견적 기법의 2단계를 보완한다면 전체 알고리즘의 성능이 향상될 것으로 생각된다.
해의 개선횟수와 초기해의 성과도, 해의 개선율의 결과로 볼 때, 편차 허용치가 작으면 실행가능한 초기해를 구하는데 비용이 높은 초기해를 구성하고 해의 개선단계에서 높은 개선 성과를 보인다고 판단할 수 있다. 또한, 전체적으로 최적해 대비 초기해의 성과도가 매우 높고 개선율이 비교적 낮은 것으로 미루어 볼때, 초기해 구성이 발견적 기법의 성과도에 큰 영향을 미치는 것으로 판단할 수 있다.
실험결과를 요약하면, 혼합정수계획모형의 특징으로 문제의 크기가 증가함에 따라 최적해를 구하는 계산시간이 급격히 늘어나는 것을 확인할 수 있고, 크기 A5이상의 문제부터 일정 시간내에 최적해를 산출할 수 없어 제한시간내의 가장 좋은 해를 산출하여 발견적 기법의 근사해와 비교하였다. 발견적 기법으로 문제의 크기에 상관없이 1초 미만의 짧은 시간내에 근사해를 구할 수 있었으며, 편차허용치 5%와 10%에서 각각 최적해 대비 평균 12.42%, 11.72%의 차이를 나타냈다. 제시한 발견적 기법은 초기해 구성과 해의 개선 2단계로 구성되기 때문에, 초기해의 성과도와 개선율을 확인할 필요가 있다.
42%의 차이를 나타냈다. 발견적 기법으로 얻은 작업조를 이용하여 최적해를 구한 결과 전체 최적해 대비 평균 7.43%의 차이를나타냈고, 발견적 기법의 작업할당 단계에서 추가적으로 4.63%의 차이를 발생시킨 것으로 나타났다. 총 50회의 실험 중 해의 개선을 수행하지 않은 횟수는 10회였고, 해의 개선을 수행한 40회의 실험을 통해 작업조 변경 2회, 작업할당 변경 95회로 총 97회의 개선을 수행한 것으로 나타났다.
발견적 기법으로 얻은 작업조를 이용하여 최적해를 구한 결과 전체 최적해 대비 평균 8.41%의 차이를 나타냈고, 발견적 기법의 작업할당 단계에서 추가적으로 3.04%의 차이를 발생시킨 것으로 나타났다. 총 50회의 실험 중 해의 개선을 수행하지 않은 횟수는 20회였고, 해의 개선을 수행한 30회의 실험을 통해 작업조 변경 2회, 작업할당 변경 53회로 총 55회의 개선을 수행한 것으로 나타났다.
제안한 알고리즘은 크게 2단계로 구성되는데 1단계에서 실행 가능한 초기해를 구성하고, 2단계에서는 1단계에서 구한 초기해를 이용하여 해의 개선을 수행한다. 제안한 알고리즘은 실험결과에서 보여주듯이 문제의 크기에 상관없이 최적해 대비 높은 성과도의 해를 빠른 시간 내에 구할 수 있었다. 1단계에서 구한 초기해의 결과가 발견적 기법의 성과에 큰 영향을 주었고, 해의 개선단계를 통한 개선은 비교적 작았던 것으로 미루어 볼 때, 해를 개선하는 발견적 기법의 2단계를 보완한다면 전체 알고리즘의 성능이 향상될 것으로 생각된다.
[Table 12]에는 편차허용치를 평균작업량의 10%로 설정하여 각 크기별 10회씩 총 50회 실험의 실험치들과 성과도를 표시하였다. 총 50회의 실험 중 1회에 걸쳐 발견적 기법으로 근사해를 구할 수 없었고, 발견적 기법으로 최적해 대비 평균 11.72%의 차이를 나타냈다.
[Table 10]에는 편차허용치를 평균작업량의 5%로 설정하여 각 크기별 10회씩 총 50회 실험의 실험치들과 성과도를 표시하였다. 총 50회의 실험 중 3회에 걸쳐 발견적 기법으로 근사해를 구할 수 없었고, 발견적기법으로 최적해 대비 평균 12.42%의 차이를 나타냈다. 발견적 기법으로 얻은 작업조를 이용하여 최적해를 구한 결과 전체 최적해 대비 평균 7.
63%의 차이를 발생시킨 것으로 나타났다. 총 50회의 실험 중 해의 개선을 수행하지 않은 횟수는 10회였고, 해의 개선을 수행한 40회의 실험을 통해 작업조 변경 2회, 작업할당 변경 95회로 총 97회의 개선을 수행한 것으로 나타났다. 이에 대한 결과가 [Table 11]에 표시되어 있다.
04%의 차이를 발생시킨 것으로 나타났다. 총 50회의 실험 중 해의 개선을 수행하지 않은 횟수는 20회였고, 해의 개선을 수행한 30회의 실험을 통해 작업조 변경 2회, 작업할당 변경 53회로 총 55회의 개선을 수행한 것으로 나타났다. 이에 대한 결과가 [Table 13]에 표시되어 있다.
본 연구에서는 작업자의 구성에 상관없이 작업시간에 동일하다고 가정하였으나 실제로는 작업시간 또한 달라질 수 있으며 기간에 따라 수행해야 하는 작업이 달라지고 활용할 수 있는 작업자가 변화하는 경우로 연구의 범위를 확장할 수 있다. 해를 구하는 알고리즘도 유전자알고리즘, 시뮬레이티드 어닐링, 타부서치 등과 같은 메타 휴리스틱을 이용하여 본 연구에서 수립한 문제를 해결하는 연구가 가능하다. 다만 문제의 정 의시 실제적으로 필요한 데이터를 합리적으로 수집 가능하여 적용가능성이 있는가에 대한 분석과 해법이 적절한 계산 시간 내에 종료될 수 있는가를 고려하는 실용성에 대한 분석도 따라야 한다.
초기해의 성과도는 편차 허용치 5%일 경우에 10%일 경우보다 나쁘지만 해의 개선율이 높은 것을 확인할 수 있다. 해의 개선횟수와 초기해의 성과도, 해의 개선율의 결과로 볼 때, 편차 허용치가 작으면 실행가능한 초기해를 구하는데 비용이 높은 초기해를 구성하고 해의 개선단계에서 높은 개선 성과를 보인다고 판단할 수 있다. 또한, 전체적으로 최적해 대비 초기해의 성과도가 매우 높고 개선율이 비교적 낮은 것으로 미루어 볼때, 초기해 구성이 발견적 기법의 성과도에 큰 영향을 미치는 것으로 판단할 수 있다.

후속연구

본 연구에서 제안한 알고리즘은 공평한 작업배분과 작업량 편차를 고려해야 하는 모든 작업환경에 활용할 수 있고, 주작업자와 보조작업자로 작업조를 구성하여 작업을 수행해야 하는 경우에 그 활용가능성이 높다. 그리고, 작업자가 생각하는 적정수준의 작업량 편차 허용치와 의사결정자를 포함한 경영진이 생각하는 적정수준의 작업량 편차 허용치가 다를 수 있는데, 본 연구에서 수립한 수리모델은 각각의 경우에 대한 비용의 변화를 확인할 수 있는 장점이 있다.
본 연구에서는 작업자의 구성에 상관없이 작업시간에 동일하다고 가정하였으나 실제로는 작업시간 또한 달라질 수 있으며 기간에 따라 수행해야 하는 작업이 달라지고 활용할 수 있는 작업자가 변화하는 경우로 연구의 범위를 확장할 수 있다. 해를 구하는 알고리즘도 유전자알고리즘, 시뮬레이티드 어닐링, 타부서치 등과 같은 메타 휴리스틱을 이용하여 본 연구에서 수립한 문제를 해결하는 연구가 가능하다.
72%의 차이를 나타냈다. 제시한 발견적 기법은 초기해 구성과 해의 개선 2단계로 구성되기 때문에, 초기해의 성과도와 개선율을 확인할 필요가 있다. [Figure 3]에는 편차 허용치와 문제의 크기에 따른 최적해 대비 초기해의 성과도와 개선율을 표시하였다.

핵심어	질문	논문에서 추출한 답변
	불량은 무엇이라고 할 수 있는가?	작업조를 구성하는 작업자들은 해당 작업에 대한 경력과 숙련도, 작업에 대한 선호도, 동반 작업자에 대한 선호도 등을 가지며, 이런 이유로 어떻게 작업조를 구성하고 구성한 작업조에 어떤 작업을 할당하느냐의 결과에 따른 불량이 발생하게 된다. 불량은 일종의 비용으로서, 작업경력이 많은 조장과 조수로 구성된 작업조는 그렇지 않은 작업조보다 불량품을 발생시킬 확률이 낮을 것이다. 또한 작업자는 자신이 주로 경험하지 않았던 작업에 대해서는 더 높은 불량을 발생시킬 것이다.
	할당 문제는 언제 처음 사용되었는가?	할당 문제(Assignment problem)는 Votaw and Orden(1952)에 의해 처음 사용되어 Kuhn(1955)에 의해 Hungarian method라고 알려진 해법이 소개되면서 할당문제의 수많은 변형과 확장문제들이 소개되었고 실질적인 해법이 소개되었다. 일대일 할당문제가 확장되어일대다의 할당이가능한 경우를GAP이라고 하며 Cattrysse and Van Wassenhove(1992)의 서베이 논문에 수많은 변형 및 확장문제와 다양한 해법이 소개되었다.
	본 연구에서 수립한 수리모델이 해결할 수 있는 어려움은?	그리고, 작업자가 생각하는 적정수준의 작업량 편차 허용치와 의사결정자를 포함한 경영진이 생각하는 적정수준의 작업량 편차 허용치가 다를 수 있는데, 본 연구에서 수립한 수리모델은 각각의 경우에 대한 비용의 변화를 확인할 수 있는 장점이 있다. 특히 작업량편차 허용의 범위를 정하는 문제는 실제문제에서 적용할 때 적절한 값을 설정하기에 많은 어려움이 있다. 본 연구에서 제안하는 알고리즘이 짧은 시간내에 해를 구하는데 중점을 두는 이유 중의 하나는 적절한 편차허용범위를 설정하기 위해 여러 차례의 시행착오를 거치는 과정이 필요하기 때문이다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

작업조 구성과 작업량 평준화를 고려한 작업할당문제에 관한 연구
The Workload Assignment Problem in consideration of the Worker Pairing and the Workload Balancing 원문보기

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

데이터처리

성능/효과

후속연구

질의응답

참고문헌 (13)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

작업조 구성과 작업량 평준화를 고려한 작업할당문제에 관한 연구 The Workload Assignment Problem in consideration of the Worker Pairing and the Workload Balancing 원문보기

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

가설 설정

제안 방법

데이터처리

성능/효과

후속연구

질의응답

참고문헌 (13)

이 논문을 인용한 문헌

저자의 다른 논문 :

이영훈 (33)

관련 콘텐츠

원문 보기

원문 URL 링크

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

작업조 구성과 작업량 평준화를 고려한 작업할당문제에 관한 연구
The Workload Assignment Problem in consideration of the Worker Pairing and the Workload Balancing 원문보기

AI 본문요약
AI-Helper