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 is 8/3-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.