Parallel Machine Scheduling Considering the Moving Time of Multiple Servers = 다중 서버의 이동 시간을 고려하는 병렬 머신 스케줄링

다국어 초록 (Multilingual 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.

목차 (Table of Contents)

• Abstract
• I. Introduction
• II. Related Works
• III. Proposed Method
• IV. Performance Evaluation
• V. Conclusion
• REFERENCES

참고문헌 (Reference)

1 정균락, "다중 서버를 사용하는 병렬 머신 스케줄링을 위한 효율적인 알고리즘" 한국컴퓨터정보학회 19 (19): 101-108, 2014

2 J. H. Lee, "tabu search algorithm for unrelated parallel machine scheduling with sequenceand machine-dependent setups: minimizing total tardiness" 2013

3 M.-A. Hassan, "Valid inequalities for unrelated parallel machines scheduling with precedence constraints" 677 (677): 677-682, 2016

4 L. Y. Wang, "Unrelated parallel machine scheduling with deteriorating maintenance activities to minimize the total completion time" 2012

5 F. Werner, "Scheduling with Multiple Servers" 71 (71): 2109-2121, 2010

6 C. P. Koulamas, "Scheduling two parallel semiautomatic machines to minimize machine interference" 23 (23): 945-956, 1996

7 J. He, "Scheduling two parallel machines with maintenance-dependent availabilities" 72 : 13-42, 2016

8 A. H. Abdekhodaee, "Scheduling parallel machines with a single server: the general case" 33 : 994-1009, 2006

9 A. H. Abdekhodaee, "Scheduling parallel machines with a single server: some solvable cases and heuristics" 29 : 295-315, 2002

10 X. Xie, "Scheduling Parallel Machines with a Single Server: a Dedicated Case" 146-149, 2012

11 X. Xie, "Scheduling Parallel Machines with a Single Server" 453-456, 2012

12 N. G. Hall, "Parallel machine scheduling with a common server" 102 : 223-243, 2000

13 J. Hu, "Parallel Machine Scheduling with a Single Server: Loading and Unloading" 8287 : 106-116, 2013

14 F. Werner, "Parallel Machine Scheduling with a Single Server" 26 : 1-11, 1997

15 J. Ou, "Parallel Machine Scheduling with Multiple Unloading Servers" 13 (13): 213-226, 2009

16 Z. Xu, "Mixed 0–1 programming model for three parallel machines scheduling problem with machine-dependent unavailable constraints" 1-4, 2016

17 K. Lee, "Makespan minimization in online scheduling with machine eligibility" 204 : 189-222, 2013

18 K. Abdellafou, "Makespan minimization for two parallel machines with unavailability constraints" 601-606, 2016

19 V. Kayvanfar, "Intelligent water drops algorithm on parallel machines scheduling" 1-5, 2015

20 A. H. Abdekhodaee, "Equal processing and equal setup time cases of scheduling parallel machines with a single server" 31 : 1867-1889, 2004

21 P. Brucker, "Complexity results for parallel machine problems with a single server" 5 : 429-457, 2002

22 C. W. Lin, "Ant colony optimization for unrelated parallel machine scheduling" 2013

23 C. Wu, "An effective estimation of distribution algorithm for solving uniform parallel machine scheduling problem with precedence constraints" 2626-2632, 2016

24 H. S. Gan, "A branch-and-price algorithm for scheduling parallel machines with a single server" 39 : 2242-2247, 2012