Retour au site du LAAS-CNRS

Laboratoire d’analyse et d’architecture des systèmes

Publications de l'équipe ROC

Choisir la langue : FR | EN

615documents trouvés

17471
26/12/2017

Algorithm for the power control and distribution unit - PCDU Nanosat

E.HEBRARD, C.ARTIGUES

ROC

Rapport de Contrat : EREMS Contract 67696 - Final report, Décembre 2017, 27p. , N° 17471

Non diffusable

141915
17126
06/12/2017

Complexity results and algorithms for an integrated single machine scheduling and outbound delivery problem with fixed sequence

A.CHEREF, A.AGNETIS, C.ARTIGUES, J.C.BILLAUT

ROC, UNISI, LI

Revue Scientifique : Journal of Scheduling, Vol.20, N°6, pp.681-693, Décembre 2017 , N° 17126

Lien : https://hal.archives-ouvertes.fr/hal-01529299

Diffusable

Plus d'informations

Abstract

In this paper, we consider an integrated production and outbound delivery scheduling problem. In particular, we address the situation in which the scheduling sequence and the delivery sequence are the same and predefined. A set of jobs are processed on a single machine and finished jobs are delivered to the customers by a single capacitated vehicle. Each job has a processing time and transportation times between customers are taken into account. Since the sequence is given, the problem consists to form batches of jobs and our objective is to minimize the sum of the delivery times or general functions of the delivery times. The NP-hardness of the general problem is established and a pseudopolynomial time dynamic programming algorithm is given. Some particular cases are treated, for which NP-hardness proofs and polynomial time algorithms are given. Finally, a fixed-parameter tractability result is given.

141652
17419
05/12/2017

Robust basic cyclic scheduling problem

I.HAMAZ, L.HOUSSIN, S.CAFIERI

ROC, ENAC

Rapport LAAS N°17419, Décembre 2017, 21p.

Lien : https://hal.archives-ouvertes.fr/hal-01635856

Diffusable

Plus d'informations

Abstract

This paper addresses the Basic Cyclic Scheduling Problem where the processing times are affected by uncertainties. We formulate the problem as a two-stage robust optimization problem with polyhedral uncertainty set. We propose three exact algorithms for solving the problem. Two of them use a negative circuit detection algorithm as a subroutine and the last one is an Howard's algorithm adaptation. Results of numerical experiments on randomly generated instances show that the Howard's algorithm adaptation yields efficient results and opens perspectives on more difficult robust cyclic scheduling problems.

141640
17434
04/12/2017

Inventory routing problems with explicit energy consideration

Y.HE

ROC

Doctorat : Université de Toulouse III - Paul Sabatier, 4 Décembre 2017, 188p., Président: , Rapporteurs: M.G.SPERANZA, F.SEMET, Examinateurs: N.ABSI, D.QUADRI, Directeurs de thèse: N.JOZEFOWIEZ, C.BRIAND , N° 17434

Lien : https://hal.laas.fr/tel-01675497

Diffusable

Plus d'informations

Résumé

Dans le problème de tournées avec gestion de stock ou “Inventory Routing Problem” (IRP), le fournisseur a pour mission de surveiller les niveaux de stock d’un ensemble de clients et gérer leur approvisionnement en prenant simultanément en compte les coûts de transport et de stockage. Etant données les nouvelles exigences de développement durable et de transport écologique, nous étudions l’IRP sous une perspective énergétique, peu de travaux s’étant intéressés à cet aspect. Plus précisément, la thèse identifie les facteurs principaux influençant la consommation d’énergie et évalue les gains potentiels qu’une meilleure planification des approvisionnements permet de réaliser. Un problème relatif à l’approvisionnement en composants de chaînes d’assemblage d’automobiles est tout d’abord considéré pour lequel la masse transportée, la dynamique du véhicule et la distance parcourue sont identifiés comme les principaux facteurs impactant la consommation énergétique. Ce résultat est étendu à l’IRP classique et les gains potentiels en termes d’énergie sont analysés. Un problème industriel de tournées avec gestion de stock est ensuite étudié et résolu, notamment à l’aide d’une méthode de génération de colonnes. Ce problème met en évidence les limitations du modèle IRP classique, ce qui nous a amené à définir un modèle d’IRP plus réaliste. Finalement, une méthode de décomposition basée sur la relaxation lagrangienne est développée pour la résolution de ce problème dans le but de minimiser la consommation énergétique.

