[논문]Parallel Machine Scheduling Considering the Moving Time of Multiple Servers

Chong, Kyun-Rak

doi:10.9708/jksci.2017.22.10.101

Parallel Machine Scheduling Considering the Moving Time of Multiple Servers 원문보기

韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information, v.22 no.10, 2017년, pp.101 - 107

Chong, Kyun-Rak (Dept. of Computer Engineering, Hongik University)

Abstract ▼ AI-Helper

In this paper, we study the problem of parallel machine scheduling considering the moving time of multiple servers. The parallel machine scheduling is to assign jobs to parallel machines so that the total completion time(makespan) is minimized. Each job has a setup phase, a processing phase and a removal phase. A processing phase is performed by a parallel machine alone while a setup phase and a removal phase are performed by both a server and a parallel machine simultaneously. A server is needed to move to a parallel machine for a setup phase and a removal phase. But previous researches have been done under the assumption that the server moving time is zero. In this study we have proposed an efficient algorithm for the problem of parallel machine scheduling considering multiple server moving time. We also have investigated experimentally how the number of servers and the server moving time affect the total completion time.

주제어

AI 본문요약
AI-Helper

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

문제 정의

현재 할당될 작업을 j라 하자. 또 SQ에서 사용 가능 시간이 가장 빠른 서버를 S_i라 하고, MSQ에서 사용 가능 시간이 가장 빠른 병렬 머신을 Mk라 하자. 서버 S_i와 병렬 머신 M_k가 작업 j의 준비 과정을 시작할 수 있는 가장 빠른 시간은 etS(i)에다 서버 Si가 병렬 머신 M_k로 이동하는 시간 m_ik를 더한 시간과 etM(k)를 비교해서 이중 큰 쪽이 된다.
과거의 연구들은 단일 서버를 사용하는 연구가 주류를 이루었고, 다수의 서버를 사용하는 경우에도 서버의 이동 시간은 고려되지 않았다. 본 연구에서는 다중 서버를 사용하고 서버의 이동 시간을 고려하는 병렬 머신 스케줄링을 위한 효율적인 알고리즘을 제안하였다. 또 서버 부하를 고려하여 다양한 데이터를 생성하여 서버의 수와 서버 이동 시간에 따라 작업들이 완료되는 최종 시간이 어떻게 변하는지 실험을 통해 분석하였다.
본 연구에서는 다중 서버와 동일 병렬 머신들을 사용하고, 서버의 이동 시간과 작업의 준비 시간, 처리 시간과 제거 시간을 모두 고려하는 병렬 머신 스케줄링 문제를 위한 효율적인 알고리즘을 제안하였다. 또 서버 부하를 고려하여 다양한 데이터를 생성하고 서버의 수와 서버 이동 시간에 따라 작업들이 완료되는 최종 시간이 어떻게 변하는지 실험을 통해 분석하였다.
작업의 처리가 끝나면 제거 과정을 시행하게 되는데 제거 과정은 바로 시행할 필요는 없고 나중에 서버가 시간이 있을 때 시행하면 된다. 이 문제의 목적은 주어진 조건을 모두 만족하면서 모든 작업들의 총 완료 시간을 최소로 하는 스케줄을 찾는 것이다.

가설 설정

1. 서버와 병렬 머신의 개수, 작업의 개수와 작업 시간들은 처음부터 고정되어 있고 중간에 변하지 않는다.
4. 서버 S_i가 작업을 처리하기 위해 시작 위치에서 병렬 머신 M_k로 이동하는 시간이 m_ik이면, 서버가 병렬 머신 M_k에서 시작 위치로 돌아오는 시간도 m_ik라고 가정한다.
계수 smtc는 0, 5, 10, 20을 사용하였는데 smtc = 0이면 서버이동 시간은 없음을 의미한다. 또 각 서버가 시작 위치에서 같은 병렬 머신으로 이동하는 시간은 동일하다고 가정하였다. 작업의 수는 1,000개를 사용하였고, 작업의 준비 시간과 처리 시간은 [24]에서와 같이 서버 부하(load)를 사용하여 임의로 생성되었다.
병렬 머신의 수는 30을 사용하였고, 서버의 수(S)는 1, 2, 3, 4, 5 를 사용하였다. 서버 i가 시작 위치에서 병렬 머신 k로 이동하는 시간 m_ik = smtc*k로 가정하였다. 계수 smtc는 0, 5, 10, 20을 사용하였는데 smtc = 0이면 서버이동 시간은 없음을 의미한다.

제안 방법

