[논문]패밀리 셋업이 존재하는 병렬기계 일정계획 수립

권익현; 신현준; 엄동환; 김성식

문제 정의

그러나 본 연구는 납기관련 목적함수를 갖고 있기 때문에 전체 계획대상 작업을 단순히 패밀 리 셋업군 별로 묶는 다면 상대적으로 뒤쪽에 위치 하는 패밀리 셋업군에 속하는 작업일수록 납기를 어기는 정도가 커지게 되어 좋지 못하다. 그러므로 본 논문에서는 앞에서 설명된 방식의 단점을 보안 하기 위하여 먼저 전체 계획 대상 작업을 비슷한 납기를 가지는 작업군으로 나누고, 이러한 각각의 작업군에 속하는 작업들에 대해서 패밀리군 별로 묶어 주는 방식으로 납기와 셋업 횟수를 동시에 줄 여나갈 수 있도록 한다. 세부적으로 선행계획 단계 에서는 납기의 우선순위에 따라 작업을 정렬하기 위해서 EDD(earliest due date) 규칙과 Lew와 Pinedo[15, 19]가 제안한 ATCS(apparent tardiness cost with setup) 규칙, 그리고 타부 탐색 (tabu search) 기법을 적용하였다.
본 논문에서는 이러한 주어진 상황과 가정 하에서 납기지연 가중치의 합을 최소화하는 일정 계획 을 수립하는 알고리듬을 제시한다.
따라서 작업들의 납기와 우선순위, 패밀리 셋업을 고려하여 전체 계획 대상 작업에 대한 납기지연 가중 치의 합(total weighted tardiness)을 최소로 하는 일정계획을 수립하는 것이 현실적이라 할 수 있겠 다. 본 논문은 패밀리 셋업이 존재하는 동일 병렬기 계로 이루어진 작업환경에서 납기지연 가중치의 합 을 최소화하는 일정계획을 수립하는 알고리듬을 제 시하였다.
본 연구에서는 패밀리 셋업이 존재하는 동일 병 렬기계 문제에 대한 납기지연 가중치의 합을 최소 화하기 위한 발견적 기법(heuristic)을 제안하였다. 제안된 발견적 기법은 크게 선행계획 단계와 할당 단계의 두 단계로 구성되는데, 선행계획 단계에서 는 먼저 대상 작업을 납기의 우선순위에 따라 정렬 하고 계획 구획 수(number of scheduling sections) 를 사용하여 비슷한 납기를 가지는 작업군으로 분 류하였다.

가설 설정

[그림 2]에서 현재 할당 대상 작업은 厶3이고 이와 동일한 패밀리 셋업 형태로 끝난 기계 또한 존재한다. 그러나』么에는 이미 많은 작업이 할당되어 있어 厶3가 할당된다면 납기를 어기는 정도가 납기지연 한계값。'상이 된다고 가정하자. (b)는 이러한 상황에서 동일 잔여 작업수를 적용하지 않은 경우로, 厶3와 厶4는 대상 기계 중 가공 완료시간이 가장 빠른 也에 할당되고 다음에 위치한 계획 대상 작업 % B2< B3 등은 동일한 패밀리 셋업 형태로 끝나는 기계가 존재하지 않으므로 必에 할당 되었다.
. 하나의 작업을 복수개의 작업으로 분할(job spUt) 하여 할당하는 것은 불가능하다.
o 각 기계의 임시 저장장소의 크기는 고려하지 않 는다.

제안 방법

