Catálogo de publicaciones - libros

Fleet assignment models are used by many airlines to assign aircraft to flights in a schedule to maximize profit [1]. A major airline reported that the use of the fleet assignment model increased annual profits by more than $100 million [3] a year over three years. The results of fleet assignment models affect subsequent planning, marketing and operational processes within the airline. Anticipating these processes and developing solutions favorable to them can further increase the benefits of fleet assignment models. We develop fleet assignment solutions that increase planning flexibility and reduce cost by imposing station purity, limiting the number of fleet types allowed to serve each airport in the schedule [4]. Imposing station purity on the fleet assignment model can limit aircraft dispersion in the network and make solutions more robust relative to crew planning, maintenance planning and operations.

We consider the Arrow-Debreu competitive market equilibrium problem which was first formulated by Leon Walras in 1874 [12]. In this problem every one in a population of players has an initial endowment of a divisible good and a utility function for consuming all goods—own and others. Every player sells the entire initial endowment and then uses the revenue to buy a bundle of goods such that his or her utility function is maximized. Walras asked whether prices could be set for everyone’s good such that this is possible. An answer was given by Arrow and Debreu in 1954 [1] who showed that such equilibrium would exist if the utility functions were concave. Their proof was non-constructive and did not offer any algorithm to find such equilibrium prices.

Let be a undirected connected graph. Given a set of groups each being a subset of (), tree routing and coloring is to produce trees in and assign a color to each of them in such a way that all vertices in every group are connected by one of produced trees and no two trees sharing a common edge are assigned the same color. In this paper we study how to find a tree routing and coloring that uses minimal number of colors, which finds an application of setting up multicast connections in optical networks. We first prove Ω()-inapproximability of the problem even when is a mesh, and then we propose some approximation algorithms with provable performance guarantees for general graphs and some special graphs as well.

In this paper, we present three energy efficient broadcast and multicast routing algorithms for wireless ad hoc networks. The first algorithm computes a broadcast tree whose energy consumption is within a factor 2 + 2 ln ( – 1) of the optimal. The second algorithm computes a multicast tree whose energy consumption is within a constant factor of the optimal.Our third algorithm, for a multicast request with a given duration, computes an optimal multicast tree such that the minimal remaining energy of nodes is maximized after the multicast session. This algorithm helps to maximize the lifetime of the network.

In this paper we study an algorithm to find critical points of a lower semicontinuous nonconvex function. We use the Moreau regularization for a special type of functions belonging to the class of prox-regular functions which have very interesting algorithmic properties. We show that it is possible to generate an algorithm in order to obtain a critical point using the theory developed for the composite functions and also the results for the solutions of nonsmooth vectorial equations. We prove the convergence of the algorithm and some estimations of the convergence speed.

Competitive analysis for all investors in the Bahncard problem (a railway pass of the Deutsche Bundesbahn company) has received much attention in recent years. In contrast to this common approach, which selects the riskless outcome and achieves the optimal competitive ratio, this paper introduces a risk-reward competitive strategy to achieve flexibility. Namely, we extend the traditional competitive analysis to provide a framework in which the travellers can develop optimal trading strategies based on their risk tolerance and investing capability. We further present a surprisingly flexible competitive ratio of for the Bahncard problem, where is the risk tolerance and is the percentage of discount with respect to this strategy. Then substituting = 1 into the above equation, we obtain the (2 – )–competitive ratio which is the best attainable result presented by Fleischer.

In this paper we study the on-line production order disposal problem considering preemption and abortion penalty. We discuss the cases when orders have uniform and nonuniform lengths. For the case of uniform order length, the GR strategy is proved to be -competitive, where ≥ 0 is the coefficient of the punishment. For the case of nonuniform order lengths, GR is -competitive where is the ratio of length between the longest and shortest orders. When abortion penalty is not counted, the ER strategy is proposed and proved to be + + 1 -competitive, where ≈ 2.718. The result is much better than that of GR. We show that ER is not competitive when abortion penalty is counted.

University timetabling problem is a very common and seemingly simple, but yet very difficult problem to solve in practice. While solution definitely exists (evidenced by the fact that we do hold classes), an automated optimal schedule is very difficult to derive at present. There were successful attempts to address this problem using heuristics search methods. However, until now, university timetabling is still largely done by hand, because a typical university setting requires numerous customized complicated constraints that are difficult to model or automate. In addition, there is a problem of certain constraints being inviolable, while others are merely desirable. This paper intends to address the university timetabling problem that is highly constrained using Artificial Immune System. Empirical study on course timetabling for the School of Computer Engineering (SCE), Nanyang Technological University (NTU), Singapore as well as the benchmark dataset provided by the Metaheuristic Network shows that our proposed approach gives better results than those obtained using the Genetic Algorithm (GA).

In this paper we investigate two single machine scheduling problems. The first problem addresses a class of the two-stage scheduling problem in which the first stage is job production and the second stage is job delivery. For the case that jobs are processed on a single machine and delivered by a single vehicle to one customer area, with the objective of minimizing the time when all jobs are completed and delivered to the customer area and the vehicle returns to the machine, an approximation algorithm with a worst-case ratio of 5/3 is known and no approximation can have a worst-case of 3/2 unless = . We present an improved approximation algorithm with a worst-case ratio of 53/35, which only leaves a gap of 1/70. The second problem is a single machine scheduling problem subject to a period of maintenance. The objective is to minimize the total completion time. The best known approximation algorithm has a worst-case ratio of 20/17. We present a polynomial time approximation scheme.

It is wel-known that Nash considered the n-person noncooperative game with each player having finite strategic set and proved the celebrated existence result of Nash equilibrium point (in mixed strategies). This paper investigates the n-person noncooperative game with each player having infinite strategic set. By considering these infinite strategic as complete metric spaces and based on a new finite equilibrium system, we obtain new existence result of Nash equilibrium. Then an algorithm is given to compute Nash equilibrium points and its convergence is proved.