Retour au site du LAAS-CNRS

Abstract

We propose exact hybrid methods based on integer linear programming (ILP) and constraint programming (CP) for an integrated employee timetabling and job-shop scheduling problem. Each method we investigate uses a CP formulation associated with an LP relaxation. Under a CP framework, the LP relaxation is integrated into a global constraint using in addition reduced cost-based filtering techniques. We propose two CP formulations of the problem yielding two different LP relaxations. The first formulation is based on a direct representation of the problem. The second formulation is based on a decomposition in intervals of the possible operation starting times. We show the theoretical interest of the decomposition-based representation compared to the direct representation through the analysis of dominant schedules. Computational experiments on a set of randomly generated instances confirm the superiority of the decomposition-based representation. In both cases, the hybrid methods outperform pure CP for employee cost minimization while it is not the case for makespan minimization. The experiments also investigate the interest of the proposed integrated method compared to a sequential approach and show its potential for multiobjective optimization.

Abstract

SDMA (Spatial Division Multiple Access) is a principle of radio resource sharing that relies on the division of the space dimension into separated communication channels. It can be used with common Frequency DivisionMultiple Access (FDMA), Time Division Multiple Access (TDMA) or Code Division Multiple Access (CDMA) techniques. Main terrestrial communication standards already implement SDMA. SDMA basically relies on adaptive and dynamic beam-forming associated to a clever algorithm in charge of resource allocation. As satellite communication systems move towards an increasing number of users and a larger throughput for each of them, SDMA is one of the most promising techniques that can reach these two goals. This paper studies static Frequency Allocation Problems (FAP) in a satellite communication system involving a gateway connected to a terrestrial network and some user terminals located in a service area. Two scenarios are considered: one based on SDMA and the other based on usual spot coverage. We propose original integer linear programming formulations and greedy allocation algorithms for the FAP which involve unusual cumulative interference constraints. By considering the link budget of each user, the objective is to maximize the number of users that the system can serve. We show through computational experiments on realistic data that the FAP associated with the SDMA system can be solved efficiently, yielding substantial improvement compared to the traditional system.

Mots-Clés / Keywords

Abstract

In this paper we present a scheduling problem dealing with energy constraints (typically electrical energy). Mainly we propose an extension of specific resource constraint propagation techniques (known as "energy reasoning") to efficiently prune the search space and then to facilitate its resolution. We also present dominance rules and a branching scheme to solve the problem via tree search. Finally, computational results are provided.

Abstract

In this paper, we consider a frequency assignment problem occurring in a military context. The main originality of the problem pertains to its dynamic dimension: new communications requiring frequency assignments need to be established throughout a battlefield deployment. The problem resolution framework decomposes into three phases: assignment of an initial kernel of communications, dynamic assignment of new communication links and a repair process when no assignment is possible. Different solution methods are proposed and extensive computational experiments are carried out on realistic instances.

Mots-Clés / Keywords