Search

We address the conflict resolution problem in air traffic management. It is widely acknowledged that air traffic controllers' (ATCs) workload is related to the density of flights. ATCs' main task is to ensure the safety of flights throughout their trips and consists of ensuring the respect of separation standards. Recently, the concept of subliminal control has emerged as a promising conflict resolution technique that could be used to reduce the impact of conflicts on ATCs' workload. In this research, we present deterministic conflict resolution models adapted to subliminal speed control. The proposed models are formulated as nonlinear optimization problems that seek to minimize indicators related to ATCs' workload (total conflict duration, total number of conflicts) using only minor speed adjustments. We introduce a linear approximation of the aircraft separation equations to implement the obtained mixed integer programs on a continental size air traffic network. Specifically, we develop a simulation framework aiming at reproducing realistic navigation conditions and evaluate the robustness of our conflict resolution models using a generic uncertainty model. We show that the impact of conflicts on ATCs' workload can be significantly reduced using only limited resources, i.e., a narrow speed modulation range, even in the presence of perturbations. Further, we demonstrate that a significant share of the potential conflicts can be resolved without inducing important delays to flights. Finally, we report that our model does not require extensive computational resources as most instances can be solved to global optimality in a few seconds. [ABSTRACT FROM AUTHOR]

A malleable task is a computational unit that may be executed on any arbitrary number of processors, whose execution time depends on the amount of resources allotted to it. This paper presents a new approach for scheduling a set of independent malleable tasks which leads to a worst case guarantee of 3⁄2 + ϵ for the minimization of the parallel execution time for any fixed ϵ > 0. The main idea of this approach is to focus on the determination of a good allotment and then to solve the resulting problem with a fixed number of processors by a simple scheduling algorithm. The first phase is based on a dual approximation technique where the allotment problem is expressed as a knapsack problem for partitioning the set of tasks into two shelves of respective heights 1 and ⅛ [ABSTRACT FROM AUTHOR]

In this paper, we study the single-item and the multi-item capacitated lot sizing problem in presence of inventory bounds (CLSP-IB). That is, in any period, both the quantity produced and the stock on hand are limited. For the single-item CLSP-IB with a stationary production capacity, time-dependent inventory bounds and concave costs, we show that the problem can be solved in time $$O(T^4)$$ by adapting a well-known algorithm in the literature. Restricting to non-speculative costs, we propose an $$O(T^3)$$ time dynamic programming algorithm. For the multi-item CLSP-IB, we consider the lot-sizing problem with item dedicated machines and a common capacitated storage space shared by all the items. We show that this problem is $$\text{ NP }$$ -hard in the strong sense even if all the cost parameters and capacities of the instance are stationary and identical for each item. [ABSTRACT FROM AUTHOR]

We study the problem of scheduling on k identical machines a set of parallel tasks with release dates and deadlines in order to maximize simultaneously two criteria, namely the Size (number of scheduled tasks) and the Weight (sum of the weights of scheduled tasks). If no task requires more than half of the machines, we construct schedules that are simultaneously approximations for the Size and the Weight by combining two approximate schedules, one for each parameter. We obtain existence results and polynomial time bicriteria approximation algorithms in contiguous and non contiguous models. [ABSTRACT FROM AUTHOR]