다중 서버를 사용하는 병렬 머신 스케줄링을 위한 효율적인 알고리즘

다국어 초록 (Multilingual Abstract)

The parallel machine scheduling is to schedule each job to exactly one parallel machine so that the total completion time is minimized. It is used in various manufacturing system areas such as steel industries, semiconductor manufacturing and plastic industries. Each job has a setup phase and a processing phase. A removal phase is needed in some application areas. 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. Most of previous researches used a single server and considered only a setup phase and a processing phase. If a single server is used for scheduling, the bottleneck in the server increases the total completion time. Even though the number of parallel machines is increased, the total completion time is not reduced significantly. In this paper, we have proposed an efficient algorithm for the parallel machine scheduling using multiple servers and considering setup, processing and removal phases. We also have investigated experimentally how the number of servers and the number of parallel machines affect the total completion time.

참고문헌 (Reference)

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

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

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

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

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

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

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

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

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

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

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

12 C. Su, "Online LPT algorithms for parallel machines scheduling with a single server" 26 : 480-488, 2013

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

14 C. Bussema, "Greedy multiprocessor server scheduling" 34 : 451-458, 2006

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

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

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

18 J. H. Lee, "A tabu search algorithm for unrelated parallel machine scheduling with sequence- and machine-dependent setups: minimizing total tardiness" 2013

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