본 연구에서는 다중 서버와 동일 병렬 머신들을 사용하고, 서버의 이동 시간과 작업의 준비 시간, 처리 시간과 제거 시간을 모두 고려하는 병렬 머신 스케줄링 문제를 위한 효율적인 알고리즘을 제안하였다. 또 서버 부하를 고려하여 다양한 데이터를 생성하고 서버의 수와 서버 이동 시간에 따라 작업들이 완료되는 최종 시간이 어떻게 변하는지 실험을 통해 분석하였다.
본 연구에서는 다중 서버를 사용하고 서버의 이동 시간을 고려하는 병렬 머신 스케줄링을 위한 효율적인 알고리즘을 제안하였다. 또 서버 부하를 고려하여 다양한 데이터를 생성하여 서버의 수와 서버 이동 시간에 따라 작업들이 완료되는 최종 시간이 어떻게 변하는지 실험을 통해 분석하였다.
먼저 두 대의 병렬 머신을 사용하는 대표적인 연구를 보면, [5]에서는 각 작업이 준비 시간과 처리 시간만을 가질 때 총완료 시간을 최소로 하는 스케줄링 문제가 강한 NP-하드임을 보이고 정수프로그래밍을 사용하여 이 문제를 해결하는 방법을 제시하였다. 또 특수한 경우로 모든 작업에 대해 처리 시간이 준비 시간보다 작거나 같을 때와 준비 시간과 처리 시간의 합이 모두 같을 경우를 위한 다항 시간 최적 알고리즘을 제안하였다. [6]에서는 처리 시간이 모두 같고 준비 시간이 모두 처리 시간 보다 작거나 같은 경우와 준비 시간이 모두 같고 각 작업의 처리 시간이 다른 작업의 준비 시간과 처리 시간의 합보다 작거나 같은 경우도 NP-완비임을 보이고 휴리스틱들을 제안하였다.
[20]에서 도구 교환이나 주기적 유지보수 같은 비가동 제약 조건을 고려한 두 대의 병렬 머신에서 총 완료 시간을 최소로 하는 병렬 머신 스케줄링이 연구되었다. 문제의 크기가 작은 경우에는 혼합 0-1 프로그래밍이 사용되었고, 문제의 크기가 큰 경우에는 LPT 방법을 비롯한 여러 가지 휴리스틱을 개발하고 실험을 통해 비교분석하였다.
또 MRQ에서 작업의 제거를 가장 빨리할 수 있는 병렬 머신을 y라 하면, 서버는 i와 q, 병렬 머신은 x와 y가 있으므로 서버와 병렬 머신의 조합은 다음 네 가지 경우가 생기게 된다. 제안 알고리즘은 이 네 가지 경우 중 실행 가능 시간이 가장 빠른 경우를 선택해서 실행한다.
제안된 알고리즘은 C 언어를 사용해서 PC에서 구현되었고, 서버의 수와 서버의 이동 시간이 총 완료 시간에 어떤 영향을 미치는 지 실험을 통해 분석하였다. 실험을 위해 데이터는 다음과 같이 생성되었다.
[14]에서는 다수의 언로딩 서버를 사용하고 각 작업은 처리 시간과 제거 시간만을 고려하는데 제거 시간은 모든 작업이 같다고 가정하였다. 최소 처리 시간을 갖는 작업부터 스케줄하면 최악의 경우 성능 비율이 2임을 보였고, 이 문제를 해결하기 위한 휴리스틱 알고리즘들을 제안하였다. [15]에서는 각 작업의 준비 시간과 처리 시간을 고려하였는데 고정된 수의 병렬 머신과 서버가 주어졌을 때 총 완료 시간을 최소로 하는 스케줄링 문제가 NP-하드임을 보였다.

대상 데이터

또 각 서버가 시작 위치에서 같은 병렬 머신으로 이동하는 시간은 동일하다고 가정하였다. 작업의 수는 1,000개를 사용하였고, 작업의 준비 시간과 처리 시간은 [24]에서와 같이 서버 부하(load)를 사용하여 임의로 생성되었다. 서버 부하는 준비 시간의 합을 처리 시간의 합으로 나눈 값으로 정의되는데, 서버 부하가 L일 때 처리 시간이 구간 [0, P]에서 임의로 생성되면 준비 시간은 구간 [0, L*P]에서 생성된다.

데이터처리

제거 시간은 준비 시간과 같은 구간에서 임의로 생성되었다. 서버 부하는 L=0.05, 0.5 두 가지 경우를 고려하였는데, 각 경우에 대해 10개씩 임의로 데이터를 생성하여 평균 결과를 측정하였다.

