Vi presenterar den första kopplade formella och empiriska analysen av Satellite Range Scheduling ansökan. Vi strukturerar vår studie som en progression; vi börjar med att studera en förenklad version av problemet där endast en resurs finns. Vi visar att den förenklade versionen av problemet är likvärdig med en välkänd maskin schemaläggning problem och använda detta resultat för att bevisa att Satellite Range Scheduling är NP-komplett. Vi visar också att för en resurs version av problemet, algoritmer från maskinen schemaläggning domän överträffa en genetisk algoritm som tidigare identifierats som en av de bästa algoritmer för Satellite Range Scheduling. Därefter undersöker vi om dessa resultat generaliserar för problemet med flera resurser. Vi utnyttjar två datakällor: faktiska begäran data från U.S. Air Force Satellite Control Network (AFSCN) runt 1992 och data som skapats av vår problemgenerator, som är utformad för att producera problem liknande dem som för närvarande lösts av AFSCN. Tre huvudsakliga resultat framträder från vår empiriska studie av algoritmprestanda för problem med flera källor. För det första, de resultat som erhållits för en enda resurs version av problemet inte generalisera: algoritmerna från maskinen schemaläggning domänen fungerar dåligt för flera källor problem. För det andra visar sig en enkel heurism fungera bra på de gamla problemen från 1992, men den lyckas inte skala upp till större, mer komplexa problem. Slutligen, en genetisk algoritm visar sig ge den bästa övergripande prestanda på de större, svårare problem som produceras av vår generator. - Vad är det för fel på dig?
En sådan resulterande problem kallas Multi-Resource Range Scheduling Problem (MURRSP) och är NP-hård REF ).
Scheduling space-ground communications for the Air Force satellite control network
{'venue': 'Journal of Scheduling', 'journal': None, 'mag_field_of_study': ['Computer Science']}