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 ().