Abstract

The thesis studies the Inventory Routing Problem (IRP) with explicit energy consideration. Under the Vendor Managed Inventory (VMI) model, the IRP is an integration of the inventory management and routing, where both inventory storage and transportation costs are taken into account. Under the new sustainability paradigm, green transport and logistics has become an emerging area of study, but few research focus on the ecological aspect of the classical IRP. Since the classical IRP concentrates solely on the economic benefits, it is worth studying under the energy perspective. The thesis gives an estimation of the energetic gain that a better supplying plan can provide. More specifically, this thesis integrates the energy consumption into the decision of the inventory replenishment and routing. It starts with a part supplying problem in car assembly lines, where the transported mass, the vehicle dynamics and the travelled distance are identified as main energy influencing factors. This result is extended to the classical IRP with energy objective to show the potential energy reduction that can be achieved. Then, an industrial challenge of IRP is presented and solved using a column generation approach. This problem put the limitations of the classical IRP model in evidence, which brings us to define a more realistic IRP model on a multigraph. Finally, a Lagrangian relaxation method is presented for solving this new model with the aim of energy minimization.

Mots-Clés / Keywords
Inventory routing problem; Logistics; Energy; Problème de tournées de véhicules avec gestion de stock; Logistique; Energie;

141693
17478
01/12/2017

Heuristics and lower bounds for minimizing fuel consumption in hybrid-electrical vehicles

S.U.NGUEVEU , S.CAUX, F.MESSINE, M.GUEMRI

ROC, LAPLACE

Revue Scientifique : 4OR: A Quarterly Journal of Operations Research, Vol.15, N°4, pp.407-430, Décembre 2017 , N° 17478

Lien : https://hal.archives-ouvertes.fr/hal-01671023

Diffusable

Plus d'informations

Abstract

In hybrid electric vehicles, the electrical powertrain system has multiple energy sources that it can gather power from to satisfy the propulsion power requested by the vehicle at each instant. This paper focusses on the minimization of the fuel consumption of such a vehicle, taking advantage of the different energy sources. Based on global optimization approaches, the proposed heuristics find solutions that best split the power requested between the multi-electrical sources available. A lower bounding procedure is introduced to validate the quality of the solutions. Computational results show a significant improvement over previous results from the literature in both the computing time and the quality of the solutions.

142053
17402
06/11/2017

Cyclic job shop problem with varying processing times

I.HAMAZ, L.HOUSSIN, S.CAFIERI

ROC, ENAC

Revue Scientifique : IFAC-PapersOnLine, Vol.20, N°1, pp.5012-5016, Novembre 2017 , N° 17402

Lien : https://hal-enac.archives-ouvertes.fr/hal-01626534

Diffusable

Plus d'informations

Abstract

In this paper, we consider a cyclic job shop problem where a subset of tasks have varying processing times. The minimum processing times and maximum processing times of these tasks are known. We propose a branch and bound method that finds the schedule which minimizes the mean cycle time with respect to variations. We show that the evaluation of a schedule can be considered as a volume calculus of some polytopes. Indeed, for each schedule we can associate a set of polytopes whose volumes provide information on the variation effect on the considered schedule.

141393
15361
01/11/2017

The multi-vehicle cumulative covering tour problem

D.A.FLORES-GARZA, M.A.SALAZAR-AGUILAR, S.U.NGUEVEU , G.LAPORTE

UANL, ROC, CIRRELT

Revue Scientifique : Annals of Operations Research, Vol.258, N°2, pp.761-780, Novembre 2017, doi 10.1007/s10479-015-2062-7 , N° 15361

Diffusable

Plus d'informations

Abstract

