[논문]작업순서와 기계 의존적인 작업준비시간을 고려한 이종병렬기계의 일정계획을 위한 효과적인 작업할당 방법을 이용한 유전알고리즘

주철민; 김병수

doi:10.7232/ieif.2012.25.3.357

작업순서와 기계 의존적인 작업준비시간을 고려한 이종병렬기계의 일정계획을 위한 효과적인 작업할당 방법을 이용한 유전알고리즘
Genetic Algorithm with an Effective Dispatching Method for Unrelated Parallel Machine Scheduling with Sequence Dependent and Machine Dependent Setup Times 원문보기

산업공학 = IE Interfaces, v.25 no.3, 2012년, pp.357 - 364

주철민 (동서대학교 산업경영공학과) , 김병수 (부경대학교 기술경영(MOT) 일반대학원)

Abstract ▼ AI-Helper

This paper considers a unrelated parallel machine scheduling problem with ready times, due times and sequence and machine-dependent setup times. The objective of this problem is to determine the allocation of jobs and the scheduling of machines to minimize the total tardy time. A mathematical model for optimal solution is derived. An in-depth analysis of the model shows that it is very complicated and difficult to obtain optimal solutions as the problem size becomes large. Therefore, a genetic algorithm using an effective dispatching method is proposed. The performance of the proposed genetic algorithm is evaluated using several randomly generated examples.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

