Laboratoire d’analyse et d’architecture des systèmes
Rapport de Contrat : EREMS Contract 67696 - Final report, Décembre 2017, 27p. , N° 17471
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
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.
I.HAMAZ, L.HOUSSIN, S.CAFIERI
Rapport LAAS N°17419, Décembre 2017, 21p.
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.
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
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.
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.
S.U.NGUEVEU , S.CAUX, F.MESSINE, M.GUEMRI
Revue Scientifique : 4OR: A Quarterly Journal of Operations Research, Vol.15, N°4, pp.407-430, Décembre 2017 , N° 17478
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.
I.HAMAZ, L.HOUSSIN, S.CAFIERI
Revue Scientifique : IFAC-PapersOnLine, Vol.20, N°1, pp.5012-5016, Novembre 2017 , N° 17402
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.
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
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.
Rapport LAAS N°17395, Octobre 2017, 32p.
M.FREY, R.KOLISCH, C.ARTIGUES
Revue Scientifique : Transportation Science, Vol.51, N°4, pp.1226-1241, Octobre 2017, https://doi.org/10.1287/trsc.2017.0739 , N° 17394
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.
LFU, M.A.ALOULOU, C.ARTIGUES
Revue Scientifique : Journal of Scheduling, 31p., Octobre 2017, DOI 10.1007/s10951-017-0542-0 , N° 16227
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.