Dynamic Spectrum Allocation Algorithms
Abstract
In our previous funding, we reported the following. The standard online scheduling method to avoid fragmentation is called First Fit, which roughly speaking tries to schedule every task as early in time and as low in the spectrum as possible. We find that for the input distributions that we tested, First Fit does not perform appreciably bettor than random placement, We then considered offline algorithms that can do the jobs in some predefined order. We also give some theoretical evidence of the difficulty of producing good schedules in the online setting 2. More precisely, we showed that if one is given a sequence of tasks that can be fit into a spectrum of size B, there is no online algorithm that can fit these tasks into spectrum of size c*B, for any constant c. In the offline setting, we have found that, among the simple heuristic algorithms, the best are those that in some sense try to schedule the jobs from earliest in time to latest in time. We call it Timeline. On the inputs we tested these algorithms were consistently able to schedule 5% to 10% more jobs than Random. While a 5% to 10% improvement may seem modest, one needs to ask oneself about the benefit of being able to schedule a few more tests per day relative to the cost of the system required to produce such a schedule.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 31, 2002
- Accession Number
- ADA420598
Entities
People
- Bala Kalyanasundaram
- Kirk Pruhs
Organizations
- University of Pittsburgh