Online t-interval scheduling

This paper deals with non-preemptive online t-interval scheduling. A tinterval is a union of t half-open intervals (segments). In online scheduling the t-intervals are presented incrementally and each presented interval must be accepted or lost forever. A presented t-interval which overlaps a previously accepted t-interval cannot be accepted. The decision of whether or not to accept an interval is made without knowledge of the future. Scheduling t-intervals has an application in bandwidth allocation, transmission of continuous-media data, linear resource allocation and genomic sequence similarity. Online scheduling is of increasing importance in a highspeed world with an uncertain future. The most famous version of the problem is the interval scheduling problem (t = 1). This version has been analyzed both when it is online and offline. It has also been analyzed with weighted intervals. Scheduling t-intervals for t > 1 is on the other hand area covered to lesser extent. The performance of the algorithm is the ratio between the number of tintervals in its output vs. the optimal offline schedule. If the intervals are weighted, the performance is the ratio between the total weight of these sets. The maximum ratio, taken over all input instances, is the competitive ratio. The competitive ratio is measured with respect to different factors. One factor is the input size n. Another one is _, the ratio between the length of the longest and the shortest intervals.

Author dc:creator

• Unnar Þór Bachmann 1980-

Contributors dc:contributor

• Háskólinn í Reykjavík

• Computer science
• Tölvunarfræði
• Meistaraprófsritgerðir

Language dc:language.iso

en

Handle dc:identifier.uri

http://hdl.handle.net/1946/7417

OAI identifier oai:identifier

oai:skemman.is:1946/7417