On-line machine covering on two machines with local migration

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 $\beta$ 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 $\beta =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.