The continuing increase in air travel demand combined with the saturation of air traffic networks lead to recurrent congestion episodes. Among the many elements responsible for the escalation of air traffic management costs, we focus particularly on the impact of conflict-resolution strategies that arise in congested networks. In air traffic control, a conflict occurs when two or more aircraft fly too close to one another. While many automated conflict-resolution methods have been proposed, most of them cannot be integrated without a profound revision of traffic control procedures as they lack interaction with air traffic controllers (ATCs). Recently, subliminal speed control has been shown to be a promising approach to reducing the impact of air conflicts onto ATCs' workload and potentially improve airspace capacity. From the perspective of airlines however, little has been done to quantify the impact of conflict-resolution strategies onto direct operating costs. We address this gap by introducing an innovative formulation for the aircraft collision avoidance problem, which integrates the economic profile of flights and promotes equitable solutions. We present a goal programming-based model designed to minimize the deviation from fair solutions during the resolution of potential conflicts. The performance of the model is evaluated using a fuel-equivalent conflict-resolution scheme, hence offering a sustainable framework to efficiently and equitably resolve air conflicts.

We study the integration of the carbon emission constraint into the single item uncapacitated lot sizing problem (ULSP) under the cap-and-trade policy. Besides a limitation on the total carbon emitted through the production and storage activities over the entire hoziron, the cap-and-trade policy allows the firm to buy and to sell carbon units in case of need or surplus. In addition to the classical lot sizing costs (setup cost, unit production and unit holding costs) we take into account a cost of buying and a cost of selling carbon units. The speculative trades are not allowed by assuming stationary prices both for selling and buying activities. With an unlimited budget assumption, we show that the problem is equivalent to the classical ULSP which is polynomially solvable. We study two budget constraints and we show the problem to be NP-hard in the ordinary sense under a limited budget assumption using a recent result in Helmrich et al., 2012. We also show that both problems under different budget constraints and carbon trade costs can be reduced to the problem studied in Helmrich et al., 2012.

We consider a well-known NP-hard deterministic inventory control problem: the One-Warehouse Multi-Retailer (OWMR) problem.We present a simple combinatorial algorithm to recombine the optimal solutions of the natural single-echelon inventory subproblems into a feasible solution of the OWMR problem.This approach yields a 3approximation.We then show how this algorithm can be improved to a 2-approximation by halving the demands at the warehouse and at the retailers in the subproblems.Both algorithms are purely combinatorial and can be implemented to run in linear time for traditional linear holding costs and quadratic time for more general holding cost structures.We finally show that our technique can be extended to the Joint Replenishment Problem (JRP) with backorders and to the OWMR problem with non-linear holding costs.

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 $\frac{3}{2}+\varepsilon$ for the minimization of the parallel execution time for any fixed $\varepsilon > 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 $\frac{1}{2}$.

We are concerned in this article with a decision problem of a company producing to order. The company receives commands with specific required delivery dates from different clients, and has to decide which commands should be accepted and which ones should be rejected. Each accepted command results in a benefit for the company, but this benefit is reduced by a financial penalty in case of tardy delivery. We study the static case of a portfolio of commands in a single resource environment. The objective is to determine the subset of the jobs to accept together with a schedule for them to maximize the total profit of the company, taking into account tardiness penalties. We present results on two cases of penalty functions, fixed and linear. For fixed penalties, we show that the problem can be seen as 1 /spl par//spl Sigma//spl omega//sub i/U/sub i/ problem. For linear penalties we propose a mixed integer formulation of the problem, and a fully polynomial time approximation scheme for a fixed sequence. We have also adapted 3 heuristics of the literature and give computational results.

We are concerned with a decision problem of a company producing to order. The company receives commands with specific required delivery dates from different clients, and has to decide which commands should be accepted and which ones should be rejected. Each accepted command results in a benefit for the company, but this benefit is reduced by a financial penalty in case of tardy delivery. We study the static case of a portfolio of commands in a single resource environment. The objective is to determine the subset of the jobs to accept together with a schedule for them to maximize the total profit of the company, taking into account tardiness penalties. We present results on two cases of penalty functions, fixed and linear. For fixed penalties, we show that the problem can be seen as 1|| /spl Sigma/ w/sub i/U/sub i/ problem. For linear penalties we propose a mixed integer formulation of the problem, and a fully polynomial time approximation scheme for a fixed sequence. We have also adapted 3 heuristics of the literature and give computational results.

A malleable task is a computational unit which may be executed on any arbitrary number of processors, its execution time depending on the amount of resources allotted to it.According to the standard behavior of parallel applications, we assume that the malleable tasks are monotonic, i.e. that the execution time is decreasing with the number of processors while the computational work increases.This paper presents a new approach for scheduling a set of independent malleable tasks which leads to a worst case guarantee of fi for the minimization of the parallel execution time, or makespan.It improves all other existing practical results including the two-phases method introduced by Turek et al.The main idea is to transfer the difficulty of a two phases method from the scheduling part to the allotment selection.We show how to formulate this last problem as a knapsack optimization problem.Then, the scheduling problem is solved by a dual-approximation which leads to a simple structure of two consecutive shelves.

This paper establishes the exact upper bound for Lawler's heuristic proving that its schedule of a UECT tree on m identical processors does not exceed an optimal solution by more than m/2 time units.