[논문]Rate-Modifying 활동이 있는 병렬기계의 Makespan 최소화를 위한 일정 계획

조항민; 임승빈; 정인재

Rate-Modifying 활동이 있는 병렬기계의 Makespan 최소화를 위한 일정 계획
Parallel Machines Scheduling with Rate-Modifying Activities to Minimize Makespan 원문보기

산업경영시스템학회지 = Journal of society of korea industrial and systems engineering, v.30 no.2, 2007년, pp.44 - 50

조항민 (한양대학교 산업공학과) , 임승빈 (한양대학교 산업공학과) , 정인재 (한양대학교 산업공학과)

Abstract ▼ AI-Helper

This paper deals with the problem of scheduling jobs and rate-modifying activities on parallel machines. A rate-modifying activity is an activity that changes the production rate of equipment such as maintenance and readjustment. If a job is scheduled after the rate-modifying activity, then the processing time varies depending on the modifying rate of the activity. In this study, we extend the single machine problem to parallel machines problem and propose algorithms is to schedule the rate-modifying activities and jobs to minimize the makespan on parallel machines which is NP-hard. We propose a branch and bound algorithm with three lower bounds to solve medium size problems optimally. Also we develop three heuristics, Modified Longest Processing Time, Modified MULTIFIT and Modified COMBINE algorithms to solve large size problems. The test results show that branch and bound algorithm finds the optimal solution in a reasonable time for medium size problems (up to 15 jobs and 5 machines). For large size problem, Modified COMBINE and Modified MULTIFIT algorithms outperform Modified LPT algorithm in terms of solution quality.

주제어

AI 본문요약
AI-Helper

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

문제 정의

수 있게 한다. 또한, 오차 한계(error bound)를 보증하는 해법을 찾아서 하한을 개선하여 효과적으로 해를 찾게 하며 최적해를 구하기 어려운 큰 크기 문제의 해 비교 시에 활용할 수 있도록 하는 것이다.
본 논문은 병렬기계 안에서 작업 스케줄링과 rate-modifying 활동을 다루고 있다. Rate-modifying 활동은 기계의 수리(repair), 정비(maintenance), 조정(readjust) 등의 modifying 활동을 의미한다.
본 연구는 NF-hard 문제인 rate-modifying 활동이 있는 병렬기계의 makespan 최소화(p/m/Qiax)하는 알고리듬을 제안하였다.
그리고 휴리스틱은 MC0M과 MMF가 MLPT보다 더 좋은 결과를 보였다. 여기서 MC0Me MLPT의가능해를 한계로 갖는 좋은 가능해를 찾았다.

제안 방법

