118documents trouvés
On integer linear programming formulations for the resource-constrained modulo scheduling problem
M.AYALA PEREZ, C.ARTIGUES
MOGISA
Rapport LAAS N°10393, Juillet 2010, 31p.
Lien : http://hal.archives-ouvertes.fr/hal-00538821/fr/
Diffusable
Plus d'informations
Abstract
The resource-constrained modulo scheduling problem (RCMSP) is a general periodic cyclic scheduling problem, abstracted from the problem solved by compilers when optimizing inner loops at instruction level for very long instruction word parallel processors. Since solving the instruction scheduling problem at compilation phase in less time critical than for real time scheduling, integer linear programming (ILP) is a relevant technique for the RCMSP. This paper shows theoretical evidence that the two ILP formulations used by practitioners are equivalent in terms of linear programming (LP) relaxation. Stronger formulations issued from Dantzig-Wolfe decomposition are presented. All formulations are compared experimentally on problem instances generated from real data. In terms of LP relaxation, the experiments corroborates the superiority of the new formulations on problems with non binary resource requirements.
Generalized resource constraint propagation for job shop scheduling with time lags
P.LOPEZ, M.J.HUGUET, C.ARTIGUES
MOGISA
Manifestation sans acte : European Conference on Operational Research (EURO XXIV), Lisbonne (Portugal), 11-14 Juillet 2010, 1p. (Résumé) , N° 10466
Diffusable
122218Vehicle routing problems with alternative paths: an application to demand responsive transports
T.GARAIX, C.ARTIGUES, D.FEILLET, D.JOSSELIN
MOGISA, UMR ESPACE, LIA Avignon
Revue Scientifique : European Journal of Operational Research, Vol.204, N°1, pp.62-75, Juillet 2010 , N° 06695
Lien : http://hal.archives-ouvertes.fr/hal-00109003
Diffusable
Plus d'informations
Abstract
The class of vehicle routing problems involves the optimization of freight or passenger transportation activities. These problems are generally treated via the representation of the road network as a weighted complete graph. Each arc of the graph represents the shortest route for a possible origin-destination connection. Several attributes can be dened for one arc (travel time, travel cost . . . ), but the shortest route modelled by this arc is computed according to one single criterion, generally travel time. Consequently, some alternative routes proposing a di erent compromise between the attributes of the arcs are discarded from the solution space. In this work, we propose to represent the road network with a multigraph, so that these alternative routes are considered, and to evaluate how it impacts on solution algorithms and solution values. A simple insertion algorithm is proposed and illustrated in the context of a on-demand transportation system developed in a French area. Computational experiments on academic and realistic data underline the potential cost savings brought by the multigraph model.
Bi-objective multimodal time-dependent shortest viable path algorithms
F.GUEYE, C.ARTIGUES, M.J.HUGUET
MOGISA
Manifestation avec acte : Triennial Symposium on Transportation Analysis (TRISTAN VII), Tromso (Norvège), 20-25 Juin 2010, pp.322-325 , N° 10028
Diffusable
121821Heuristic column generation for railroad track inspection scheduling
S.LANNEZ, C.ARTIGUES, J.DAMAY, M.GENDREAU
MOGISA, SNCF, CIRRELT
Manifestation avec acte : Triennial Symposium on Transportation Analysis (TRISTAN VII), Tromso (Norvège), 20-25 Juin 2010, pp.482-484 , N° 10853
Lien : http://hal.archives-ouvertes.fr/hal-00562593/fr/
Diffusable
Plus d'informations
Abstract
The problem we are solving is to visit a given set of tracks given that tracks can't be inspected all over the year and track outages can alter vehicles speed. Furthermore, vehicles speed depend on their type and circulation mode (either inspecting or not). These vehicles have limited capacity defined by the amount of water which can be brought on board. For organisational purposes, water tanks can only be refilled at the end of a shift and the objective is to minimise the total deadhead distance. We named this problem the Railroad Track Inspection Problem (RTISP).
Résolution du RCPSP avec production et consommation de ressources : modèles PLNE basés sur les événements
O.KONE, C.ARTIGUES, P.LOPEZ, M.MONGEAU
MOGISA, IMT, Toulouse
Manifestation avec acte : International Conference of Modeling and Simulation (MOSIM'10), Hammamet (Tunisie), 10-12 Mai 2010, 10p. , N° 10300
Lien : http://hal.archives-ouvertes.fr/hal-00484259/fr/
Diffusable
121423Une approche par la théorie des tas pour le jobshop cyclique
T.BEN RAHHOU, L.HOUSSIN, C.ARTIGUES
MOGISA
Manifestation avec acte : International Conference of Modeling and Simulation (MOSIM'10), Hammamet (Tunisie), 10-12 Mai 2010, 7p. , N° 10282
Diffusable
121417Flexible solutions in disjunctive scheduling: general formulation and study of the flow-shop case
M.A.ALOULOU, C.ARTIGUES
MOGISA, LAMSADE
Revue Scientifique : Computers & Operations Research, Vol.37, N°5, pp.890-898, Mai 2010, , N° 07036
Lien : http://hal.archives-ouvertes.fr/hal-00158669
Diffusable
Plus d'informations
Abstract
The purpose of this work is to provide the decision-maker a characterization of possible modifications of predictive schedules while preserving optimality. In the context of machine scheduling, the anticipated modifications are changes in the predictive order of operations on the machines. To achieve this goal, a flexible solution is provided. It represents a set of semi-active schedules and is characterized by a partial order on each machine, so that the total order can be set on-line, as required Flexible solutions in disjunctive scheduling [...] by the decision maker. A flexible solution is optimal if all the complete schedules that can be obtained by extension are also optimal. We consider the problem of evaluating the worst case performance of flexible solutions in disjunctive scheduling. We show that this problem can be modeled as an elementary longest path problem in the disjunctive graph representing the scheduling problem with additional constraints. In the flow-shop context, we give a polynomial algorithm to solve the problem and propose a method to issue optimal flexible solutions. Computational experiments show that significant flexibility is obtained.
Column generation based lower bounds for the resource constrained modulo scheduling
M.AYALA PEREZ, C.ARTIGUES
MOGISA
Manifestation avec acte : 12th International Workshop devoted to Project Management and Scheduling (PMS 2010), Tours (France), 26-28 Avril 2010, 4p. , N° 10221
Diffusable
121207Generalized Constraint Propagation for Solving Job Shop Problems with time lags
M.J.HUGUET, C.ARTIGUES, M. DUGAS, P.LOPEZ
MOGISA
Manifestation avec acte : 12th International Workshop devoted to Project Management and Scheduling (PMS 2010), Tours (France), 26-24 Avril 2010, 4p. , N° 10008
Diffusable
121203