| Online algorithms for scheduling with machine activation cost on two uniform machines |
| |
| 作者姓名： | HAN Shu-guang JIANG Yi-wei HU Jue-liang |
| |
| 作者单位： | HAN Shu-guang1，JIANG Yi-wei2，HU Jue-liang2 (1Department of Mathematics，Zhejiang University，Hangzhou 310027，China) (2Faculty of Science，Zhejiang Sci-Tech University，Hangzhou 310018，China) |
| |
| 基金项目： | Project (No. Y605316) supported by the Natural Science Foundationof Zhejiang Province, China and the Natural Science Foundation of the Education Department of Zhejiang Province (No. 20060578), China |
| |
| 摘 要： | INTRODUCTION In this paper we investigate the uniform ma-chines scheduling problem with machine activationcost. This problem has application in garment pro-duction of international trade and is motivated by thefollowing scenario. Import-export company is com-pared to scheduler in this model, and orders are jobs,which arrive one by one. And garment factories canbe regarded as machines. Since jobs should be fin-ished on time, scheduler will choose a reasonablenumber of machines to make the…
|
| 关 键 词： | 同类机 在线算法 在线排序 机器激活成本 竞争分析 |
| 收稿时间： | 2006-01-28 |
| 修稿时间： | 2006-05-03 |
Online algorithms for scheduling with machine activation cost on two uniform machines |
| |
| HAN Shu-guang JIANG Yi-wei HU Jue-liang.Online algorithms for scheduling with machine activation cost on two uniform machines[J].Journal of Zhejiang University Science,2007,8(1):127-133. |
| |
| Authors: | Shu-guang Han Yi-wei Jiang Jue-liang Hu |
| |
| Institution: | (1) Department of Mathematics, Zhejiang University, Hangzhou, 310027, China;(2) 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.
Project (No. Y605316) supported by the Natural Science Foundation of Zhejiang Province, China and the Natural Science Foundation
of the Education Department of Zhejiang Province (No. 20060578), China |
| |
| Keywords: | Online algorithm Competitive analysis Uniform machine scheduling Machine activation cost |
| 本文献已被 CNKI 维普 SpringerLink 等数据库收录！ |