그러나 어떠한 경우에는 납기를 어느 정도 어기는 경우가 발생하 더라도 패밀리 셋업의 형태를 먼저 고려하여 동일한 패밀리 셋업 형태로 끝나는 기계에 계속해서 작 업을 할당하는 것이 전체적인 일정계획의 측면에서 효과적일 수 있을 것이다. 그러므로 대상 작업을 할 당하는데 있어서 보다 세부적이고 명확한 기준이 필요한데 이를 위해서 본 연구에서는 납기지연 한 계값(threshold value, a)과 허용 잔여 작업수(look- ahead parameter, 를 정의하고 이를 바탕으로 할 당규칙을 적용한다.
제안된 발견적 기법은 크게 선행계획 단계와 할당 단계의 두 단계로 구성되는데, 선행계획 단계에서 는 먼저 대상 작업을 납기의 우선순위에 따라 정렬 하고 계획 구획 수(number of scheduling sections) 를 사용하여 비슷한 납기를 가지는 작업군으로 분 류하였다. 그리고 ATCS 알고리듬을 사용하여 동일 패밀리 셋업을 갖는 작업별로 패밀리군을 형성하였으며, 타부 탐색으로 세부 일정계획을 발전시켰다. 할당 단계에서는 이전 단계에서 수립된 선행계획 결과를 납기와 패밀리 셋업 횟수 등을 고려하여 각 기계에 할당할 수 있도록 납기지 연 한계값(threshold value)과 허용 잔여 작업수(look-ahead pa~ rameter)라는 모수를 적용하였다.
본 논문의 상황에서처 럼 패밀리 셋업이 존재할 때, 패밀리간의 셋업 횟수 를 줄이는 것이 허의 성능에 크게 영향을 미치는 경우에는 전자와 같은 방법을 따르는 것이 더 효율 적이다. 따라서 본 논문에서는 전자와 같은 절차를 이용하여 전체 알고리듬을 선행 계획 단계(pre-processing procedure)와 할당 단계 (allocation proce- dure)로 구성하였다. 본 연구의 특징은 선행계획 단 계에서 초기해를 구할 때, 매우 잘 계획된 일정계획 을 수립함으로써 할당 단계에서는 해의 향상을 위한 별도의 절차가 필요치 않게 한다는 점이다.
또한 계획 구획 수(A)는 2로 고정시켰고, 납기지연 한계값(a)은 실험데이터 중에서 가장 큰 패밀리 셋업 시간으로 설정하였으며 허용 잔여 작업 수((3)는 2로 고정한다. 문제의 유 형은 작업 수(沥 = (30, 50, 100), 기 계 수(%) = (3, 5, 7, 10), 패밀리 셋업 수(P) = (4, 6, 8)의 조합으 로 총 36가지로 구성하였으며, 각각의 문제들은 20 번의 반복 실험을 실시한 후 그 결과의 평균값을 제시하였다.
본 논문에서 제안된 알고리듬의 성능을 평가하기 위해 기존에 알려진 알고리듬을 비교대상으로 하여 다양한 실험을 실시하여 분석하였다. 앞서 기존 연구에서 언급하였듯이 본 연구와 동일한 상황에 대한 알고리듬은 존재하지 않으므로 이와 가장 유사 하다고 할 수 있는 Ovacik & Uzsoy[17, 18]가 제안한 RHP(rolling horizon procedure) 와 Lee & Pine- do[15] 가 제안한 ATCS 알고리듬을 비교 대안으로 정하였다.
본 논문에서는 가공 시간(3), 가중치( 約), 납기 (%), 패밀리 셋업(family setup) 시간( £)을 갖는 如개의 작업과 m개의 동일한 병렬기계에 대한 일 정계획 수립 문제를 다룬다. 모든 작업은 계획시작 시점에서 가공 가능한 것으로 가정하여 공정 가능 시간(release time)은 존재하지 않는다.
본 수치 예제는 3개의 기계, 15개의 작업과 4개의 패밀리 셋업 형태를 갖는 문제를 다룬다. 다음<표 1>은 이 문제에 대한 기초 데이터로서 대상 작업의 패밀리 타입, 납기, 가중치 및 가공 시간을 나타낸다.
이는 어느 일정 한도 이내로 납기를 어기더라도 셋업을 발생시키지 않는 것이 다른 패밀리 셋업 형태로 끝 나는 기계에 할당되어 셋업을 발생시키는 것보다 전체 일정계획의 측면에서 효과적일 수 있기 때문이다. 본 연구에서는 전체 패밀리 셋업 시간 중의 최대값을 납기지연 한계값으로 설정하였다.
실험에 필요한 데이터를 얻기 위해 작업의 가공 시간, 가중礼 패밀리 셋업 시간, 납기는 난수를 발 생시켜 각각 (1, 300), (1, 10), (300, 500), (500, 1000) 의 범위를 갖는 균일 분포(uniform distribution)를 이루도록 생성하였다. 또한 계획 구획 수(A)는 2로 고정시켰고, 납기지연 한계값(a)은 실험데이터 중에서 가장 큰 패밀리 셋업 시간으로 설정하였으며 허용 잔여 작업 수((3)는 2로 고정한다.
본 논문에서 제안된 알고리듬의 성능을 평가하기 위해 기존에 알려진 알고리듬을 비교대상으로 하여 다양한 실험을 실시하여 분석하였다. 앞서 기존 연구에서 언급하였듯이 본 연구와 동일한 상황에 대한 알고리듬은 존재하지 않으므로 이와 가장 유사 하다고 할 수 있는 Ovacik & Uzsoy[17, 18]가 제안한 RHP(rolling horizon procedure) 와 Lee & Pine- do[15] 가 제안한 ATCS 알고리듬을 비교 대안으로 정하였다. RHP는 순서 의존적인 작업준비 시간을 갖는 병렬기계 문제를 일련의 단일기계 문제로 분 할(decomposition) 하고 각각의 단일기계 문제에 대해 분지 한계법을 이용하여 납기지연 시간의 최대 값(Lmax)을 최소화하는 방법이고, ATCS 알고리듬 은 기존의 단일기계 문제에 적용했던 ATCS 알고 리듬을 병렬기계 문제로 확장한 것으로 순서 의존 적인 작업준비 시간을 갖는 병렬기계 문제에 대한 납기지연 가중치의 합을 최소화하는 방법이다.
이를 위해 전체 계획 대상 작업을 앞서 언급했던 EDD 규칙에 의해 정렬한다. 이들을 비슷한 납기를 가지는 작업군으로 분류하기 위해서는 계획 대상 작업을 구분하는 기준이 필요 한데 이를 위해 본 논문에서는 계획 시평(scheduling horizon) 과 계획 구획 수(num讪er of scheduling sections)를 정의한다. 계획 시평( T)은 계획 대상 작업의 납기 최대값(, 妇缺)과 최소값(4„血)의 차이를 계획 구획 수(人)로 나누어준 값이다.
선행계획 단 계의 첫 절차는 납기의 우선순위에 따라서 대상 작 업들을 나열하는 것이다. 이를 위해 전체 계획 대상 작업을 앞서 언급했던 EDD 규칙에 의해 정렬한다. 이들을 비슷한 납기를 가지는 작업군으로 분류하기 위해서는 계획 대상 작업을 구분하는 기준이 필요 한데 이를 위해 본 논문에서는 계획 시평(scheduling horizon) 과 계획 구획 수(num讪er of scheduling sections)를 정의한다.
본 연구에서는 패밀리 셋업이 존재하는 동일 병 렬기계 문제에 대한 납기지연 가중치의 합을 최소 화하기 위한 발견적 기법(heuristic)을 제안하였다. 제안된 발견적 기법은 크게 선행계획 단계와 할당 단계의 두 단계로 구성되는데, 선행계획 단계에서 는 먼저 대상 작업을 납기의 우선순위에 따라 정렬 하고 계획 구획 수(number of scheduling sections) 를 사용하여 비슷한 납기를 가지는 작업군으로 분 류하였다. 그리고 ATCS 알고리듬을 사용하여 동일 패밀리 셋업을 갖는 작업별로 패밀리군을 형성하였으며, 타부 탐색으로 세부 일정계획을 발전시켰다.
이러한 지표값을 계산하는 식 (2)의 우변은 세 개의 항 목으로 이루어져 있다. 첫 번째는 작업별 가중치를 가공 시간으로 나누어 주는 WSPT(weighted shortest processing time first) 규칙을 반영하는 항목으 로 가공 시간이 짧은 작업들과 가중치가 큰 작업들 을 우선적으로 계획하게 한다. 두 번째 항목은 MS(minimum slack) 규칙을 반영하는 것으로써 납 기에 대한 여유가 적은 작업이 큰 지표값을 가지게 한다.

대상 데이터

본 논문은 패밀리 셋업(family setup)이 존재하는 동일한 병렬기계들로 구성된 작업환경을 연구 대상으로 한다. 여기서 패밀리 셋업이란 순서 의존적인 작업준비 시간(sequence-dependent setup times)의 특수한 형태로서 제품의 특성이나 작업의 종류가 상이할 경우 발생하는 작업준비 시간을 의미한다.

이론/모형

본 연구에서는 이와 같은 ATCS 규칙의 단점을 보완하여 패밀리군의 순서 조정을 위해서 타부 탐 색(tabu search) 기법을 추가로 사용하였다. Glover [7, 8]에 의해 체계화된 타부 탐색은 일반적으로 복 합 최적화(combinatorial optimization)와 일정계획 수립 문제 등의 해결에 다양하게 사용되고 있다.
그러므로 본 논문에서는 앞에서 설명된 방식의 단점을 보안 하기 위하여 먼저 전체 계획 대상 작업을 비슷한 납기를 가지는 작업군으로 나누고, 이러한 각각의 작업군에 속하는 작업들에 대해서 패밀리군 별로 묶어 주는 방식으로 납기와 셋업 횟수를 동시에 줄 여나갈 수 있도록 한다. 세부적으로 선행계획 단계 에서는 납기의 우선순위에 따라 작업을 정렬하기 위해서 EDD(earliest due date) 규칙과 Lew와 Pinedo[15, 19]가 제안한 ATCS(apparent tardiness cost with setup) 규칙, 그리고 타부 탐색 (tabu search) 기법을 적용하였다.

성능/효과

본 연구에서는 제안된 알고리듬의 객관적인 성능 평가를 위해 RHP와 ATCS 알고리듬을 이용하여 비교 실험을 수행^였고 다양한 실험을 통해 제안 된 알고리듬 우수성을 입증하였다. 추후 연구로는 작업에 대한 공정 가능 시간(release time)0] 존재하는 경우 이를 고려할 수 있는 방법과 작업을 기 계에 할당하는 과정에서 작업 분할(job split)을 고려할 수 있는 방법 등에 대한 연구가 필요하다.
<표 2>에서는 RHP, ATCS와 제안된 알고리듬 의 수행 결과에 대한 비교값을 나타내었다.<표 2> 에서 알 수 있듯이 본 논문에서 제안한 알고리듬이 기존의 비교대상 알고리듬보다 좋은 결과를 얻고 있다는 것을 보여준다. 이는 본 논문의 알고리듬이 선행계획과 할당 단계를 통해 납기와 패밀리 셋업 의 회수를 동시에 고려하는 효과적인 계획수립을 하는 반면에, RHP는 계획되어진 작업군을 한꺼번 에 하나의 기계에 할당하기 때문에 비효율적이라 할 수 있다.
[그림 기에서 제안된 알고리듬은 나머지 알고리듬보다 모든 경우에 우월한 수행도를 보이고 있다. 특히 제안된 알고리듬은 다른 알고리듬에 비해 패밀리 셋업수의 증가에 따른 목적함수의 증가 치가 상대적으로 완만함을 알 수 있으며, 이로 인해 제안된 알고리듬은 패밀리 셋업이 존재하는 환경에서 우수한 결과를 나타낸다고 할 수 있겠다.

후속연구

즉, 병렬기계 문제를 다룬 기존 연구가운데에서 패밀리 셋업을 가정한 논문은 많지 않으며 이러한 논문이 고려하고 있는 목적함수는 작업완료 시간의 최대값 (GD이나 패밀리 셋업의 횟수 등을 최소화하는 경우가 대부분이다. 그러나 보다 현실적이고 실제 생 산 환경을 잘 반영하기 위해서는 납기관련 목적함 수를 고려하는 것이 더 바람직할 것이고 이에 본 연구에서처럼 납기지연 가중치의 합을 최소화하는 문제에 보다 큰 의미를 부여할 수 있을 것이다.
추후 연구로는 작업에 대한 공정 가능 시간(release time)0] 존재하는 경우 이를 고려할 수 있는 방법과 작업을 기 계에 할당하는 과정에서 작업 분할(job split)을 고려할 수 있는 방법 등에 대한 연구가 필요하다. 또한 실제 현장에서 적용이 가능하도록 동적인 상황 에서 계획수립(dynamic scheduling)0] 가능하도록 하는 연구가 이루어져야 한다.
선행계획 단계는 각 작업을 기계에 할당하기 전에 계획 대상 작업의 순서를 정해준다. 본 논문의 상황과 같이 패밀리 셋업이 존재하는 경우 될 수 있는 한 같은 패밀리에 속하는 작업들을 하나의 패 밀리로 묶어서 동일한 패밀리 셋업군 별로 계획을 수립하면 셋업 횟수를 줄일 수 있는 효과를 나타낼 것이다. 그러나 본 연구는 납기관련 목적함수를 갖고 있기 때문에 전체 계획대상 작업을 단순히 패밀 리 셋업군 별로 묶는 다면 상대적으로 뒤쪽에 위치 하는 패밀리 셋업군에 속하는 작업일수록 납기를 어기는 정도가 커지게 되어 좋지 못하다.
표에서 최적의 人값은 일정하지 않으며, 이러한 현상은 실험을 위한 데이터 생성 시 각각의 문제별 데이터가 동일하지 않음으로 인해 발생하는 결과이다. 그러므로 일정계획의 대상이 되는 작업 의 환경과 특성에 따라서 a와 B 및 /!의 값을 적 절히 조절해 주면서 제안된 알고리듬을 적용한다면, 보다 우수한 결과를 얻을 수 있으리라 판단된다.
본 연구에서는 제안된 알고리듬의 객관적인 성능 평가를 위해 RHP와 ATCS 알고리듬을 이용하여 비교 실험을 수행^였고 다양한 실험을 통해 제안 된 알고리듬 우수성을 입증하였다. 추후 연구로는 작업에 대한 공정 가능 시간(release time)0] 존재하는 경우 이를 고려할 수 있는 방법과 작업을 기 계에 할당하는 과정에서 작업 분할(job split)을 고려할 수 있는 방법 등에 대한 연구가 필요하다. 또한 실제 현장에서 적용이 가능하도록 동적인 상황 에서 계획수립(dynamic scheduling)0] 가능하도록 하는 연구가 이루어져야 한다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증

패밀리 셋업이 존재하는 병렬기계 일정계획 수립
Scheduling for Parallel Machines with Family Setup Times 원문보기

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

참고문헌 (23)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

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

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

선택된 텍스트

연합인증

패밀리 셋업이 존재하는 병렬기계 일정계획 수립 Scheduling for Parallel Machines with Family Setup Times 원문보기

Abstract ▼ AI-Helper

주제어

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

문제 정의

가설 설정

제안 방법

대상 데이터

이론/모형

성능/효과

후속연구

참고문헌 (23)

이 논문을 인용한 문헌

저자의 다른 논문 :

권익현 (10) 김성식 (59)

관련 콘텐츠

원문 보기

원문 URL 링크

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

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

선택된 텍스트

패밀리 셋업이 존재하는 병렬기계 일정계획 수립
Scheduling for Parallel Machines with Family Setup Times 원문보기

AI 본문요약
AI-Helper