최적화 모형을 이용한 최적해 탐색은 기계당 평균 작업수가 5개를 초과하면 현실적으로 제한된 시간에 최적해의 탐색이 어려워진다. 따라서 보다 효율적인 해의 도출을 위해 본 연구에서는 효율적인 작업할당 방식을 이용한 유전알고리즘(GA_DR)을 제시하였다. 실험으로부터 GA_DR이 작업의 기계할당 방식의 복잡함 때문에 상대 적으로 시간이 더 소요되지만 GA_SC보다 현저히 우수한 해를 도출함을 알 수 있었다.
제 2장에서 제시한 혼합정수계획 모형은 기계당 평균 5개의 작업 이상인 문제인 경우 CPLEX 등의 상용 패키지를 사용하여 제한된 시간 내에 최적해를 구하기 어렵다(제 4장 참조). 따라서 본 연구에서는 효과적인 메타휴리스틱(meta-heuristic) 알고리즘의 개발에 초점을 맞추었다.
본 연구에서는 작업순서 의존적이고 기계 의존적인 작업 준비 시간과 작업 투입가능시점 및 완료요구시점을 고려한 이종병렬기계의 일정계획문제를 다루었다. 목적함수는 총 작업완료 지연시간을 최소화하는 것이다. 최적해 도출을 위해 혼합정수 계획 최적화 모형을 제시하였다.
본 연구는 다수의 작업(Job)을 다수의 이종병렬기계(unrelated parallel machine)에 할당하는 일정계획(scheduling) 문제를 다룬다. 각 작업은 투입가능시점(job release time)과 완료요구시점 (due time)을 가지며, 작업이 완료되는 시점에 따라 작업완료지연시간(tardy time)이 발행한다.
본 연구에서는 순서 의존적이고 기계의존적인 작업 준비시간과 작업 투입가능시점 및 완료요구시점이 주어진 상황에서 총 작업완료지연시간을 최소화하는 이종병렬기계 일정계획 문제를 다룬다. 순서 의존적인 작업준비시간을 고려한 동일 병렬기계의 총 작업완료시간 최소화 문제는 NP-hard로 증명되어 있다(Nait et al.
본 연구에서는 유전알고리즘의 성능 향상을 위해 기존의 여러 연구에서 입증된 할당 구분자인 특수문자를 이용한 해의 표현과 다른 새로운 해의 표현을 제안하고 그 성능을 비교한다. 새로운 해의 표현은 기계 할당을 위한 작업의 순서만을 결정하는 단순화된 방법을 이용하여 유전알고리즘을 시행하고 적합도(fitness) 평가시 효과적인 작업할당(dispatching) 방법을 적용하여 작업의 기계할당 및 기계 내의 작업들의 순서를 결정하도록 한다.
본 연구에서는 작업순서 의존적이고 기계 의존적인 작업 준비 시간과 작업 투입가능시점 및 완료요구시점을 고려한 이종병렬기계의 일정계획문제를 다루었다. 목적함수는 총 작업완료 지연시간을 최소화하는 것이다.

제안 방법

GA_SC와 GA_DR의 상대적 비교실험을 시행하기 전에 먼저 최적해와의 절대적 성능 비교를 위해 기계당 평균 작업수는 5개인 작은 규모의 문제들에 대한 실험을 시행하였다. 기계수 2, 3, 4인 경우 생성된 각각 3개 실험 데이터에 대해 혼합정수모형을 CPLEX로 수행한 결과, 기계 2대인 경우의 첫 번째 데이터는 73.
따라서 GA_SC과 GA_DR의 상대적 성능평가를 위해 기계수를 2, 3, 4대로 고정하고, 기계당 평균 작업수를 5, 10, 20, 30개로 증가시켜 실험을 시행하였다. 각 12개의 실험 방법에 대해 각각 3개 실험데이터(instance)를 생성하여 총 36개의 실험데이터를 생성하고, 각 실험데이터에 대해 10번의 반복실험을 시행하였다. 각각의 실험데이터에 대한 총 작업수 및 계획기간은 [Table 1]와 같다.
본 연구에서는 병렬기계의 일정계획문제에 소개되는 일반적인 염색체 표현과 달리 1부터 n까지의 정수만으로 표현되는 1차원 배열의 염색체 표현을 사용한다. 단순화된 1차원 배열의 염색체를 이용하여 기계들의 작업할당 및 각 기계 내의 할당된 작업들의 작업순서를 결정하기 위해서 효과적인 작업 할당 방법을 제안한다. 염색체 내에 존재하는 숫자들은 작업 할당을 수행하는 작업순서를 의미하며, 해당 작업의 기계할당 방법은 각 기계의 작업완료시간을 기반으로 한다.
일반적으로 병렬기계 일정 계획문제의 복잡도는 기계당 평균 작업수가 늘어남에 따라 증가하게 된다. 따라서 GA_SC과 GA_DR의 상대적 성능평가를 위해 기계수를 2, 3, 4대로 고정하고, 기계당 평균 작업수를 5, 10, 20, 30개로 증가시켜 실험을 시행하였다. 각 12개의 실험 방법에 대해 각각 3개 실험데이터(instance)를 생성하여 총 36개의 실험데이터를 생성하고, 각 실험데이터에 대해 10번의 반복실험을 시행하였다.
본 연구에서는 병렬기계의 일정계획문제에 소개되는 일반적인 염색체 표현과 달리 1부터 n까지의 정수만으로 표현되는 1차원 배열의 염색체 표현을 사용한다. 단순화된 1차원 배열의 염색체를 이용하여 기계들의 작업할당 및 각 기계 내의 할당된 작업들의 작업순서를 결정하기 위해서 효과적인 작업 할당 방법을 제안한다.
일반적으로 유전알고리즘은 교차변이연산(crossover), 돌연변이연산(mutation), 재생산(reproduction)의 세 가지 유전작업들을 이용하여 유전형질을 다음세대로 계승한다. 본 연구에서도 GA_SR과 GA_DR의 실험의 일관성을 유지하기 위해 동일한 상황에서 세 가지 유전작업 방식들을 적용한다. 교차변이연산으로 하나의 교차점을 임의로 선택하고 [Figure 3]과 같이 두 부모의 유전자를 교차하여 자식을 생성하는 한점 교차변이(one cut-point crossover)연산을 사용한다.
본 연구에서는 유전알고리즘의 성능 향상을 위해 기존의 여러 연구에서 입증된 할당 구분자인 특수문자를 이용한 해의 표현과 다른 새로운 해의 표현을 제안하고 그 성능을 비교한다. 새로운 해의 표현은 기계 할당을 위한 작업의 순서만을 결정하는 단순화된 방법을 이용하여 유전알고리즘을 시행하고 적합도(fitness) 평가시 효과적인 작업할당(dispatching) 방법을 적용하여 작업의 기계할당 및 기계 내의 작업들의 순서를 결정하도록 한다. 제 2장에서는 주어진 이종병렬기계 일정계획 문제에 대한 최적화 수리모형을 제시하였다.
각각의 실험데이터에 대한 총 작업수 및 계획기간은 [Table 1]와 같다. 여기서, 기계당 평균작업수에 대한 계획기간의 생성은 작업시간과 작업준비시간의 중간값의 합인 65분에 기계당 평균 작업수를 곱한 값으로 정하였다.
유전알고리즘 파라메터 설정은 제시된 GA_SC과 GA_DR 모두 해집단의 수를 2⋅n으로 하였고, 교차변이율과 돌연변이율은 여러 가지 조합의 예비 실험결과에서 가장 좋은 성능을 보였던 0.7과 0.3으로 수행하였다.
제 2장에서 제시한 혼합정수 모형에 의한 최적해는 ILOG CPLEX 10.2을 적용하여 구하였고 두 가지 유전알고리즘은 C#을 이용하여 구현하였으며, 모든 실험은 1.86GHz Intel Core 2 Processor, 2GB RAM의 PC을 이용하여 수행되었다. 유전알고리즘 파라메터 설정은 제시된 GA_SC과 GA_DR 모두 해집단의 수를 2⋅n으로 하였고, 교차변이율과 돌연변이율은 여러 가지 조합의 예비 실험결과에서 가장 좋은 성능을 보였던 0.
따라서 본 연구에서 다루는 이종병렬기계 일정계획의 문제는 기계의 종류가 상이하여 작업준비시간이 작업 순서 및 기계에 따라 달라지며 작업시간 역시 기계에 따라 달라지는 훨씬 복잡한 상황을 다루므로 NP-hard하다. 주어진 일정계획 문제에 대해 기계별 작업 할당과 작업순서를 동시에 결정하기 위한 수리모형을 제시하고, 해를 보다 효율적으로 도출하기 위한 유전 알고리즘을 제안한다. 일반적으로 유전알고리즘의 성능을 향상시키기 위해서는 해의 효과적인 표현방법이 필요하다.
목적함수는 총 작업완료 지연시간을 최소화하는 것이다. 최적해 도출을 위해 혼합정수 계획 최적화 모형을 제시하였다. 최적화 모형을 이용한 최적해 탐색은 기계당 평균 작업수가 5개를 초과하면 현실적으로 제한된 시간에 최적해의 탐색이 어려워진다.

대상 데이터

본 연구에서 제안한 알고리즘의 성능을 평가하기 위하여 임의로 실험데이터를 생성하였다. 각 기계에서 각 작업의 작업시간은 [30, 60] 단위시간 구간 내에서, 작업준비시간은 [10, 30] 단위시간 구간 내에서 임의로 생성하였다.

데이터처리

[Table 2]에는 모든 실험 데이터의 10번의 반복에 대한 GA_ SC와 GA_DR의 해의 평균 값(mean), 평균 절대편차(Mean Absolute Deviation : MAD), 수행 시간, 그리고 GA_SC 대비 GA_DR의 RR을 정리하였다. [Table 2]의 실험 결과를 보면 GA_SC 대비 GA_DR의 RR 전체 평균이 28.
통계적으로 GA_SC 대비 GA_DR의 우수성을 검증하기 위하여 95% 신뢰구간의 평균과 Tukey HSD(Honestly Significant Difference) intervals로 기계당 작업수의 변화와 기계수의 변화에 따른 두 알고리즘의 RR에 대한 95% 신뢰구간의 평균을 도식화하였다. [Figure 5]에서 보는바와 같이 기계당 작업수나 기계 수에 크게 관계없이 우수한 감소율(RR)을 보임을 알 수 있다.

성능/효과

[Table 2]에는 모든 실험 데이터의 10번의 반복에 대한 GA_ SC와 GA_DR의 해의 평균 값(mean), 평균 절대편차(Mean Absolute Deviation : MAD), 수행 시간, 그리고 GA_SC 대비 GA_DR의 RR을 정리하였다. [Table 2]의 실험 결과를 보면 GA_SC 대비 GA_DR의 RR 전체 평균이 28.97%로 GA_DR 해가 GA_SC 해에 비해 현저히 우수하였다. 이는 특수문자를 이용한 염색체 표현을 이용하는 것에 비해, 본 연구에서 제시한 작업할당 방법을 이용한 염색체 표현을 이용하는 것이 이종병렬기계 일정계획문제에 대한 GA의 성능을 훨씬 향상 시킨다는 사실을 알 수 있다.
GA_SC와 GA_DR의 상대적 비교실험을 시행하기 전에 먼저 최적해와의 절대적 성능 비교를 위해 기계당 평균 작업수는 5개인 작은 규모의 문제들에 대한 실험을 시행하였다. 기계수 2, 3, 4인 경우 생성된 각각 3개 실험 데이터에 대해 혼합정수모형을 CPLEX로 수행한 결과, 기계 2대인 경우의 첫 번째 데이터는 73.250초, 두 번째 데이터는 430.368초, 세 번째 데이터는 9050.150초 만에 최적해를 도출하였으나, 기계 3, 4대인 경우의 모든 데이터에 대해서는 10800초(3시간)내에 최적해를 도출하지 못하였다. 도출한 최적해는 각기 33, 77, 97로 이는 GA_DR의 결과와 비교하면([Table 2] 참고), GA_DR의 절대적 성능이 규모가 제한된 문제에 대해 우수함을 알 수 있다.
, 2001; Yalaoui and Chu, 2003). 따라서 본 연구에서 다루는 이종병렬기계 일정계획의 문제는 기계의 종류가 상이하여 작업준비시간이 작업 순서 및 기계에 따라 달라지며 작업시간 역시 기계에 따라 달라지는 훨씬 복잡한 상황을 다루므로 NP-hard하다. 주어진 일정계획 문제에 대해 기계별 작업 할당과 작업순서를 동시에 결정하기 위한 수리모형을 제시하고, 해를 보다 효율적으로 도출하기 위한 유전 알고리즘을 제안한다.
실험으로부터 GA_DR이 작업의 기계할당 방식의 복잡함 때문에 상대 적으로 시간이 더 소요되지만 GA_SC보다 현저히 우수한 해를 도출함을 알 수 있었다. 또한, GA_DR은 규모가 큰 현실적인 문제에 대한 실험에서 GA_SC 대비 우수한 해를 1분 이내에 탐색하는 탁월한 효율성을 입증하였다.
따라서 보다 효율적인 해의 도출을 위해 본 연구에서는 효율적인 작업할당 방식을 이용한 유전알고리즘(GA_DR)을 제시하였다. 실험으로부터 GA_DR이 작업의 기계할당 방식의 복잡함 때문에 상대 적으로 시간이 더 소요되지만 GA_SC보다 현저히 우수한 해를 도출함을 알 수 있었다. 또한, GA_DR은 규모가 큰 현실적인 문제에 대한 실험에서 GA_SC 대비 우수한 해를 1분 이내에 탐색하는 탁월한 효율성을 입증하였다.
97%로 GA_DR 해가 GA_SC 해에 비해 현저히 우수하였다. 이는 특수문자를 이용한 염색체 표현을 이용하는 것에 비해, 본 연구에서 제시한 작업할당 방법을 이용한 염색체 표현을 이용하는 것이 이종병렬기계 일정계획문제에 대한 GA의 성능을 훨씬 향상 시킨다는 사실을 알 수 있다. 해의 탐색시간은 총 작업수가 많아질수록 증가폭이 커지나 모든 실험에 대해 GA_SC와 GA_DR 모두 1분 이내일정도로 적어 실제문제에 적용시 효율적인 일정계획의 수립이 가능할 것이다.

