118documents trouvés
Robust optimization for resource-constrained project scheduling with uncertain activity durations
C.ARTIGUES, R.LEUS, F.TALLA NOBIBON
MOGISA, KU Leuven
Revue Scientifique : Flexible Services and Manufacturing Journal, Vol.25, N°1-2, pp.165-205, Juin 2013 , N° 11084
Lien : http://hal.archives-ouvertes.fr/hal-00564435/fr/
Diffusable
Plus d'informations
Abstract
The purpose of this paper is to propose models for project scheduling when there is considerable uncertainty in the activity durations, to the extent that the decision maker cannot with confidence associate probabilities with the possible outcomes of a decision. Our modeling techniques stem from robust optimization, which is a theoretical framework that enables the decision maker to produce solutions that will have a reasonably good objective value under any likely input data scenario. We develop and implement a scenario-relaxation algorithm and a scenario-relaxation-based heuristic. The first algorithm produces optimal solutions but requires excessive running times even for medium-sized instances; the second algorithm produces high-quality solutions for medium-sized instances and outperforms two benchmark heuristics.
Comparison of mixed integer linear programming models for the resource-constrained project scheduling problem with consumption and production of resources
O.KONE, C.ARTIGUES, P.LOPEZ, M.MONGEAU
MOGISA, IMT, Toulouse
Revue Scientifique : Flexible Services and Manufacturing Journal, Vol.25, N°1-2, pp.25-47, Juin 2013 , N° 11085
Lien : http://hal.archives-ouvertes.fr/hal-00564443/fr/
Diffusable
Plus d'informations
Abstract
This paper addresses an extension of the resource-constrained project scheduling problem, which takes into account non-renewable resources. To solve this problem, we propose the generalization of two existing mixed integer linear programming models for the classical resourceconstrained project scheduling problem, as well as one novel formulation based on the concept of event. Computational results are reported to compare these formulations with each other.
A note on "event-based MILP models for resource-constrained project scheduling problems"
C.ARTIGUES, P.BRUCKER, S.KNUST, O.KONE, P.LOPEZ, M.MONGEAU
MOGISA, Osnabrück, Abobo-Adjame, ENAC
Revue Scientifique : Computers & Operations Research, Vol.40, N°4, pp.1060-1063, Avril 2013 , N° 12550
Diffusable
129004Propagation mechanism for a non-preemptive strictly periodic scheduling problem
C.PIRA, C.ARTIGUES
MOGISA
Rapport de Contrat : Projet LAAS OSEC & Région Midi-Pyrénée, allocation de recherche post-doctorant n° 11050523, Février 2013, 16p. , N° 13007
Lien : http://hal.archives-ouvertes.fr/hal-00784363
Diffusable
Plus d'informations
Abstract
We study a non-preemptive strictly periodic scheduling prob- lem. This problem, introduced in [6, 4], arises for example in the avionic field where a set of N periodic tasks (measure of a sensor, etc.) has to be scheduled on P processors distributed on the plane. In the related fi eld of cyclic scheduling, some notable success has been recently achieved through the use of speci c constraint propagation. In this article, we consider a heuristic, first proposed by Al Sheikh et al. 2012, which is based on the notion of equilibrium. Following a game theory analogy, each task tries successively to optimize its own schedule and therefore to produce the best response, given the other schedules. We present a propagation mechanism for non-overlapping constraints which signi cantly improves this heuristic.
An efficient best response heuristic for a non-preemptive strictly periodic scheduling problem
C.PIRA, C.ARTIGUES
MOGISA
Manifestation avec acte : Learning and Intelligent OptimizatioN Conference ( LION ) 2013 du 07 janvier au 11 janvier 2013, Catania (Italie), Janvier 2013, 15p. , N° 12668
Lien : http://hal.archives-ouvertes.fr/hal-00761345
Diffusable
Plus d'informations
Abstract
In this article, we study an original heuristic for a non- preemptive strictly periodic scheduling problem, based on the notion of equilibrium. This heuristic was first considered in Al Sheikh (2011). Our contribution is to greatly improve its efficiency through a complete redesign of its main method, which is the best response procedure.
Disruption management for commercial airlines: methods and results for the ROADEF 2009 Challenge
C.ARTIGUES, E.BOURREAU, H.AFSAR, O.BRIANT, M.BOUDIA
MOGISA, LIRMM, G-SCOP, AMADEUS
Revue Scientifique : European Journal of Industrial Engineering, Vol.6, N°6, pp.669-689, Novembre 2012 , N° 10486
Lien : http://hal.archives-ouvertes.fr/hal-00492035/fr/
Diffusable
129000The bi-objective multi-vehicle covering tour problem: formulation and lower bound by column generation
B.M.SARPONG, C.ARTIGUES, N.JOZEFOWIEZ
MOGISA
Rapport Local N°12562, 22p.
Diffusable
128266Scheduling scientific experiments on the Rosetta/Philae mission
G.SIMONIN, C.ARTIGUES, E.HEBRARD, P.LOPEZ
MOGISA
Manifestation avec acte : International Conference on Principles and Practice of Constraint Programming (CP) 2012 du 08 octobre au 12 octobre 2012, Québec (Canada), 2012, 15p. , N° 12344
Lien : http://hal.archives-ouvertes.fr/hal-00713858
Diffusable
Plus d'informations
Abstract
The Rosetta/Philae mission was launched in 2004 by the European Space Agency (ESA). It is scheduled to reach the comet 67P/ChuryumovGerasimenko in 2014 after traveling more than six billion kilometers. The Philae module will then be separated from the orbiter (Rosetta) to attempt the first ever landing on the surface of a comet. If it succeeds, it will engage a sequence of scientific exploratory experiments on the comet. In this paper we describe a constraint programming model for scheduling the different experiments of the mission. A feasible plan must satisfy a number of constraints induced by energetic resources, precedence relations on activities, or incompatibility between instruments. Moreover, a very important aspect is related to the transfer (to the orbiter then to Earth) of all the data produced by the instruments. The capacity of inboard memories and the limitation of transfers within visibility windows between lander and orbiter, make the transfer policy implemented on the lander's CPU prone to data loss. We introduce a global constraint to handle data transfers. The goal of this constraint is to ensure that data-producing activities are scheduled in such a way that no data is lost. Thanks to this constraint and to the filtering rules we propose, mission control engineers are now able to compute feasible plans in a few seconds for scenarios where minutes or even hours were previously often required. Moreover, in many cases, data transfers are now much more accurately simulated, thus increasing the reliability of the plans.
Frequency assignment in a SDMA satellite communication system with beam decentring feature
K.KIATMANAROJ, C.ARTIGUES, L.HOUSSIN, F.MESSINE
MOGISA, IRIT-ENSEEIHT
Rapport LAAS N°12284, Juin 2012, 17p.
Lien : http://hal.archives-ouvertes.fr/hal-00706037
Diffusable
Plus d'informations
Abstract
In satellite communication, Spatial DivisionMultiple Access (SDMA) has become one of the most promising techniques that can accommodate continuing increase in the number of users and traffic demands. The technology is based on radio resource sharing that separates communication channels in space. It relies on adaptive and dynamic beam-forming technology and well-designed algorithms for resource allocation among which frequency assignment is considered. This paper studies static Frequency Assignment Problem (FAP) in a satellite communication system involving a satellite and a number of users located in a service area. The objective is to maximize the number of users that the system can serve while maintaining the signal to interference plus noise ratio of each user under a predefined threshold. Traditionally, interference is treated as binary and fixed. In this paper, the interference is cumulative and variable. To solve the problem, we work on both discrete and continuous optimizations. Integer linear programming formulations and greedy algorithms are proposed for solving the discrete frequency assignment problem. The solution is further improved by beamdecentring algorithmwhich involves continuous adjustment of satellite beams and deals with non-linear change of interference.
Frequency allocation in a SDMA satellite communication system with beam moving
K.KIATMANAROJ, C.ARTIGUES, L.HOUSSIN, F.MESSINE
MOGISA, IRIT-ENSEEIHT
Manifestation avec acte : IEEE International Conference on Communications (ICC 2012), Ottawa (Canada), 10-15 Juin 2012, 5p. , N° 12324
Diffusable
127567