Online algorithms for scheduling with machine activation cost on two uniform machines

In this paper we investigate a variant of the scheduling problem on two uniform machines with speeds 1 and s. For this problem, we are given two potential uniform machines to process a sequence of independent jobs. Machines need to be activated before starting to process, and each machine activated...

Full description

Saved in:
Bibliographic Details
Published in:Journal of Zhejiang University. A. Science 2007, Vol.8 (1), p.127-133
Main Authors: Han, Shu-guang, Jiang, Yi-wei, Hu, Jue-liang
Format: Article
Language:English
Subjects:
同类机
在线排序
在线算法
机器激活成本
竞争分析
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper we investigate a variant of the scheduling problem on two uniform machines with speeds 1 and s. For this problem, we are given two potential uniform machines to 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 the machine activation cost. We design optimal online algorithms with competitive ratio of （2s＋ 1）/（s＋ 1） for every s≥1.
ISSN:1673-565X
1862-1775
DOI:10.1631/jzus.2007.A0127