No Access

TWO APPROXIMATION SCHEMES FOR SCHEDULING ON PARALLEL MACHINES UNDER A GRADE OF SERVICE PROVISION

WEIDONG LI

Department of Atmospheric Science, Yunnan University, Kunming 650091, P. R. China

Search for more papers by this author

JIANPING LI

Department of Mathematics, Yunnan University, Kunming 650091, P. R. China

Corresponding author.

Search for more papers by this author

, and

TONGQUAN ZHANG

School of Mathematics and Computer Science, Yunnan Nationalities University, Kunming 650031, P. R. China

Search for more papers by this author

https://doi.org/10.1142/S0217595912500297Cited by:12 (Source: Crossref)

Abstract

We consider the offline scheduling problem to minimize the makespan on m parallel and identical machines with certain features. Each job and machine are labeled with the grade of service (GoS) levels, and each job can only be executed on the machine whose GoS level is no more than that of the job. In this paper, we present an efficient polynomial-time approximation scheme (EPTAS) with running time O(n log n) for the special case where the GoS level is either 1 or 2. This partially solves an open problem posed in (Ou et al., 2008). We also present a simpler full polynomial-time approximation scheme (FPTAS) with running time O(n) for the case where the number of machines is fixed.

Keywords:

References

N. Alonet al., Journal of Scheduling 1, 55 (1998). Crossref, Google Scholar
A. Fishkin, K. Jansen and M. Mastrolilli, Algorithmica 51, 183 (2008). Crossref, Web of Science, Google Scholar
R. L. Grahamet al., Annals of Discrete Mathematics 5, 287 (1979). Crossref, Google Scholar
E. Horowitz and S. Sahni, Journal of the ACM 23, 317 (1976). Crossref, Web of Science, Google Scholar
H. C. Hwang, S. Y. Chang and K. Lee, Computers & Operations Research 31, 2055 (2004). Crossref, Web of Science, Google Scholar
Jansen, K (2009). Parameterized approximation scheme for the multiple knapsack problem. In Proc. 20th ACM-SIAM Symposium on Discrete Algorithms. pp. 665–674; SIAM Journal on Computing, 39, 1392–1412 . Google Scholar
K. Jansen and L. Porkolab, Mathematics of Operations Research 26, 324 (2001). Crossref, Web of Science, Google Scholar
M. Ji and T. C. E. Cheng, Information Processing Letters 108, 171 (2008). Crossref, Web of Science, Google Scholar
Y. Jiang, Journal of Combinatorial Optimization 16, 28 (2008). Crossref, Web of Science, Google Scholar
A. Kulik and H. Shachnai, Information Processing Letters 110, 707 (2010). Crossref, Web of Science, Google Scholar
H. W. Lenstra, Mathematics of Operations Research 8, 538 (1983). Crossref, Web of Science, Google Scholar
J. Y. T. Leung and C. L. Li, International Journal of Production Economics 116, 251 (2008). Crossref, Web of Science, Google Scholar
M. Mastrolilli, Journal of Scheduling 6, 521 (2003). Crossref, Web of Science, Google Scholar
J. Ou, J. Y. T. Leung and C. L. Li, Naval Research Logistics 55, 328 (2008). Crossref, Web of Science, Google Scholar
Z. Tan and A. Zhang, Theoretical Computer Science 412, 246 (2011). Crossref, Web of Science, Google Scholar
G. J. Woeginger, INFORMS Journal on Computing 12, 57 (2000). Crossref, Web of Science, Google Scholar
G. J. Woeginger, Information Processing Letters 109, 341 (2009). Crossref, Web of Science, Google Scholar
A. Zhang, Y. Jiang and Z. Tan, Theoretical Computer Science 410, 3597 (2009). Crossref, Web of Science, Google Scholar
P. Zhou, Y. Jiang and Y. He, Applied Mathematics: A Journal of Chinese Universities (Series A) 22, 275 (2007). Web of Science, Google Scholar