On-line machine covering on two machines with local migration |
| |
Authors: | Xufeng Chen Sen Qin |
| |
Affiliation: | School of Science, Hangzhou Dianzi University, Hangzhou 310018, China |
| |
Abstract: | We study an on-line machine covering problem, in which jobs arrive one by one and their processing times are known upon their arrival, and jobs are allowed to migrate between machines when a new job is added in the system. However, the total processing time of migration induced by an incoming job is bounded by a constant factor β times the processing time of the incoming job. The objective is to maximize the minimum machine load. In this paper, we present an on-line algorithm with competitive ratio 6/5 for the two identical machines case with β=1. Moreover, the presented on-line algorithm is only a local migration, that is, when one job is assigned to machine i, only the jobs on machine i are allowed to migrate. We also show that the provided algorithm is a best possible on-line algorithm in the sense of local migration. |
| |
Keywords: | On-line scheduling Machine covering Competitive ratio Bounded migration |
本文献已被 ScienceDirect 等数据库收录! |
|