Scheduling resource allocation with timeslot penalty for changeover

AbstractGiven 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 85-competitive. We provide improved analysis of Wait Dominate Hold (WDH) algorithm that was previously known to be 4-competitive. We prove that WDH is 83-competitive. We also consider k-lookahead algorithms, and prove lower bound of (k+2)/(k+1) on their competitiveness and give an online algorithm that is 2-competitive