성능/효과

2. 작업은 한 개의 병렬 머신에만 할당될 수 있으며, 서버와 병렬 머신은 동시에 두 개 이상의 작업을 처리할 수 없다.
3. 작업의 준비, 처리, 제거 과정들은 모두 한번 시작되면 완료될 때까지 실행되어야 하며 중간에 중지시켰다가 다시 시작할 수 없다.
7% 밖에 감소하지 않았다. smtc가 커질수록 서버의 수가 증가하면 총 완료 시간이 서버의 수가 1인 경우에 비해 상대적으로 더 많이 감소하였다. 실험 결과를 보면 smtc가 20일 때 서버의 수가 2, 3, 4, 5로 증가하면 서버의 수가 1인 경우에 비해 총 완료 시간이 각각 56.
05일 때 서버의 수와 서버 이동 시간에 대한 총 완료 시간의 변화가 그래프로 그려져 있다. 실험 결과를 보면 smtc가 0인 경우는 서버의 수가 1일 때의 총 완료 시간에 비해 서버의 수가 2, 3, 4, 5로 증가하면 총 완료 시간이 각각 53.5%, 43.1%, 39.5%, 37.8%가 된다. L=0.
5일 때 서버의 수와 서버 이동 시간에 대한 총 완료 시간의 변화가 그래프로 그려져 있다. 실험 결과를 보면 smtc가 0인 경우는 서버의 수가 1일 때의 총 완료 시간에 비해 서버의 수가 2, 3, 4, 5로 증가하면 총 완료시간이 각각 50%, 33.4%, 25%, 20%로 이상적으로 감소하고 있다. 즉 서버의 수가 S가 되면 총 완료시간이 1/S이 되는 것을 알 수 있다.
smtc가 커질수록 서버의 수가 증가하면 총 완료 시간이 서버의 수가 1인 경우에 비해 상대적으로 더 많이 감소하였다. 실험 결과를 보면 smtc가 20일 때 서버의 수가 2, 3, 4, 5로 증가하면 서버의 수가 1인 경우에 비해 총 완료 시간이 각각 56.6%, 41.5%, 32.7%, 27.5%로 감소하고 있다. 또 L=0.
smtc가 커질수록 서버의 이동 시간이 길어져 서버의 수가 S가 되면 총 완료시간이 1/S보다 약간 커짐을 나타내고 있다. 실험 결과에 의하면 smtc가 20일 때 서버의 수가 2, 3, 4, 5로 증가하면 서버의 수가 1인 경우에 비해 총 완료 시간이 각각 53.1%, 35.9%, 27.1%, 21.8%로 감소하고 있다.
[15]에서는 각 작업의 준비 시간과 처리 시간을 고려하였는데 고정된 수의 병렬 머신과 서버가 주어졌을 때 총 완료 시간을 최소로 하는 스케줄링 문제가 NP-하드임을 보였다. 특수한 경우로 모든 작업의 처리 시간과 준비 시간이 같을 때 문제 해결을 위한 다항 시간 알고리즘을 제안하였고, 모든 작업의 준비 시간이 1이고 서버의 수가 병렬 머신의 수보다 한 대 적을 때는 의사 다항 시간에 해결됨을 보였다. [4]에서는 준비 시간, 처리 시간, 제거 시간을 모두 고려한 스케줄링 문제를 위한 효율적인 휴리스틱을 제안하고 서버의 수와 병렬머신의 수를 증가시키면서 총 완료 시간이 단축되는 비율을 서버 부하(load)가 다른 다양한 데이터를 사용하여 분석하였다.

후속연구

본 연구에서 얻은 실험 결과는 서버 이동 시간과 작업들의 총 완료 시간을 고려할 때 몇 대의 서버들을 사용하는 것이 합리적인 가를 결정하는데 활용될 것으로 기대된다.
향후 연구 과제로는 각 서버의 이동 시간과 병렬 머신의 성능이 동일하지 않을 경우 총 완료 시간을 최소로 하는 효율적인 알고리즘의 개발이 필요한 것으로 사료된다.

참고문헌 (24)

J. H. Lee, J. M. Yu and D. H. Lee, "A tabu search algorithm for unrelated parallel machine scheduling with sequenceand machine-dependent setups: minimizing total tardiness, " Intl. J. of Adv. Manuf. Tech., 2013.
K. Lee, J. Y.-T. Leung and M. L. Pinedo, " Makespan minimization in online scheduling with machine eligibility," Ann. Ope. res., vol. 204, pp. 189-222, 2013.

