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

Weidong Li (), Jianping Li () and Tongquan Zhang ()
Additional contact information
Weidong Li: Department of Atmospheric Science, Yunnan University, Kunming 650091, P. R. China
Jianping Li: Department of Mathematics, Yunnan University, Kunming 650091, P. R. China
Tongquan Zhang: School of Mathematics and Computer Science, Yunnan Nationalities University, Kunming 650031, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2012, vol. 29, issue 05, 1-12

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: Makespan; EPTAS; FPTAS (search for similar items in EconPapers)
Date: 2012
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595912500297
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:29:y:2012:i:05:n:s0217595912500297

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595912500297

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().