"그리고 실험 문제의 크기는 와 같이 job의 개수("")와 기계의 대수(m)를 작은 크기에서부터 큰 크기의 문제까지 실험한다."
Branch and bound(B&B) 알고리듬은 3개의 하한(£3) 을 제안하여 기계 5대와 job 15개까지인 중간 크기의 문제에 대해 합리적인 시간 안에 최적해를 찾았다. 그리고 더 큰 크기의 문제에 대해 Modified LPT(MLPT), Modified MULTIFIT(MMF), Modified COMBINE(MCOM) 알고리듬등을 제안하여 짧은 시간 안에 좋은 가능해를찾았다.
문제 크기에 따른 알고리듬의 사용은 job 15개와 기계 5대까지인 중간 크기까지는 branch and bound(B&B) 알고리듬으로 최적해를 구하고 휴리스틱들로 가능해를 구하였다. 그리고 큰 크기 문제는 최적해를 구할 시 많은 계산시간이 소요되어 휴리스틱들로 빠른 시간 내에 가능해 만 구하였다.
다음은 해(solution)를 비교한 것으로 중간 크기 문제인 기계 5대와 job 15개까지의 문제는 B&B로 구한 최적해와 휴리스틱들로 구한 가능해 간의 % 편차를 비교하였다. 최적해는 이 고 MLPT의 가능해는 ZNILPT, MMF 의 가능해는 zMmf, MCOM의 가능해는 zecom로_ 표현한다.
문제는 <표 1>과 같이 일양(Uniform) 분포에서 랜덤하게 발생 시킴으로써 다양한 조건에서 문제를 실험하도록 한다. 또한 랜덤 발생 범위가 작을 때 (small variance)와 클 때 (large variance)로 상황으로 구분하여 실험하도록 한다.
문제까지 실험한다. 문제 크기에 따른 알고리듬의 사용은 job 15개와 기계 5대까지인 중간 크기까지는 branch and bound(B&B) 알고리듬으로 최적해를 구하고 휴리스틱들로 가능해를 구하였다. 그리고 큰 크기 문제는 최적해를 구할 시 많은 계산시간이 소요되어 휴리스틱들로 빠른 시간 내에 가능해 만 구하였다.
본 연구에서는 Lee and Leon[9]가 다룬 단일기계 문제를 확장시켜 병렬기계에서 rate-modifying 활동의 유*무에 따라 생산성이 변화하는 makespan을 목적함수로 하는 문제에 대하여 중간 크기 문제는 branch and bound 으로 최적해를 구하고 큰 크기 문제는 Modified LPT(MLPT), Modified MULTIFIT(MMF), Modified COM-BINE(MCOM) 알고리듬들을 제안한다.
Rate-modifying 후에 할당되는 job j는 a>1이면 가공시간이 증가하고, a<1이면 가공 시간이 감소한다. 본 연구에서는 makespair을 최소화하는 m 개의 병렬기계에서 rate-modifying 활동(rm)과 job 의 스케줄을 결정하는 문제 PmSICg을 다룬다[12].
실험은 의 문제 크기마다의 조합인 8가지 조건에서 각 20 회씩 실험을 하였다.
그리고 큰 크기의 문제에서는 3가지 휴리스틱이 모두 1초 내. 외로 가능해를 찾았다. 여기서 Modified MULTIFIT(MMF)보다 Modified COMBINE (MCOM)이 초기 상한을 Modified LPT(MLPT)의 가능해를사용하기 때문에 MLPT의 계산시간만큼 더 소요된다.
큰 크기 문제는 MLPT로 구한 가능해와 그 외 휴리스틱들로 구한 가능해 간의 % 편차를 비교하였다. 이 문제의 Vp.

대상 데이터

실험은 <표 2>의 문제 크기마다<표 1>의 조합인 8가지 조건에서 각 20 회씩 실험을 하였다. 따라서 1개의 문제 크기에 160회 (20x8)를 실시하였다.<표3>은 Vp tp a 에 대한 평균 실행 시간(seconds)에 관한 결과이다.

성능/효과

00%로 MLPT의 가능해와 차이가 있다. 그리고 기계 100대와 job 1000개의 문제에서 MMF가 평균 16.75%, MCOM이 평균 16.76%로 MLPT의가능해와 차이가 있다. 여기서 MCOMe MLPT의 가능해를 한계(bound)로 갖는 좋은 가능해를 찾았다.
그리고 더 큰 크기의 문제에 대해 Modified LPT(MLPT), Modified MULTIFIT(MMF), Modified COMBINE(MCOM) 알고리듬등을 제안하여 짧은 시간 안에 좋은 가능해를찾았다. 실험 결과로 B&B는 LB3가 가장 좋은 한계이며 다음으로 LB2, LB1 순으로 최적해를 찾는 좋은 한계이다.
실험 결과로 B&B는 LB3가 가장 좋은 한계이며 다음으로 LB2, LB1 순으로 최적해를 찾는 좋은 한계이다. 그리고 휴리스틱은 MC0M과 MMF가 MLPT보다 더 좋은 결과를 보였다. 여기서 MC0Me MLPT의가능해를 한계로 갖는 좋은 가능해를 찾았다.
기계 5대와 job 15개의 문제에서 MLPT가 평균 28.12%, MMF가 평균 19.27%, MCOM이 평균 18.00%로 최적해와 차이가 있다. 그리고 <표 5>는 이 문제의 Vp, t}, %에대한 해를 유의 수준a= 0.
이 결과로 MCOM, MMFe MLPT와 비교하여 차이가 있음을 알 수 있고 MCOMe MMF와 비교하여 차이가 있다고 볼 수 없다. 따라서 MCOM과 MMF가 MLPT 보다 더 좋은 가능해를 찾는 알고리듬들임을 알 수 있다.
76%로 MLPT의가능해와 차이가 있다. 여기서 MCOMe MLPT의 가능해를 한계(bound)로 갖는 좋은 가능해를 찾았다. 그리고 <표 7>은 이 문제의 Vp, tj, a에 대한 해를 유의 수준 a = 0.
05에서 T 검정 결과 p-값이다. 이 결과로 MCOM, MMFe MLPT와 비교하여 차이가 있음을 알 수 있고 MCOMe MMF와 비교하여 차이가 있다고 볼 수 없다. 따라서 MCOM과 MMF가 MLPT 보다 더 좋은 가능해를 찾는 알고리듬들임을 알 수 있다.