후속연구

이는 특수문자를 이용한 염색체 표현을 이용하는 것에 비해, 본 연구에서 제시한 작업할당 방법을 이용한 염색체 표현을 이용하는 것이 이종병렬기계 일정계획문제에 대한 GA의 성능을 훨씬 향상 시킨다는 사실을 알 수 있다. 해의 탐색시간은 총 작업수가 많아질수록 증가폭이 커지나 모든 실험에 대해 GA_SC와 GA_DR 모두 1분 이내일정도로 적어 실제문제에 적용시 효율적인 일정계획의 수립이 가능할 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	작업은 무엇을 가지며, 완료되는 시점에 따라 무엇을 발행하나요?	본 연구는 다수의 작업(Job)을 다수의 이종병렬기계(unrelated parallel machine)에 할당하는 일정계획(scheduling) 문제를 다룬다. 각 작업은 투입가능시점(job release time)과 완료요구시점 (due time)을 가지며, 작업이 완료되는 시점에 따라 작업완료지연시간(tardy time)이 발행한다. 다수로 주어진 이종병렬기계들은 그 용량이나 범용성의 정도 등에 따라 각 작업을 수행하는 속도가 다르게 주어지므로, 각 작업의 가공시간(processing time) 은 어느 기계에 할당되는지에 따라 달라진다.
	이종병렬기계는 무엇에 따라 달라지나요?	각 작업은 투입가능시점(job release time)과 완료요구시점 (due time)을 가지며, 작업이 완료되는 시점에 따라 작업완료지연시간(tardy time)이 발행한다. 다수로 주어진 이종병렬기계들은 그 용량이나 범용성의 정도 등에 따라 각 작업을 수행하는 속도가 다르게 주어지므로, 각 작업의 가공시간(processing time) 은 어느 기계에 할당되는지에 따라 달라진다. 작업준비시간(setup time) 역시 어떤 기계에 할당되느냐에 따라서도 달라질 뿐만 아니라, 해당기계에서의 작업순서에 따라서도 달라진다.
	총 작업완료지연시간을 최소화하는 이종병렬기계 일정계획의 문제는 무엇인가요?	, 2001; Yalaoui and Chu, 2003). 따라서 본 연구에서 다루는 이종병렬기계 일정계획의 문제는 기계의 종류가 상이하여 작업준비시간이 작업 순서 및 기계에 따라 달라지며 작업시간 역시 기계에 따라 달라지는 훨씬 복잡한 상황을 다루므로 NP-hard하다. 주어진 일정계획 문제에 대해 기계별 작업 할당과 작업순서를 동시에 결정하기 위한 수리모형을 제시하고, 해를 보다 효율적으로 도출하기 위한 유전 알고리즘을 제안한다.

