Award Date

12-2011

Degree Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science

First Committee Member

Wolfgang Bein, Chair

Second Committee Member

Ajoy Datta

Third Committee Member

Lawrence Larmore

Graduate Faculty Representative

Emma Regentova

Number of Pages

68

Abstract

We consider a class of problems of scheduling independent jobs on identical, uniform and unrelated parallel machines with an objective of achieving an optimal schedule. The primary focus is on the minimization of the maximum completion time of the jobs, commonly referred to as Makespan (C max ). We survey and present examples of uniform machines and its applications to the single slot and multiple slots based on bids and budgets.

The Internet is an important advertising medium attracting large number of advertisers and users. When a user searches for a query, a search engine returns a set of results with the advertisements either on top of the page or on the right hand side. The assignment of these ads to positions is determined by an auction using the ad-slot placement. The algorithmic approach using the level algorithm (which constructs optimal preemptive schedules on uniform parallel machines) is taken into consideration for assigning bidders to the slots on the Internet.

Keywords

Computer scheduling; Internet advertising; Parallel processing (Electronic computers)

Disciplines

Computer Sciences | Databases and Information Systems | Numerical Analysis and Scientific Computing

Language

English


Share

COinS