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 -competitive. We provide improved analysis of Wait Dominate Hold (WDH) algorithm that was previously known to be 4-competitive. We prove that WDH is -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.