No Access

An Optimal Preemptive Algorithm for the Single-Server Parallel-Machine Scheduling with Loading and Unloading Times

Yiwei Jiang

Department of Mathematics, Zhejiang Sci-Tech University, Hangzhou 310018, P. R. China

Corresponding author.

Search for more papers by this author

Huijuan Wang

School of Economics and Management, Zhejiang Sci-Tech University, Hangzhou 310018, P. R. China

Search for more papers by this author

, and

Ping Zhou

School of Humanities, Zhejiang Business College, Hangzhou 310053, P. R. China

Search for more papers by this author

https://doi.org/10.1142/S0217595914500390Cited by:2 (Source: Crossref)

Abstract

We study a preemptive scheduling problem on two identical parallel machines that share a common server. Each job has to be loaded by the server before being processed on one of the machines and unloaded by the server after its processing. The loading and unloading times are both equal to one time unit. The goal is to minimize the makespan. We propose a O(n log n) solution algorithm for the preemptive variant of the problem.

Keywords:

References

A. Abdekhodaee and A. Wirth , Computers and Operations Research 29 , 295 ( 2002 ) . Crossref, Web of Science, Google Scholar
A. Abdekhodaee , A. Wirth and H. Gan , Computers and Operations Research 31 , 1867 ( 2004 ) . Crossref, Web of Science, Google Scholar
A. Abdekhodaee , A. Wirth and H. Gan , Computers and Operations Research 33 , 994 ( 2006 ) . Crossref, Web of Science, Google Scholar
G. Batur, O. Karasan and M. Akturk, International Journal of Production Economics 135(2), 726 (2012). Crossref, Web of Science, Google Scholar
P. Brucker et al. , Journal of Scheduling 5 , 429 ( 2002 ) . Crossref, Web of Science, Google Scholar
M. Dawande et al. , Journal of Scheduling 8 , 387 ( 2005 ) . Crossref, Web of Science, Google Scholar
H. Gan , A. Wirth and A. Abdekhodaee , Computers and Operations Research 39 , 2242 ( 2012 ) . Crossref, Web of Science, Google Scholar
T. Ganesharajah , N. Hall and C. Sriskandarajah , Annals of Operations Research 76 , 109 ( 1998 ) . Crossref, Web of Science, Google Scholar
N. Hall , C. Potts and C. Sriskandarajah , Discrete Applied Mathematics 102 , 223 ( 2000 ) . Crossref, Web of Science, Google Scholar
J. Huet al., Parallel machine scheduling with a single server: Loading and unloading, COCOA 20138287, Lecture Notes in Computer Sciences (2013) pp. 106–116. Google Scholar
Y. Jiang , J. Dong and M. Ji , Computers and Industrial Engineering 66 , 514 ( 2013 ) . Crossref, Web of Science, Google Scholar
M. Y. Kim and Y. H. Lee , Computers and Operations Research 39 , 2457 ( 2012 ) . Crossref, Web of Science, Google Scholar
C. Koulamas, Computers and Operations Research 23(10), 945 (1996). Crossref, Web of Science, Google Scholar
S. Kravchenko and F. Werner , Mathematical and Computer Modelling 26 , 1 ( 1997 ) . Crossref, Web of Science, Google Scholar
J. Ou , X. Qi and C. Lee , Journal of Scheduling 13 , 213 ( 2010 ) . Crossref, Web of Science, Google Scholar
C. Su , Journal of Combinatorial Optimization 26 , 480 ( 2013 ) . Crossref, Web of Science, Google Scholar
G. Wang and T. C. E. Cheng , Journal of the Operational Research Society 52 , 234 ( 2001 ) . Crossref, Web of Science, Google Scholar
F. Werner and S. Kravchenko, Automation and Remote Control 71(10), 2109 (2010). Crossref, Web of Science, Google Scholar
X. Xieet al., Scheduling parallel machines with a single server, 2012 Int. Conf. Measurement, Information and Control (MIC)1 (IEEE, 2012) pp. 453–456. Google Scholar
X. Xie, Y. Zheng and Y. Li, Scheduling parallel machines with a single server: A dedicated case, 2012 Fifth Int. Joint Conf. Computational Sciences and Optimization (CSO) (IEEE, 2012) pp. 146–149. Google Scholar
Y. Yip , C. Cheng and C. Low , International Journal of Advanced Manufacturing Technology 30 , 286 ( 2006 ) . Crossref, Web of Science, Google Scholar
L. Zhang and W. Andrew , Computers and Operations Research 36 , 1529 ( 2009 ) . Crossref, Web of Science, Google Scholar