Paper
On-Line Dynamic Machine Covering with Bounded Migration
- Authors:
- Xufeng Chen; Sen Qin; Yan Lan
- Abstract
- Consider an on-line dynamic machine covering problem, in which jobs arrive over time and might depart at some unknown later time. Upon the arrival of a job, its weight and reassignment cost are known, the objective is to maximize the minimum machine load. The on-line scheduler is allowed to migrate jobs between machines when a new job arrives or an old job leaves, however the total reassignment cost incurred by a specific job is bounded. In this paper, we focus two different reassignment cost models on the two machines. First, we study the uniform reassignment cost model, where the reassignment cost of each job is uniform. Then we develop an on-line algorithm whose competitive ratio is of 2 with migration factor 3. Next, the proportional reassignment cost model is dealt with, where the reassignment cost of a job is proportional to its weight. Based on the model, a 2-competitive on-line algorithm with migration factor 5 is proposed.
- Keywords
- Combinatorial Optimization; Online Scheduling; Machine Covering; Competitive Ratio; Migration
- StartPage
- 8
- EndPage
- 16
- Doi