참고문헌 (16)

Agarwal, A., Colak, C., Jacob, V., and Pirkul, H. (2006), Heuristics and augmented neural networks for task scheduling with non-identical machines, European Journal of Operational Research, 175(1), 296-317.

상세보기
Balin, S. (2011), Non-identical parallel machine scheduling using genetic algorithm, Expert Systems with Applications, 38, 6814-6821.

상세보기
Behnamian, J., Zandieh M., and Ghomi, F. (2009), Parallel-machine scheduling problems with sequence-dependent setup times using an ACO, SA and VNS hybrid algorithm, Expert Systems with Applications, 36, 9637-9644.

상세보기
Bobrowski, P. M. and Kim, S. C. (1994), The impact of sequence dependent setup time on job shop scheduling performance, International Journal of Production Research, 32, 1503-1520.

상세보기
Jou, C. (2005), A genetic algorithm with sub-indexed partitioning genes and its application to production scheduling of parallel machines, Computers and Industrial Engineering, 48, 39-54.

상세보기
Flynn, B. B. (1987), The effects of setup time on output capacity in cellular manufacturing, International Journal of Production Research, 25, 1761-1772.
Frederickson, G., Hecht, M. S., and Kim, C. E. (1978), Approximation algorithm for some routing problems, SIAM Journal on Computing, 7, 178-193.

