다중 서버의 이동 시간을 고려하는 병렬 머신 스케줄링
Parallel Machine Scheduling Considering the Moving Time of Multiple Servers
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
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.
Abstract
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.
참고문헌 (24)
- J. 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, "Makespan minimization in online scheduling with machine eligibility", Ann. Ope. res, 204, pp.189~222 (2013)
- X. Xie, "Scheduling Parallel Machines with a Single Server", IEEE Intl. Conf. on MIC, pp.453~456 (2012)
- 정균락, "다중 서버를 사용하는 병렬 머신 스케줄링을 위한 효율적인 알고리즘", 한국컴퓨터정보학회논문지, 19(6), pp.101~108 (2014), 한국컴퓨터정보학회
- A. H. Abdekhodaee, "Scheduling parallel machines with a single server: some solvable cases and heuristics", Computers and Operation Research, 29, pp.295~315 (2002)
- A. H. Abdekhodaee, "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, "Scheduling parallel machines with a single server: the general case", Computers and Operation Research, 33, pp.994~1009 (2006)
- H. S. Gan, "A branch-and-price algorithm for scheduling parallel machines with a single server", Computers and Operation Research, 39, pp.2242~2247 (2012)
- F. Werner, "Parallel Machine Scheduling with a Single Server", Mathematics and Computer Modelling, 26, pp.1~11 (1997)
- N. G. Hall, "Parallel machine scheduling with a common server", Discrete Applied Mathematics, 102, pp.223~243 (2000)
- P. Brucker, "Complexity results for parallel machine problems with a single server", J. of Scheduling, 5, pp.429~457 (2002)
- J. Hu, "Parallel Machine Scheduling with a Single Server: Loading and Unloading", LNCS, 8287, pp.106~116 (2013)
- X. Xie, "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, "Parallel Machine Scheduling with Multiple Unloading Servers", J. of Scheduling, 13(3), pp.213~226 (2009)
- F. Werner, "Scheduling with Multiple Servers", Automation and Remote Control, 71(10), pp.2109~2121 (2010)
- C. Wu, "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, "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, "Makespan minimization for two parallel machines with unavailability constraints", IEEE International Conference on Systems, Man, and Cybernetics (SMC), pp.601~606 (2016)
- Z. Xu, "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, "Scheduling two parallel machines with maintenance-dependent availabilities", Computer and Operation Research, 72, pp.13~42 (2016)
- L. Y. Wang, "Unrelated parallel machine scheduling with deteriorating maintenance activities to minimize the total completion time", Optim. Letters (2012)
- C. W. Lin, "Ant colony optimization for unrelated parallel machine scheduling", Intl. J. of Adv. Manuf. Tech (2013)
- V. Kayvanfar, "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, 23(10), pp.945~956 (1996)