ONLINE ALGORITHMS FOR SCHEDULING WITH MACHINE ACTIVATION COST
Yong He,
Shuguang Han and
Yiwei Jiang ()
Additional contact information
Yong He: Department of Mathematics, Zhejiang University, Hangzhou 310027, P. R. China
Shuguang Han: Department of Mathematics, Zhejiang University, Hangzhou 310027, P. R. China
Yiwei Jiang: Faculty of Science, Zhejiang Sci-Tech University, Hangzhou 310018, China
Asia-Pacific Journal of Operational Research (APJOR), 2007, vol. 24, issue 02, 263-277
Abstract:
In this paper, we consider a variant of the classical parallel machine scheduling problem. For this problem, we are givenmpotential identical machines to non-preemptively process a sequence of independent jobs. Machines need to be activated before starting to process, and each machine activated incurs a fixed machine activation cost. No machines are initially activated, and when a job is revealed the algorithm has the option to activate new machines. The objective is to minimize the sum of the makespan and activation cost of machines. We first present two optimal online algorithms with competitive ratios of 3/2 and 5/3 form = 2, 3 cases, respectively. Then we present an online algorithm with a competitive ratio of at most 2 for generalm ≥ 4, while the lower bound is 1.88.
Keywords: Parallel machine scheduling; machine activation cost; online algorithm; competitive analysis (search for similar items in EconPapers)
Date: 2007
References: View complete reference list from CitEc
Citations:
Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595907001231
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:24:y:2007:i:02:n:s0217595907001231
Ordering information: This journal article can be ordered from
DOI: 10.1142/S0217595907001231
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 ().