publication . Article . 2011

On-line machine covering on two machines with local migration

Chen, Xufeng; Qin, Sen;
Open Access English
  • Published: 01 Sep 2011 Journal: Computers & Mathematics with Applications, issue 5, pages 2,336-2,341 (issn: 08981221, Copyright policy)
  • Publisher: Elsevier Ltd.
Abstract
AbstractWe 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 ma...
Subjects
free text keywords: On-line scheduling, Machine covering, Competitive ratio, Bounded migration, Modelling and Simulation, Computational Theory and Mathematics, Computational Mathematics, Computer science, Bounded function, Competitive analysis, Constant factor, Mathematical optimization
Related Organizations
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue