|
|
|
| Online algorithms for scheduling with machine activation cost on two uniform machines |
| HAN Shu-guang, JIANG Yi-wei, HU Jue-liang |
| Department of Mathematics, Zhejiang University, Hangzhou 310027, China; Faculty of Science, Zhejiang Sci-Tech University, Hangzhou 310018, China |
|
|
|
Abstract 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.
|
|
Received: 28 January 2006
|
|
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
