An efficient algorithm for scheduling parallel machines with multiple servers (다중 서버를 사용하는 병렬 머신 스케줄링을 위한 효율적인 알고리즘)

Kyun Rak Chong (정균락)

An efficient algorithm for scheduling parallel machines with multiple servers

Journal of The Korea Society of Computer and Information
Abbr : JKSCI
2014, 19(6), pp.101-108
Publisher : The Korean Society Of Computer And Information
Research Area : Engineering > Computer Science

Kyun Rak Chong ¹

¹홍익대학교

Accredited

ABSTRACT

The parallel machine scheduling is to schedule each job to exactly one parallel machine so thatthe total completion time is minimized. It is used in various manufacturing system areas such assteel industries, semiconductor manufacturing and plastic industries. Each job has a setup phaseand a processing phase. A removal phase is needed in some application areas. A processing phaseis performed by a parallel machine alone while a setup phase and a removal phase are performedby 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 forscheduling, the bottleneck in the server increases the total completion time. Even though thenumber of parallel machines is increased, the total completion time is not reduced significantly. Inthis paper, we have proposed an efficient algorithm for the parallel machine scheduling usingmultiple servers and considering setup, processing and removal phases. We also have investigatedexperimentally how the number of servers and the number of parallel machines affect the totalcompletion time.

KEYWORDS

parallel machine scheduling, the total completion time, NP-hard

Citation status

* References for papers published after 2023 are currently being built.

[journal] J. H. Lee / 2013 / A tabu search algorithm for unrelated parallel machine scheduling with sequence- and machine-dependent setups: minimizing total tardiness / Intl. J. of Adv. Manuf. Tech.

[journal] K. Lee / 2013 / Makespan minimization in online scheduling with machine eligibility / Ann. Ope. res. 204 : 189~222

[journal] C. P. Koulamas / 1996 / Scheduling two parallel semiautomatic machines to minimize machine interference / Computers and operation Research 23(10) : 945~956

[journal] N. G. Hall / 2000 / Parallel machine scheduling with a common server / Discrete Applied Mathematics 102 : 223~243

[journal] A. H. Abdekhodaee / 2002 / Scheduling parallel machines with a single server: some solvable cases and heuristics / Computers and Operation Research 29 : 295~315

[confproc] X. Xie / 2012 / Scheduling Parallel Machines with a Single Server / IEEE Intl. Conf. on MIC : 453~456

[journal] J. Ou / 2009 / Parallel Machine Scheduling with Multiple Unloading Servers / J. of Scheduling 13(3) : 213~226

[journal] F. Werner / 2010 / Scheduling with Multiple Servers / Automation and Remote Control 71(10) : 2109~2121

[journal] F. Werner / 1997 / Parallel Machine Scheduling with a Single Server / Mathematicsl and Computer Modelling 26 : 1~11

[journal] P. Brucker / 2002 / Complexity results for parallel machine problems with a single server / J. of Scheduling 5 : 429~457

[journal] A. H. Abdekhodaee / 2004 / Equal processing and equal setup time cases of scheduling parallel machines with a single server / Computers and Operation Research 31 : 1867~1889

[journal] J. Hu / 2013 / Parallel Machine Scheduling with a Single Server : Loading and Unloading / LNCS 8287 : 106~116

[journal] A. H. Abdekhodaee / 2006 / Scheduling parallel machines with a single server: the general case / Computers and Operation Research 33 : 994~1009

[journal] H. S. Gan / 2012 / A branch-and-price algorithm for scheduling parallel machines with a single server / Computers and Operation Research 39 : 2242~2247

[confproc] X. Xie / 2012 / Scheduling Parallel Machines with a Single Server: a Dedicated Case / Fifth Intl. Joint Conf. on Computational Science and Optimization : 146~149

[journal] C. Bussema / 2006 / Greedy multiprocessor server scheduling / Operations Research Letters 34 : 451~458

[journal] C. Su / 2013 / Online LPT algorithms for parallel machines scheduling with a single server / J. Comb. Optim. 26 : 480~488

[journal] L. Y. Wang / 2012 / Unrelated parallel machine scheduling with deteriorating maintenance activities to minimize the total completion time / Optim. Letters

[journal] C. W. Lin / 2013 / Ant colony optimization for unrelated parallel machine scheduling / Intl. J. of Adv. Manuf. Tech.

KJCKorea
Journal Central

Journal of The Korea Society of Computer and Information 2023 KCI Impact Factor : 0.65