상세보기
X. Xie, H. Zhou, Y. Li, and Y. Zheng, "Scheduling Parallel Machines with a Single Server,"IEEE Intl. Conf. on MIC, pp. 453-456, 2012.
K. Chong, "An efficient algorithm for scheduling parallel machines with multiple servers," Journal of the Korea Society of Computer Information, vol. 19, no. 6, pp. 101-108, 2014.
A. H. Abdekhodaee and A. Wirth, "Scheduling parallel machines with a single server: some solvable cases and heuristics," Computers and Operation Research 29, pp. 295-315, 2002.

상세보기
A. H. Abdekhodaee, A. Wirth and H. S. Gan, "Equal processing and equal setup time cases of scheduling parallel machines with a single server," Computers and Operation Research 31, pp. 1867-1889, 2004.

상세보기
A. H. Abdekhodaee, A. Wirth and H. S. Gan, "Scheduling parallel machines with a single server: the general case," Computers and Operation Research 33, pp. 994-1009, 2006.

상세보기
H. S. Gan, A. Wirth and A. H. Abdekhodaee, "A branch-and-price algorithm for scheduling parallel machines with a single server," Computers and Operation Research 39, pp. 2242-2247, 2012.

상세보기
F. Werner and S. A. Kravchenko, "Parallel Machine Scheduling with a Single Server," Mathematics and Computer Modelling, vol. 26, pp. 1-11, 1997.
N. G. Hall, C. N. Potts and C. Sriskandarajah, "Parallel machine scheduling with a common server,"Discrete Applied Mathematics, vol. 102, pp. 223-243, 2000.

상세보기
P. Brucker, C. Dhaenens-Flipo, S. Knust, S. A. Kravchchenko, and F. Werner, "Complexity results for parallel machine problems with a single server," J. of Scheduling, vol. 5, pp. 429-457, 2002.

상세보기
J. Hu, Q. Jhang, J. Dong, and Y. Jiang, "Parallel Machine Scheduling with a Single Server: Loading and Unloading," LNCS 8287, pp. 106-116, 2013.
X. Xie, Y. Li, and Y. Zheng, "Scheduling Parallel Machines with a Single Server: a Dedicated Case," Fifth Intl. Joint Conf. on Computational Science and Optimization, pp. 146-149, 2012.
J. Ou, X. Qi, and C. Y. Lee, "Parallel Machine Scheduling with Multiple Unloading Servers," J. of Scheduling, vol. 13, no. 3 pp. 213-226, 2009.
F. Werner and S. A. Kravchenko, "Scheduling with Multiple Servers," Automation and Remote Control, vol. 71, no. 10, pp. 2109-2121, 2010.

상세보기
C. Wu, L. Wang and X. Zheng, "An effective estimation of distribution algorithm for solving uniform parallel machine scheduling problem with precedence constraints," 2016 IEEE Congress on Evolutionary Computation (CEC), pp. 2626 - 2632, 2016.
M.-A. Hassan, I. Kacem, S. Martin and I. M. Osman, "Valid inequalities for unrelated parallel machines scheduling with precedence constraints," International Conference on Control, Decision and Information Technologies (CoDIT) pp. 677-682, 2016.
K. Abdellafou and Q. Korbaa, "Makespan minimization for two parallel machines with unavailability constraints," IEEE International Conference on Systems, Man, and Cybernetics (SMC), pp. 601-606, 2016.
Z. Xu, A. Liu and Q. Wang, "Mixed 0-1 programming model for three parallel machines scheduling problem with machine-dependent unavailable constraints," 13th International Conference on Service Systems and Service Management (ICSSSM), pp. 1-4, 2016.
J. He, Q. Li and D. Xu, "Scheduling two parallel machines with maintenance-dependent availabilities," Computer and Operation Research 72, pp. 13-42, 2016.
L. Y. Wang, X. Huang, P. Ji and E. M. Feng, "Unrelated parallel machine scheduling with deteriorating maintenance activities to minimize the total completion time ," Optim. Letters, 2012.
C. W. Lin, Y. K. Lin and H. T. Hsieh, "Ant colony optimization for unrelated parallel machine scheduling," Intl. J. of Adv. Manuf. Tech., 2013.
V. Kayvanfar, E. Teymourian and K. Alizadeh, " Intelligent water drops algorithm on parallel machines scheduling," International Conference on Industrial Engineering and Operations Management (IEOM) pp. 1-5, 2015.
C. P. Koulamas, "Scheduling two parallel semiautomatic machines to minimize machine interference," Computers and operation Research, vol. 23, no. 10, pp.945-956, 1996.

상세보기

표제어: 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

연합인증