Semi On-Line Scheduling Problem for Maximizing the Minimum Machine Completion Time on Two Uniform Machines期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

Semi On-Line Scheduling Problem for Maximizing the Minimum Machine Completion Time on Two Uniform Machines

Authors:	Runzi Luo Shijie Sun Wenping Huang

Affiliation:	(1) Mathematic Department, Nanchang University, Nanchang, 330047, China;(2) Mathematic Department, Shanghai University, Shanghai, 200444, China;(3) Government Office of Zaozhuang, Shandong Province, Zaozhuang, 277800, China

Abstract:	In this paper, we consider a semi on-line version on two uniform machines M_i, i = 1,2, where the processing time of the largest job is known in advance. A speed s_i(s₁ = 1, 1≤ s₂ = s) is associated with machine M_i. Our goal is to maximize the C_min. We give a C_{min 2} algorithm and prove its competitive ratio is at most $frac{2s+1}{s+1}$ . We also claim the C_{min 2} algorithm is tight and the gap between the competitive ratio of C_{min 2} algorithm and the optimal value is not greater than 0.555. It is obvious that our result coincides with that given by He for s = 1.

Keywords:	Competitive ratio scheduling semi on-line
本文献已被 CNKI 维普 SpringerLink 等数据库收录！