상세보기
Gen, M., and Cheng, R. (2000), Genetic Algorithms and Engineering Optimization, New York : Wiley.
Gharehgozli, A. H., Tavakkoli-Moghaddam, R., and Zaerpour, N. (2009), A fuzzy- mixed-integer goal programming mode for a parallel-machine scheduling problem with sequence-dependent setup times and release dates, Robotics and Computer-Integrated Manufacturing, 25, 853-859.

상세보기
Holland, J. H. (1975), Adaptation in natural and artificial systems, Ann Arbor, IL : University of Michigan Press.
Hop, N. V. and Nagarur, N. N. (2004), The scheduling problem of PCBs for multiple non-identical parallel machines, European Journal of Operational Research, 158, 577-594

상세보기
Nait, T. D., Chu, C., Yalaoui, F., and Amodeo, L. (2003), A new approach for identical parallel machine scheduling with job splitting and sequence-dependent setup times based on linear programming, In International conference on industrial engineering and production management (IEPM), 3, 266-274.
Tavakkoli-Moghaddam, R., Taheri, F., Bazzazi, M., Izadi, M., and Sassani, F. (2009), Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints, Computers and Operations Research, 36, 3224-3230.

상세보기
Sveltana, A., Kravchenko, S., and Werner, F. (2001), A heuristic algorithm for minimizing mean flow time with unit setups, Information Processing Letters, 79, 291-296.

상세보기
Vallada, E. and Ruiz, R. (2011), A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times, European Journal of Operational Research, 211, 612-622.

상세보기
Yalaoui, F. and Chu, C. (2003), An efficient heuristic approach for parallel machine scheduling with job splitting and sequence-dependent setup times, IIE Transactions, 35(2), 183-190.

상세보기

저자의 다른 논문 :

LOADING...

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

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