Salamó Llorente, MariaSànchez i Marrè, Miquel, 1964-Nakhjiri, NarimanUniversitat de Barcelona. Departament de Matemàtiques i Informàtica2026-02-272026-02-272025-11-12https://hdl.handle.net/2445/227624[eng] As the complexity of large-scale astronomical surveys increases, the need for intelligent and adaptive scheduling systems has become critical to maximizing scientific return. The Astronomical Observation Scheduling (AOS) problem represents a complex and highly constrained case of combinatorial optimization, characterized by strict computational time limits and frequent changes. Its unique structure and challenges motivate focused research to develop flexible and scalable scheduling solutions. This research is organized into two main phases, which together comprise its four core contributions. The first phase focuses on heuristic research with the aim of developing efficient heuristic strategies that effectively address the specific constraints and structure of the AOS problem. The first core contribution is the introduction of the Conflict Resolution Unit (CRU) heuristic algorithm and its variants, designed to fulfill the objectives of this phase. The second and principal phase focuses on metaheuristic research, aiming to design algorithms that are both flexible and scalable, and capable of addressing the diverse level of complexities and changes in AOS. To ensure that these metaheuristics are well-adapted to the problem, they incorporate the heuristics developed in the first phase as core components. The second contribution is the Accumulative Planner (AP) algorithm, which integrates the CRU heuristic with a greedy strategy to form a fast, primarily local optimization algorithm for AOS, with competent results. These results were used as a baseline for further improvements. The third core contribution is the Hybrid Accumulative Planner (HAP) algorithm, developed to overcome the limitations of AP. HAP uses a modified version of CRU and a multi-start strategy to enable a broader and more robust search process. The fourth and final core contribution is the Forgetful Swarm Optimization (FSO) algorithm. It combines another CRU variant with a Destroy-and-Repair strategy and a Swarm Intelligence framework to deliver a capable global optimization method. FSO is designed to balance the search in exploration and exploitation, achieving high-quality results within a reasonable computational time, while preserving the precision of domain-specific heuristics. The core contributions are adapted to a real-world example of AOS problems and evaluated using its available datasets. These datasets present a variety of test scenarios with diverse characteristics, highlighting the challenges that the algorithms must address. Besides the core contributions, the evaluation includes other adapted algorithms for this real-world problem to provide a better perspective on relative performance. These include an Evolutionary Algorithm, an Iterated Local Search, and a Hill-Climbing Greedy. The results show the effectiveness of the proposed heuristic, CRU, and its variants in handling different tasks and constraints of AOS. Furthermore, all metaheuristics that leverage CRU as a core component produce high-quality solutions. The mostly local optimization algorithm of AP competes with global approaches in terms of solution quality, even surpassing them in some cases, while operating at a fraction of their computational cost. On the other hand, FSO consistently outperforms all other algorithms across the evaluated datasets, with a significantly lower computational cost than other global optimization algorithms, such as the evaluated Evolutionary Algorithm. The HAP algorithm performs between the two other proposed metaheuristics in terms of both solution quality and computational cost. Additionally, this thesis presents an algorithm design framework that formalizes the development process leading to these solutions. This work advances the state of the art in AOS research. The novel proposals, in particular the FSO algorithm, aim to set a benchmark for future studies.[cat] A mesura que augmenta la complexitat dels estudis astronòmics a gran escala, la necessitat de sistemes de programació intel·ligents i adaptatius s'ha tornat crítica per maximitzar el retorn científic. El problema de Programació d'Observacions Astronòmiques (AOS) representa un cas complex i altament restringit d'optimització combinatòria, caracteritzat per límits estrictes de temps computacionals i canvis freqüents. La seva estructura única i els seus reptes motiven una recerca enfocada a desenvolupar solucions de programació flexibles i escalables. Aquesta recerca està organitzada en dues fases principals, que juntes comprenen les seves quatre contribucions fonamentals. La primera fase se centra en la recerca heurística amb l'objectiu de desenvolupar estratègies heurístiques eficients que abordin eficaçment les restriccions i l'estructura específiques del problema AO. La primera contribució fonamental és la introducció de l'algoritme heurístic de la Unitat de Resolució de Conflictes (CRU) i les seves variants, dissenyat per complir els objectius d'aquesta fase. La segona i principal fase se centra en la recerca metaheurística, amb l'objectiu de dissenyar algorismes que siguin flexibles i escalables, i capaços d'abordar el nivell divers de complexitats i canvis en AOS. Per assegurar que aquestes metaheurístiques estiguin ben adaptades al problema, incorporen les heurístiques desenvolupades en la primera fase com a components fonamentals. La segona contribució és l'algorisme Acumulative Planner (AP), que integra l'heurística CRU amb una estratègia cobdiciosa per formar un algorisme d'optimització ràpid, principalment local, per a AOS, amb resultats competents. Aquests resultats es van utilitzar com a base per a futures millores. La tercera contribució fonamental és l'algoritme Hybrid Accumulative Planner (HAP), desenvolupat per superar les limitacions de l'AP. HAP utilitza una versió modificada de CRU i una estratègia de múltiples inicis per permetre un procés de cerca més ampli i robust. La quarta i última contribució principal és l'algorisme d'Optimització d'Eixams Oblidats (FSO). Combina una altra variant de CRU amb una estratègia de destrucció i reparació i un marc d'intel·ligència d'eixam per oferir un mètode d'optimització global capaç. FSO està dissenyat per equilibrar la cerca en l'exploració i l'explotació, aconseguint resultats d'alta qualitat dins d'un temps computacional raonable, tot preservant la precisió de les heurístiques específiques de domini. Les contribucions bàsiques s'adapten a un exemple real de problemes d'AOS i s'avaluen utilitzant els conjunts de dades disponibles. Aquests conjunts de dades presenten una varietat d'escenaris de prova amb característiques diverses, destacant els reptes que els algoritmes han d'afrontar. A més de les contribucions principals, l'avaluació inclou altres algorismes adaptats per a aquest problema real per oferir una millor perspectiva sobre el rendiment relatiu. Aquests inclouen un algorisme evolutiu, una cerca local iterada i un Greedy d'escalada de turons. Els resultats mostren l'eficàcia de l'heurística proposada, la CRU i les seves variants per gestionar diferents tasques i restriccions de l'AOS. A més, totes les metaheurístiques que aprofiten la CRU com a component central produeixen solucions d'alta qualitat. L'algorisme d'optimització majoritàriament local dels AP competeix amb els enfocaments globals en termes de qualitat de la solució, fins i tot superant-los en alguns casos, mentre opera a una fracció del seu cost computacional. D'altra banda, FSO supera constantment tots els altres algorismes dels conjunts de dades avaluats, amb un cost computacional significativament inferior que altres algorismes d'optimització global, com l'Algorisme Evolutiu avaluat. L'algorisme HAP funciona entre les altres dues metaheurístiques proposades tant en termes de qualitat de solució com de cost computacional. A més, aquesta tesi presenta un marc de disseny d'algorismes que formalitza el procés de desenvolupament que condueix a aquestes solucions. Aquest treball avança l'estat de l'art en la recerca en AO (AOS). Les propostes noves, en particular l'algorisme FSO, pretenen establir un punt de referència per als estudis futurs.162 p.application/pdfengcc by-nc-sa (c) Nakhjiri, Nariman, 2025http://creativecommons.org/licenses/by-nc-sa/4.0/Intel·ligència artificialMetaheurísticaOptimització combinatòriaObservacions astronòmiquesArtificial intelligenceMetaheuristicsCombinatorial optimizationAstronomical observationsinfo:eu-repo/semantics/doctoralThesisinfo:eu-repo/semantics/openAccesshttp://hdl.handle.net/10803/696837