후속연구

추후 연구로는 B&B를 개선하여 좀 더 큰 문제를 해결할 수 있게 한다. 또한, 오차 한계(error bound)를 보증하는 해법을 찾아서 하한을 개선하여 효과적으로 해를 찾게 하며 최적해를 구하기 어려운 큰 크기 문제의 해 비교 시에 활용할 수 있도록 하는 것이다.

참고문헌 (12)

Baker, K. R.; Introduction to Sequencing and Scheduling, 1943-, John Wiley & Sons Inc, 1974
Coffman Jr., E. G. and, Garey, M. R. and Johnson, D. S.; 'An Application of Bin-Packing to Multiprocessor Scheduling,' SIAM Journal on Computing, 7(1) : 1-17, 1978

상세보기
Ethel Mokotoff; 'An Exact Algorithm for the Identical Parallel Machine Scheduling Problem,' European Journal of Operation Research, 152 : 758-769, 2004

상세보기
Graham, R. L.; 'Bounds on Multiprocessing Timing Anomalies,' SIAM Journal on Applied mathematics, 17(2) : 416-429, 1969

상세보기
Graves, G. H. and Lee, C.-Y.; 'Scheduling Maintenance and Semi-resumable Jobs on a Single Machine,' Naval Research Logistics, 46 : 845-863, 1999

상세보기
Ho, J. C. and Wong J. S.; 'Makespan Minimization for m Parallel Identical Processors,' Naval Research Logistics, 42 : 935-948, 1995

상세보기
Lee, C. Y. and Lin, C. S.; 'Single-Machine Scheduling with maintenance and repair rate-modifying activities,' European Journal of Operation Research, 135 : 493-513, 2001

상세보기
Lee, C.-Y. and Chen, Z. L.; 'Scheduling of Jobs and Maintenance Activities on Parallel Machines,' Naval Research Logistics, 47 : 145-165, 2000

상세보기
Lee, C.- Y. and Leon, V. J.; 'Machine Scheduling with a Rate-Modifying Activity,' European Journal of Operation Research, 128 : 119-128, 2001

상세보기
Lee, C.-Y. and Massey, J. D.; 'Multiprocessor scheduling: Combining LPT and MULTIFIT,' Discrete Applied mathematics, 20 : 233-242, 1988

상세보기
Liao, C. J. and Shyur, D. L., and Lin, C. H.; 'Makespan Minimization for Two Parallel Machines with an Availability Constraint,' European Journal of Operation Research, 160 : 445-456, 2005

상세보기
Pinedo, M.; Scheduling: Theory, Algorithms, and Systems, 2nd Edition, Prentice-Hall, Englewood Cliffs, NJ, 2002

저자의 다른 논문 :

LOADING...

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

연합인증