173documents trouvés
Weight-based heuristics for constraint satisfaction and combinatorial optimization problems
M.J.HUGUET, P.LOPEZ, W.KAROUI
MOGISA
Revue Scientifique : Journal of Mathematical Modelling and Algorithms, Vol.11, N°2, pp.193-215, Juin 2012 , N° 12169
Lien : http://hal.archives-ouvertes.fr/hal-00660715
Diffusable
Plus d'informations
Abstract
In this paper, we propose mechanisms to improve instantiation heuristics by incorporating weighted factors on variables. The proposed weight-based heuristics are evaluated on several tree search methods such as chronological backtracking and discrepancy-based search for both constraint satisfaction and optimization problems. Experiments are carried out on random constraint satisfaction problems, car sequencing problems, and jobshop scheduling with time-lags, considering various parameter settings and variants of the methods.
Multi-site scheduling under production and transportation constraints
F.H'MIDA, P.LOPEZ
ESSTT, MOGISA
Rapport LAAS N°12205, Avril 2012, 31p.
Lien : http://hal.archives-ouvertes.fr/hal-00689097
Diffusable
Plus d'informations
Abstract
For the enterprises organized in several distributed production sites, usually, production scheduling models presume either an instantaneous delivery of products or an unlimited number of available vehicles for transporting products. However, the transportation of the intermediate products to the sites is an important activity within the whole process of manufacturing, and the efficient coordination of production and transportation becomes a challenging problem in the actual higher collaborative and competitive environments. This work focuses on the integrated production and transportation scheduling properly managing the resources capacity, material flows and temporal interdependencies between sites. A case-study is reported and the industrial problem under consideration is modeled as a Constraint Satisfaction Problem (CSP). Besides scheduling under resource constraints, the model presented in this paper expands the packing problem to the area of transportation operations scheduling. It is implemented under the constraint programming language CHIP V5. The provided solutions determine values for the various variables associated to the production and transportation operations realized on the whole multi-site, as well as the curves with the profile of the total consumption of resources in time.
Improved bounds for the hybrid flow shop problem with multiprocessor tasks
A.LAHIMER, P.LOPEZ, M.HAOUARI
INSAT Tunis, MOGISA
Rapport LAAS N°12186, Avril 2012, 24p.
Lien : http://hal.archives-ouvertes.fr/hal-00680452
Diffusable
Plus d'informations
Abstract
We investigate the problem of minimizing makespan in a multistage hybrid flow shop with multiprocessor tasks. To generate high-quality approximate solutions to this challenging NP-hard problem, we propose a new discrepancy search method that is based on adjacent discrepancies. Furthermore, we describe a new lower bound that is based on the concept of dual feasible functions. The proposed lower and upper bounds are assessed through computational experiments on 300 benchmark instances with up to 100 jobs and 8 stages. For these instances, the proposed lower and upper bounds consistently outperform the best existing ones. In particular, the proposed heuristic successfully improved the best known solution of 75 benchmark instances.
Plans sur la comète !
G.SIMONIN, C.ARTIGUES, E.HEBRARD, P.LOPEZ
MOGISA
Manifestation sans acte : Congrès Annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2012), Angers (France), 11-13 Avril 2012, 2p. , N° 12173
Diffusable
126982Problème de cross-docking en mode mixte
L.BERGHMAN, C.BRIAND, R.LEUS, P.LOPEZ
KU Leuven, MOGISA
Manifestation sans acte : Congrès Annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2012), Angers (France), 11-13 Avril 2012, 2p. , N° 12175
Diffusable
126986Optimisation multi-objectif des prises de vues d'un satellite agile d'observation de la terre
P.TANGPATTANAKUL, N.JOZEFOWIEZ, P.LOPEZ
MOGISA
Manifestation sans acte : Congrès Annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2012), Angers (France), 11-13 Avril 2012, 2p. , N° 12174
Diffusable
126984Complete characterization of near-optimal sequences for the two-machine flow shop scheduling problem
J.C.BILLAUT, E.HEBRARD, P.LOPEZ
LI, MOGISA
Rapport LAAS N°12171, Avril 2012, 16p.
Lien : http://hal.archives-ouvertes.fr/hal-00676783
Diffusable
Plus d'informations
Abstract
In a two-machine flow shop scheduling problem, the set of $\epsilon$-approximate sequences (i.e., solutions within a factor $1+\epsilon$ of the optimal) can be mapped to the vertices of a permutation lattice. We introduce two approaches, based on properties derived from the analysis of permutation lattices, for characterizing large sets of near-optimal solutions. In the first approach, we look for a sequence of minimum level in the lattice, since this solution is likely to cover many optimal or near-optimal solutions. In the second approach, we look for all sequences of minimal level, thus covering all $\epsilon$-approximate sequences. Integer linear programming and constraint programming models are first proposed to solve the former problem. For the latter problem, a direct exploration of the lattice, traversing it by a simple tree search procedure, is proposed. Computational experiments are given to evaluate these methods and to illustrate the interest and the limits of such approaches.
The truck scheduling problem at cross-docking terminals
L.BERGHMAN, C.BRIAND, R.LEUS, P.LOPEZ
KU Leuven, MOGISA
Manifestation avec acte : International Conference on Project Management and Scheduling (PMS 2012), Louvain (Belgique), 1-4 Avril 2012, pp.90-93 , N° 12027
Lien : http://hal.archives-ouvertes.fr/hal-00661318
Diffusable
Plus d'informations
Abstract
We study the general case of crossdocking, in which each dock can be used both for loading and unloading (so-called mixed mode). We propose a time-indexed linear programming formulation and a branch-and- bound algorithm to solve the problem.
Evaluation des performances des solveurs de programmation linéaire sur le problème du rendez-vous orbital impulsionnel
D.ARZELIER, N.JOZEFOWIEZ, P.LOPEZ, C.LOUEMBET
MAC, MOGISA
Rapport de Contrat : Convention CNES N° 104057/00, Novembre 2011, 43p. , N° 11605
Diffusable
125804Ordonnancement d'atelier de type flow shop hybride avec tâches multiprocesseurs
A.LAHIMER, P.LOPEZ, M.HAOUARI
MOGISA, INSAT Tunis
Manifestation avec acte : Congrès International de Génie Industriel (CIGI 2011), Saint Sauveur (Canada), 12-14 Octobre 2011, 7p. , N° 11462
Lien : http://hal.archives-ouvertes.fr/hal-00617532/fr/
Diffusable
Plus d'informations
Résumé
Cet article concerne la résolution d'un problème d'ordonnancement d'atelier complexe de type flowshop hybride avec tâches multiprocesseurs. Le critère à optimiser est la minimisation de la durée totale d'ordonnancement (makespan). Nous proposons une méthode de recherche arborescente à base de divergences pour le résoudre. La méthode est évaluée sur des jeux-tests en mesurant son pouvoir de résolution exacte ou l'écart à une borne. Une étude comparative est également menée avec d'autres méthodes de la littérature. Les résultats obtenus prouvent l'efficacité de notre approche notamment sur les grandes instances.