One way of proving the optimality of this algorithm is by using the Charging argument.Īn important class of scheduling algorithms is the class of dynamic priority algorithms. The optimal solution is choosing the earliest finishing time, as in the request that finishes first. Selecting the shortest intervals or selecting intervals with the fewest conflicts is also not optimal. For example, selecting the intervals that start earliest is not an optimal solution because if the earliest interval happens to be really long by accepting it we would have to reject many other shorter requests. There are several solutions for this problem that are not optimal. A compatible set of maximum size is called optimal. We say that a subset of requests is compatible if no two of them overlap in time and our goal is to accept as large a compatible subset as possible. A request corresponds to an interval of time. Posed as an optimization problem, the goal is to maximize the number of executed tasks without overlapping the tasks. A list of tasks is given as a set of time intervals for instance, one task might run from 2:00 to 5:00 and another task might run from 6:00 to 8:00. Interval scheduling is a class of problems in computer science, particularly in the area of algorithm design.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |