2026-09-20T16:31:31Zhttps://api.mountainscholar.org/server/oai/request

oai:mountainscholar.org:10217/2434082026-02-24T12:07:09Zcom_10217_100532com_10217_100000com_10217_100388com_10217_100303col_10217_100538col_10217_100389

Barbulescu, Laura, author Whitley, Darrell, advisor Howe, Adele E., advisor 2026-02-23T19:18:11Z 2005 https://hdl.handle.net/10217/243408 https://doi.org/10.25675/3.026236 We analyze the factors that influence algorithm performance for an oversubscribed application, scheduling for the Air Force Satellite Control Network (AFSCN). AFSCN scheduling assigns access requests to specific time slots on antennas at ground stations. The application is oversubscribed: not all tasks can be accommodated given the available resources. As a special class of scheduling problems, oversubscribed problems present additional challenges. While, in general, solutions to scheduling problems specify the start times and resources assigned to tasks, in oversubscribed scheduling the maximal subset of tasks that can be scheduled with the available resources also needs to be identified. We implemented various algorithms for AFSCN scheduling. Some algorithms, such as a domain-specific repair-based algorithm or constraint-based scheduling heuristics, failed to identify good solutions. We have found a set of fairly simple algorithms that perform well on the AFSCN scheduling domain, for both real and synthetically generated problems. The algorithms in the set are: hill-climbing, a genetic algorithm (GA) and Squeaky Wheel Optimization (SWO). All the algorithms in the set are designed to traverse the same search space: solutions are represented as permutations of tasks; a greedy schedule builder converts the permutation into a schedule by assigning a start time and resources to the requests in the order in which they appear in the permutation. However, these algorithms vary in the way they traverse the search space. This research identifies performance factors that make each of the algorithms a good fit for AFSCN scheduling. The AFSCN scheduling search space is dominated by plateaus, due to both the discrete nature of the objective function and to the fact that the schedule builder converts multiple permutations into identical schedules. Each algorithm handles plateaus differently. Hill-climbing randomly walks on the plateaus until it finds exits to lower plateaus: the higher the percentage of the space occupied by plateaus, the more random wandering is likely for hill-climbing. We found the ordering of the neighbors to be the main performance factor in expediting plateau traversal for hill-climbing. The GA and SWO both traverse the plateaus quickly, by making multiple changes to the solutions. The long, directed leaps across the search space are the main performance factor for the GA and SWO. We also investigated whether initializing the search closer to the best solutions is the key to performance. We found that such initialization helps but is not by itself enough to explain algorithm performance results. The main contributions of this research work are: 1) We performed the first coupled formal and empirical analysis of the AFSCN scheduling problem. 2) We designed techniques for analyzing algorithm performance, which could transfer to other applications. 3) We identified algorithm performance factors, which are likely to hold on other similar problems. 4) We designed a new best performing algorithm, by combining the features we found to have most influence on performance. doctoral dissertations English eng Colorado State University. Libraries 2000-2019 Copyright and other restrictions may apply. User is responsible for compliance with all applicable laws. For information about copyright law, please see https://libguides.colostate.edu/copyright. Per the terms of a contractual agreement, all use of this item is limited to the non-commercial use of Colorado State University and its authorized users. computer science Analyses of algorithm performance for an oversubscribed scheduling problem Text Doctor of Philosophy (Ph.D.) Doctoral Computer Science Colorado State University This Item is protected by copyright and/or related rights (https://rightsstatements.org/vocab/InC/1.0/). You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s). open.access