Scheduling resource allocation with timeslot penalty for changeover
Given a time slotted list of resource capacities, we address the problem of scheduling resource allocation considering that a change in allocation results in the changeover penalty of one timeslot. The goal is to maximize the overall allocation of resources. We prove that no 1-lookahead algorithm can be better than (8)/(5)competitive. We provide improved analysis of Wait Dominate Hold (WDH) algorithm that was previously known to be 4-competitive. We prove that WDH (8)/(3)-competitive. We also consider k-lookahead algorithms, and prove lower bound of (k + 2)1(k + 1) on their competitiveness and give an online algorithm that is 2-competitive. (c) 2006 Elsevier B.V. All rights reserved.
resource allocation online scheduling changeover cost wireless scheduling