Please use this identifier to cite or link to this item: https://hdl.handle.net/1946/7417
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.
Þessi ritgerð fjallar um raðbundin reiknirit fyrir t-bilaval. Sammengi hálf opinna bila, t að tölu, kallast t-bil. Í raðbundnu t-bilavali er eitt t-bil birt í senn. Á þeim tímapunkti þarf að velja bilið, ella glata því fyrir fullt og allt.
t-bilaval hefur margvíslegan hagnýtan tilgang: Úthlutun á bandvídd, gagnaflutningi, auðlindastjórnun og mynsturgreiningu genamengjum. Mikilvægi raðbundinna reiknirita er sívaxandi í heimi hraða og óvissu umframtíð. Þekktasta útgáfan af t-bilavali er bilaval (t = 1). Þetta vandamál hefur verið kannað að nokkru leiti. Bæði fyrir raðbundin reiknirit og þegar bilin eru gefin fyrirfram. Einnig hefur bilaval verið kannað með vegnum bilum. Almennt t-bilaval er hins vegar mun minna kannað.
Frammistaða reiknirits er mæld með hlutfallinu milli fjölda t-bila í úttaki og stærsta mögulega bilasafnsins, þar sem engin tvö bil skarast. Nálgunarhlutfall er hámark þessa hlutfalls, reiknað yfir öll möguleg inntök. Nálgunarhlutfallið er oft metið m.t.t. tiltekinna stuðla. Dæmi um slíka stuðla er n, fjöldi bila í inntaki. Annað dæmi er _, hámarks hlutfall milli lengda bila í inntaki.
Filename | Size | Visibility | Description | Format | |
---|---|---|---|---|---|
MSc_UnnarThorBachmann.pdf | 358,15 kB | Open | Complete Text | View/Open |