This paper introduces the multi-vehicle cumulative covering tour problem whose motivation arises from humanitarian logistics. The objective is to determine a set of tours that must be followed by a fleet of vehicles in order to minimize the sum of arrival times (latency) at each visited location. There are three types of locations: mandatory, optional, and unreachable. Each mandatory location must be visited, and optional locations are visited in order to cover the unreachable locations. To guarantee the vehicle autonomy, the duration of each tour should not exceed a given time limit. A mixed integer linear formulation and a greedy randomized adaptive search procedure are proposed for this problem. The performance of the algorithm is assessed over a large set of instances adapted from the literature. Computational results confirm the efficiency of the proposed algorithm.

141355
17395
31/10/2017

Minimum-fuel fixed time impulsive elliptic glideslope guidance algoriths using semidefinite programming

Y.ARIBA, D.ARZELIER

MAC, ROC

Rapport LAAS N°17395, Octobre 2017, 32p.

Diffusable

141372
17394
25/10/2017

Column generation for outbound baggage handling at airports

M.FREY, R.KOLISCH, C.ARTIGUES

Munchen, ROC

Revue Scientifique : Transportation Science, Vol.51, N°4, pp.1226-1241, Octobre 2017, https://doi.org/10.1287/trsc.2017.0739 , N° 17394

Lien : https://hal.archives-ouvertes.fr/hal-01614391

Diffusable

Plus d'informations

Abstract

The planning of outbound baggage handling at international airports is challenging. Outgoing flights have to be assigned and scheduled to handling facilities at which the outgoing baggage is loaded into containers. To avoid disruptions of the system the objective is to minimize workload peaks over the entire system. The resource demand of the jobs, which have to be scheduled, is depending on the arrival process of the baggage. In this paper we present a time-indexed mathematical programming formulation for planning the outbound baggage. We propose an innovative decomposition procedure in combination with a column generation scheme to solve practical problem instances. The decomposition significantly reduces the symmetry effect in the time-indexed formulation and also speeds up the computational time of the corresponding Dantzig-Wolfe formulation. To further improve our column generation algorithm we propose state-of-the-art acceleration techniques for the primal problem and pricing problem. Computational results based on real data from a major European Airport show that the proposed procedure reduces the maximal workloads by more than 60% in comparison to the current assignment procedure used.

141353
16227
25/10/2017

Integrated production and outbound distribution scheduling problems with job release dates and deadlines

LFU, M.A.ALOULOU, C.ARTIGUES

LAMSADE, ROC

Revue Scientifique : Journal of Scheduling, 31p., Octobre 2017, DOI 10.1007/s10951-017-0542-0 , N° 16227

Lien : https://hal.archives-ouvertes.fr/hal-01351929

Diffusable

Plus d'informations

Abstract

In this paper, we study an integrated production and outbound distribution scheduling model with one manufacturer and one customer. The manufacturer has to process a set of jobs on a single machine and deliver them in batches to the customer. Each job has a release date and a delivery deadline. The objective of the problem is to issue a feasible integrated production and distribution schedule minimizing the transportation cost subject to the delivery deadline constraints. We consider three problems with different ways how a job can be produced and delivered: non-splittable production and delivery (NSP-NSD) problem, splittable production and non-splittable delivery (SP-NSD) problem and splittable production and delivery (SP-SD) problem. We provide a polynomial-time algorithm that solves two special cases of SP-NSD and SP-SD problems. Solving these problems allows us to compute a lower bound for the NP-hard problem NSP-NSD, which we use in a branch and bound (B&B) algorithm to solve problem NSP-NSD. The computational results show that the B&B algorithm outperforms a MILP formulation of the problem implemented on a commercial solver. keywords: single machine scheduling production and delivery release dates deadlines transportation costs branch and bound.

141354
Les informations recueillies font l’objet d’un traitement informatique destiné à des statistiques d'utilisation du formulaire de recherche dans la base de données des publications scientifiques. Les destinataires des données sont : le service de documentation du LAAS.Conformément à la loi « informatique et libertés » du 6 janvier 1978 modifiée en 2004, vous bénéficiez d’un droit d’accès et de rectification aux informations qui vous concernent, que vous pouvez exercer en vous adressant à
Pour recevoir une copie des documents, contacter doc@laas.fr en mentionnant le n° de rapport LAAS et votre adresse postale. Signalez tout problème de dysfonctionnement à sysadmin@laas.fr. http://www.laas.fr/pulman/pulman-isens/web/app.php/