Suchergebnisse

{\begin{rawhtml} Revised Version unter http://dx.doi.org/10.1007/s10479-007-0178-0 \end{rawhtml}} Wireless communication is used in many different situations such as mobile telephony, radio and TV broadcasting, satellite communication, and military operations. In each of these situations a frequency assignment problem arises with application specific characteristics. Researchers have developed different modelling ideas for each of the features of the problem, such as the handling of interference among radio signals, the availability of frequencies, and the optimization criterion. This survey gives an overview of the models and methods that the literature provides on the topic. We present a broad description of the practical settings in which frequency assignment is applied. We also present a classification of the different models and formulations described in the literature, such that the common features of the models are emphasized. The solution methods are divided in two parts. Optimization and lower bounding techniques on the one hand, and heuristic search techniques on the other hand. The literature is classified according to the used methods. Again, we emphasize the common features, used in the different papers. The quality of the solution methods is compared, whenever possible, on publicly available benchmark instances.

In der ressourcenbeschränkten Projektplanung müssen Vorgänge unter Berücksichtigung von Reihenfolgebeziehungen und Kapazitätsrestriktionen zeitlich so eingeplant werden, dass eine gegebene Kostenfunktion minimiert wird. In der vorliegenden Arbeit wird zusätzlich davon ausgegangen, dass die Dauer der einzelnen Vorgänge nicht zu Beginn der Planung bekannt, sondern durch je eine Zufallsvariable gegeben ist. Auf diese Weise ist es möglich, unvorhersehbare Ereignisse wie zum Beispiel Wetterbedingungen, Krankheit von Mitarbeitern, Rechtsfragen oder Genehmigungsverfahren in die Planung eines Projekts mit einzubeziehen. Als Konsequenz hieraus kann das Risiko von Projekt-Verzögerungen und damit verbundenen Kostensteigerungen (von denen im Rahmen von umfangreichen Projekten häufig berichtet wird) reduziert werden. Ziel der vorliegenden Arbeit ist es, Algorithmen zu entwickeln, die die Berechnung guter Lösungen in akzeptabler Rechenzeit ermöglichen. Eine Lösung ist hier eine so genannte Politik, eine Planungsvorschrift, die zu jedem möglichen Entscheidungszeitpunkt t während der Umsetzung des Projekts eine Menge von Vorgängen definiert, deren Durchführung zum Zeitpunkt t begonnen werden soll. Basierend auf der Beobachtung, dass die häufig angewendeten Prioritäts-Politiken nicht für eine "robuste" Planung geeignet sind, liegt der Schwerpunkt der Untersuchungen auf der strukturell sehr attraktiven Klasse der präselektiven Politiken. Solche Politiken selektieren für jede minimal verbotene Menge F von Vorgängen einen Vorgang aus F, dessen Durchführung erst dann begonnen wird, wenn mindestens ein anderer Vorgang aus F beendet ist. (Eine minimal verbotene Menge ist eine minimale Teilmenge von Vorgängen, zwischen denen keine Reihenfolgebeziehungen vorliegen, die jedoch aufgrund der Ressourcen-Beschränkungen nicht zur gleichen Zeit in Betrieb sein können.) Um ein bestmögliches Verständnis von präselektiven Politiken zu erzielen, betrachten wir im ersten Teil der vorliegenden Arbeit eine Verallgemeinerung klassischer Reihenfolgebeziehungen zwischen Vorgängen, die so genannten AND/OR Reihenfolgebeziehungen. Diese finden zum Beispiel im Rahmen von Montage- oder Demontage-Prozessen Anwendung; der Zusammenhang zu dem oben beschriebenen ressourcenbeschränkten Scheduling-Modell besteht in der Tatsache, dass präselektive Politiken durch eine Menge von AND/OR Reihenfolgebeziehungen repräsentiert werden können. Es werden Resultate im Zusammenhang mit der Verallgemeinerung von Begriffen wie transitive Hülle und transitive Reduktion erzielt. Darüber hinaus werden für gegebene zeitliche Abstände zwischen den Vorgängen Algorithmen zur Berechnung frühster Startzeiten von Vorgängen entwickelt. Basierend auf den beschriebenen Ergebnissen werden Dominanzresultate für präselektive Politiken abgeleitet, sowie zwei Teilklassen der präselektiven Politiken definiert und untersucht, die vom algorithmischen Standpunkt gesehen bessere Eigenschaften als präselektive Politiken besitzen. Für diese Klassen von Politiken (und eine weitere, aus der Literatur bekannte Klasse) werden insgesamt fünf verschiedene Branch-and-Bound Verfahren entwickelt und implementiert sowie auf Basis von 1440 Instanzen getestet und miteinander verglichen. Die empirischen Ergebnisse zeigen, dass die entwickelten Resultate auf dem Gebiet der AND/OR Reihenfolgebeziehungen die Leistung der Branch-and-Bound Verfahren deutlich steigern und dass die vorgeschlagenen Teilklassen der präselektiven Politiken gute Ausgangspunkte für den algorithmischen Zugang zur heuristischen Lösung von Real-Life Instanzen darstellen. ; In resource-constrained project scheduling, jobs (activities) have to be planned over time subject to precedence and resource constraints with the intention to minimize some objective function. In addition, we assume that the processing time of each job is uncertain and follows a given probability distribution. This extension of classical deterministic resource-constrained project scheduling is motivated by uncertain events that usually appear within the execution of projects. Weather conditions, unavailability of resources, and authorization processes are only some examples. The purpose of this thesis is to develop and implement algorithms to find solutions (so-called policies) of good quality within moderate computation times. A policy may be seen as a dynamic decision process that defines which jobs are started at certain decision times t, based on the observed past up to t. We study the class of preselective policies as well as different subclasses thereof. A preselective policy defines for each minimal forbidden set F a preselected job from F which is postponed until at least one other job from F has been completed. (A minimal forbidden set F is an inclusion-minimal set of jobs without any precedence constraints among them and the total resource consumption of the jobs in F exceeds the resource availability.) To obtain results on the combinatorial structure of preselective policies we study the concept of so-called AND/OR precedence constraints which are a generalization of traditional precedence constraints. AND/OR precedence constraints are of relevance in its own due to their appearance within, e.g., assembly or disassembly processes. We propose a new field of application which is based on the fact that any preselective policy can be expressed as a set of such constraints. To this end, we develop a number of basic algorithms for scheduling jobs subject to AND/OR precedence constraints. For example, we give two different polynomial time algorithms to compute earliest job start times as well as a linear time algorithm to detect 'transitive' AND/OR precedence constraints. The results obtained for AND/OR precedence constraints give also rise to consider particular subclasses of preselective policies. These classes differ with respect to both their computational tractability and the optimum expected objective function value that can be achieved within the respective class. We collect some of the structural and algorithmic properties of these classes of policies and use them to develop in total five branch-and-bound algorithms. Enhanced with many additional ingredients to speed up the computations, the algorithms are rigorously tested on 1440 instances created by the widely accepted instance generator ProGen. In particular, for each of the considered classes of policies, we establish results on the trade-off between computational efficiency on the one hand and solution quality on the other hand. The experiments reveal that the considered subclasses of preselective policies are a good starting point to develop heuristic approaches to solve large-scale stochastic resource-constrained project scheduling problems.

2000/2001 ; Ogni sistema di trasporto delle merci si presenta generalmente molto articolato e complesso: in particolare l'esistenza di numerosi soggetti che, a diverso livello e con diversi obiettivi, sono tenuti ad operare decisioni rappresenta un elemento che influisce in maniera spesso importante sull'assetto del sistema stesso. Il lavoro prende in esame un sistema di trasporto merci con due attori, denominati P e Q, che attraverso le rispettive decisioni determinano l'assetto dei flussi sulla rete. Il soggetto P, in particolare, è incaricato di soddisfare una data domanda di trasporto (ad esempio espressa mediante una matrice 0/D data) e può decidere come ripartire i flussi su una rete multi modale della quale percepisce i tratti fondamentali. Al momento della sua decisione, P conosce il costo generalizzato degli archi della rete e cerca di minimizzare il costo totale del trasporto. Inoltre il giocatore P deve rispettare le decisioni del giocatore Q. Il giocatore Q, che controlla una porzione della rete che connette le origini alle destinazioni di P, invece conosce il profitto unitario che deriva dal transito veicolare sui suoi archi e cerca di massimizzare il proprio profitto complessivo. Nel far questo può modificare la capacità degli archi della sua sotto rete, ma anch'egli deve comunque soddisfare la condizione di bilanciamento ai nodi e deve rispettare le decisioni di P. Quale primo elemento di originalità del presente lavoro può essere considerato il tentativo di condensare in un unico approccio alcuni elementi presenti singolarmente in filoni diversi. Infatti, tra i modelli della letteratura che intendono rappresentare esplicitamente le dinamiche decisionali interattoriali si ricordano i modelli multiattoriali sequenziali, i giochi su rete e la programmazione lineare bilivello i quali formano il quadro di riferimento in cui la presente lavoro si inserisce. Il quadro attoriale appena delineato offre l'opportunità di affrontare una serie di problemi diversi, nel campo dell'affidabilità della rete, a seconda dell'ordine con il quale i due giocatori decidono. Infatti il caso in cui la decisione di P preceda quella di Q può essere significativo, per P, al fine di valutare la peggiore situazione che potrebbe presentarsi per effetto di Q una volta stabilito l'assetto dei flussi sulla propria rete. È questo un tipico esempio della cosiddetta "worst case analysis. Viceversa, se gioca prima Q, P riesce a determinare il migliore assetto dei propri flussi nel rispetto di vincoli imposti da Q su una parte della rete interposta tra la sua origine e la destinazione. Si pensi ad esempio alla problematica dell'attraversamento di Paesi, quali Austria e Svizzera, che impongono severe limitazioni per i veicoli pesanti. Il problema descritto viene formulato come un gioco su rete nel quale i due giocatori, P e Q, non cooperano tra loro. Si ottiene così una formulazione di programmazione lineare bilivello (BLP) dove il giocatore che gioca per primo è il leader, mentre l'altro assume il ruolo di follower. Ricordando che i problemi BLP sono NPhard, è stato sviluppato ed implementato un algoritmo euristico di ricerca della soluzione ottima. Sfruttando però l'osservazione che, nel particolare caso in questione, la soluzione ottima del problema BLP è anche un punto di equilibrio di Nash, l'algoritmo restringe la sua ricerca nell'insieme dei punti di equilibrio di Nash. Da un punto di equilibrio di Nash si passa ad un altro corrispondente ad una soluzione "migliore per il leader fino a quando l'algoritmo non si ferma. Purtroppo però non si è sempre in grado di determinare un ottimo globale, ma solamente un ottimo locale individuando così, nel caso sia P a giocare per primo, un limite superiore alla soluzione ottima. Lo studio di tale modello è stato motivato dalla volontà di rappresentare, con riferimento al sistema del trasporto merci su gomma tra la Thrchia e l'Europa Occidentale, la situazione che si è venuta a creare nella regione dei Balcani a causa dei recenti eventi bellici. Tra le due regioni, annualmente, si registra un traffico dell'ordine delle centinaia di migliaia di veicoli commerciali. Per ragioni di semplicità, si è fatto riferimento alla sola componente verso l'Europa, fermo restando che la direzione opposta potrebbe essere analizzata in maniera del tutto analoga. Nell'esempio affrontato, la domanda di trasporto delle merci, che viene misurata in numero di veicoli all'anno, e che si sposta con origini diverse nel Sud-Est asiatico e destinazioni pure diverse nell'Europa Occidentale, è stata concentrata in due sole polarità (1 origine e l destinazione). Nel sistema appena descritto l'Associazione Industriali della nazione di origine (UND) svolge il ruolo di decisore centrale ed è stata assimilata al giocatore P di cui sopra. In breve, nota la domanda da trasportare, l'UND decide la distribuzione delle merci tra vari percorsi sulla rete che collega l'origine (Turchia) alla destinazione (Europa occidentale). Conosce pure il costo generalizzato degli archi di tale rete e opera le proprie decisioni con l'obiettivo di rendere minimo il costo del trasporto. L'evento bellico ha causato, come riflesso su detto sistema, una decisa modifica alla capacità degli archi di una porzione della rete stradale iniziale, che garantiva la connessione tra origine e destinazione. Alcuni archi sono stati eliminati (la rispettiva capacità posta pari a zero), altri hanno subito una netta riduzione della capacità, o un significativo aumento del costo generalizzato. La guerra quindi ha assunto un comportamento analogo a quello del giocatore Q. In questo caso però, non ha significato parlare di un'utilità che la guerra cerca di massimizzare secondo quanto esposto in precedenza, a meno che non si proceda ad assimilare l'utilità del giocatore Q con i costi di P: se Q gioca per massimizzare la propria utilità e quest'ultima corrisponde ai costi di P, automaticamente Q gioca per massimizzare i costi di P e il modello acquista proprio il significato di una analisi del caso peggiore per P. La rete considerata è stata semplificata in accordo con il livello di dettaglio delle informazioni di cui dispone P ed è formata da 99 nodi e 181 archi, di cui solamente 100 sotto il controllo di P. Gli altri 81 archi, concentrati nella regione dei Balcani, sono sotto il controllo di Q e costituiscono una sottorete connessa, che disconnette l'origine dalla destinazione. La capacità degli archi è stata determinata in accordo con il numero dei permessi di transito annui che ogni Stato concede ai veicoli turchi. Tale numero viene annualmente definito, mediante contrattazione tra le parti, in accordi bilaterali. In questa fase non si è tenuto conto delle differenti tipologie di permessi. In accordo con alcune necessarie ipotesi semplificative, la rete stessa è aciclica. I valori del costo per veicolo percepito da parte di P per transitare sugli archi della sottorete propria od altrui rispettivamente, sono stati determinati come funzione del costo monetario, della lunghezza fisica dell'arco e del tempo di percorrenza, tenendo in considerazione le varie voci che concorrono alla formazione del costo unitario (per veicolo-chilometro) di produzione di un servizio di trasporto sull'arco preso in esame. Per quanto riguarda i termini che compaiono nella funzione obiettivo di Q, si suppone che la guerra non tragga beneficio alcuno dal transito dei flussi veicolari sulla rete di P, mentre il profitto di Q è stato posto pari al costo sostenuto da P cambiato di segno come descritto in precedenza. Ai fini di valutare le prestazioni dell'algoritmo, il medesimo problema, viste le sue contenute dimensioni, è stato risolto anche con un algoritmo esatto, cioè in grado di determinare l'ottimo globale. Il risultato dell'algoritmo proposto si discosta di solo lo 0,3% dal risultato ottenuto con una procedura di branch and bound. L'esempio applicativo ha consentito di comprendere le potenzialità dell'approccio proposto e nell'ottica di un suo utilizzo concreto ha fornito delle utili indicazioni su possibili sviluppi da intraprendere legati sia all'algoritmo, sia al modello sia al caso di studio. In conclusione, il lavoro presenta un modello per la definizione dell'assetto del sistema di trasporto delle merci, con la trattazione esplicita delle dinamiche decisionali interattoriali. In particolare si prendono in considerazione due soggetti, che operano scelte in sequenza gerarchica, uno dei quali agisce per minimizzare i costi totali del trasporto e l'altro cerca invece di massimizzare il proprio profitto che dipende dal volume di traffico lungo gli archi sotto il suo controllo. Si propone una formulazione di programmazione lineare bilivello, per risolvere un gioco infinito statico non cooperativo con insiemi di vincoli accoppiati. Sono descritte le condizioni di esistenza e alcune proprietà dei punti di equilibrio di N ash, dalle quali discende un algoritmo di ricerca di un ottimo locale. Viene infine discussa un'applicazione del modello al caso del trasporto merci dalla Turchia all'Europa. Alcuni futuri sviluppi sono possibili. Essi portano alla progressiva eliminazione delle assunzioni semplificative che sono state adottate allo stato attuale nella formulazione del modello. In particolare si tratta della configurazione della rete, della struttura e delle proprietà dell'algoritmo (oggi trova solamente un ottimo locale). Inoltre si intende procedere con il perfezionamento del caso di studio. ; Freight transportation is generally a very complex domain where several players, each with its own set of objectives, act and operate at various decisional levels. There are different players in the field. The shippers who decide how much of each commodity to move from every origin to every destination and the means by which the goods will be moved. The carriers who respond to this transportation demands and route freight over the actual transportation network under their contro!. Finally, the government defined as the set of international, national and local authorities involved in any way with freight transportation via regulation and the provision of transportation infrastructure. In this work, we consider the case where only one shipper determines the demand for transportation over a network. However, he cannot decide fiow levels on arcs in a fully independent way due to the presence of a second agent controlling some links of the network and optimizing her own objective function. This situation is modelled as a game between two players P and Q acting o n the same network G. Player P fixes the fiows o n the arcs of G in such a way t ha t their divergence at some given nodes (sources and sinks) is equal to prescribed values. Such divergences may represent demand and availability levels for some commodity. On the other hand, player Q decides the values of the maximum capacities of some arcs of the network. Both players are interested in the fact that the connectivity between the sources and the sinks in the network is respected, i.e., they both want that the goods can reach their destination. However, they have different objectives. Player P aims at minimizing the transportation costs, whereas player Q aims at maximizing her profit (or, in generai, her utility) that is proportional to the fiow passing through the arcs under her control. Note that, in generai, the profit of player Q is not assumed to be equal to the cost of player P for the same are. Such game between players P and Q is modelled as a minimum cost flow problem for player P, where the are costs are given and the player Q decides the are capacities. The modelling of the games under investigation are mainly based upon three different research lines. First, the players understand the freight transportation system as a system where the actors involved do not act simultaneously and they explicitly take into account the sequential nature of the interactions among them. Second, they play a (hierarchical) game over a flow network which causes severe limitations and constraints to their action sets. Finally, the games exhibit linear characteristics and can be solved using bilevel linear programming. All these issues have already been discussed in the scientific literature, even though in different separate contexts. The merging of three mentioned approaches in only one single framework is a major contribution of our modelling perspective. Furthermore, bilevel programming is rich of theoretical results and numerica! algorithms, but is scare in actual applications. From this point of view, the present work might be considered as an interesting addition to the field. Bilevel noncooperative games in which one player ( called the leader) declares his strategy first an d enforces i t o n the other players ( called the followers) w ho react (rationally) to the leader's decision are referred to as Stackelberg games. Since the payoff functions and all the constraints in our Stackelberg games may be expressed in a linear form, these games will be formalized as bilevellinear programming problems (BLPPs). In generai, bilevel programming problems are difficult to sol ve because of their inherent non-convexity and non-differentiability. To face their NP-hard nature, we identify some properties of the game solutions which allow us to define a heuristic algorithm restricting its (local) search on the set of the Nash equilibrium points. The optimal solution of any BLPP lies on a vertex of the leader's inducible region. Relying on this result, we develop an algorithm which allows to move from a starting point of the shipper's inducible region to another point in the shipper's inducible region always providing a better solution for him. When no further better points may be attained, the algorithm stops. Unfortunately, only a local optimum is identified. The rationale behind the algorithm stems from the consideration that the optimal solution for our BLPP is also a Nash equilibrium point. In particular, the algorithm moves from a Nash equilibrium point to another better Nash equilibrium point of the BLPP under study. This framework may describe, as an example, the situation where restrictions are imposed by some alpine country on the number of trucks allowed to cross it by road each year. A different context involving the presence of a second agent o n the shipper's network occurred when the International Transporters' Association (UND) of Turkey had to face when the war in the Balkans started. This situation motivates our investigation on hierarchical noncooperative network games. The road freight traffi.c from Turkey to Centrai and Western Europe and viceversa suffered major disruptions because of the war in Balkans during the nineties. UND is the shipper controlling the quasi-totality of this traffi.c thus assuming the role of player P. H e had to cope with an "adverse entity" able to modify the available capacity on some specific links his vehicles had to pass through. The region involved in the confiict may be represented as a connected subnetwork disconnecting the origin and the destinations of the road transportation network since alternative road routes are not easily affordable. Other possibilities, like the seaborne links now operating, did not exist at that time. Hence the whole freight traffi.c was performed using a single mode of transport. The models developed in this work allow the shipper to perform a worst-case analysis at the strategie level for this situation assuming that player Q wishes to maximize the costs he has to afford when going through the region under her control. In fact, it is meaningless to talk about the utility or the profit the war may seek t o maximize. However, i t becomes a sensible modelling when the utility of player Q is strictly related to the costs afforded by player P on this portion of the network. lf player Q is maximizing her utility which corresponds to player P's costs, automatically she plays to maximize player P's costs. Hence the model represents a worst-case analysis for player P. A simple graph composed of 99 nodes and 181 arcs is presented. Player P controls a sub network composed of 100 arcs. The others 81 links representing the connections within the Balkans and Eastern Europe form a connected sub network. Only the main road links ha ve been considered ( motorways or highways). The capacities are calculated taking into account the total number of transit permits available for each country. This figure is annually fixed in bilatera! Joint Committee Meetings. Player P's costs are the average generalized costs derived as a function of lengths and transfer times in the physicallinks. Player Q does not have profits or losses for the fiows passing through the P zone and it is also assumed that the profits she earns for each unit of fiow going through the arcs under her control are equal to the costs afforded by the shipper when traversing these arcs. All the relevant data required to calculate these figures are collected in the UND Annual Sector Report 1997-98 (1999). The heuristic algorithm has been tested on this network and its results have been compared with the outcome obtained by using an exact enumeration procedure. Since it turns out that the percentage error of the heuristic algorithm is equal to 0,3%, we may claim that its performances are certainly highly satisfactory, at least in this specific example. Different extensions of the models and the algorithm developed may be easily envisaged both from the theoretical and the application side. These advances would provide either faster local or global search algorithms either more complete models representing in deeper detail the actual system and the interactions among the actors involved. Hence a decision support system for the shipper's decision making process at the strategie level can be built and effectively used by freight transportation practitioners. ; XIII Ciclo ; 1969 ; Versione digitalizzata della tesi di dottorato cartacea.