Search

Your search keyword '"Rapine, Christophe"' showing total 114 results
Start Over Author "Rapine, Christophe"
114 results on '"Rapine, Christophe"'

1. Makespan Minimization for Scheduling on Heterogeneous Platforms with Precedence Constraints

Author

Fagnon, Vincent, Lucarelli, Giorgio, Rapine, Christophe, Goos, Gerhard, Series Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Carretero, Jesus, editor, Shende, Sameer, editor, Garcia-Blas, Javier, editor, Brandic, Ivona, editor, Olcoz, Katzalin, editor, and Schreiber, Martin, editor

Published
2024
Full Text
View/download PDF

4. Approximation Algorithms for the Open Shop Problem with Delivery Times

Author

Kacem, Imed and Rapine, Christophe

Subjects
Computer Science - Data Structures and Algorithms
Abstract

In this paper we consider the open shop scheduling problem where the jobs have delivery times. The minimization criterion is the maximum lateness of the jobs. This problem is known to be NP-hard, even restricted to only 2 machines. We establish that any list scheduling algorithm has a performance ratio of 2. For a fixed number of machines, we design a polynomial time approximation scheme (PTAS) which represents the best possible result due to the strong NP-hardness of the problem., Comment: The short version has been published in the Proceeding of Int Conf on Computers & Industrial Engineering (CIE46), 29-31 October 2016, Tianjin / China

Published
2017

15. Iterative approach for the clustering problem

Author

Rapine, Christophe, Trystram, Denis, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Bougé, Luc, editor, Fraigniaud, Pierre, editor, Mignotte, Anne, editor, and Robert, Yves, editor

Published
1996
Full Text
View/download PDF

16. Integrated cutting stock and batch replenishment problem

Author

Akbalik, Ayse, Silva, Elsa, Carravilla, Maria Antonia, Oliveira, José Fernando, Rapine, Christophe, and Sciencesconf.org, CCSD

Subjects
Lot Sizing Problem, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Cutting stock, [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], Batch replenishment
Abstract

We study the integrated Cutting Stock & Lot Sizing Problem (CS-LSP) for a manufacturer replenishing raw materials from suppliers using capacitated vehicles. Those raw materials can be rectangular panels in two-dimensional case and bars in one-dimension. Replenishment of those raw materials constitutes the lot sizing part : how many capacitated vehicles to order in each period from which supplier, while minimizing the total cost? The transformation of those raw materials into the end items consists in the cutting stock problem : how to cut each panel (or bar) to satisfy the final demand of the customers for different types of items, while minimizing the total number of raw materials used over the given time horizon? Both problems are integrated into the same model to obtain the global optimal solution respecting replenishment cost and constraints together with cutting stock cost and constraints. Note that the replenishment decisions directly impact the assortment of raw materials available in each period when solving the cutting stock problem. We propose a mixed integer linear programming (MILP) formulation for this integrated problem. We also study some special cases by decomposing it into subproblems to use some dynamic programming algorithms already existing in the literature

Published
2022

19. Two-stage flexible-choice problems under uncertainty

Author

MiheliA, Jurij, Mahjoub, Amine, Rapine, Christophe, and RobiA, Borut

Subjects
Hedging (Finance) -- Analysis, Hedging (Finance) -- Models, Mathematical optimization -- Analysis, Mathematical optimization -- Models, Algorithms -- Analysis, Algorithms -- Models, Algorithm, Business, Business, general, Business, international
Abstract

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2009.03.016 Byline: Jurij MiheliA (a), Amine Mahjoub (b), Christophe Rapine (c), Borut RobiA (a) Keywords: Complexity theory; Uncertainty modeling; Scenarios; Combinatorial optimization; Decision analysis; Network flows Abstract: A significant input-data uncertainty is often present in practical situations. One approach to coping with this uncertainty is to describe the uncertainty with scenarios. A scenario represents a potential realization of the important parameters of the problem. In this paper we apply a recent approach, called flexibility, to solving two-stage flexible-choice problems. The first stage represents the present, where a decision maker must plan ahead to make a decision to hedge against uncertainty in the second stage, which represents the uncertain future, and is described as a set of scenarios. When one of the future scenarios is realized, a decision maker is willing to pay some recourse cost to augment the earlier solution to be more suitable for the realized scenario. Since all of the future scenarios are known, it is reasonable to presume that their desired solutions are also known. Thus, the aim of a decision maker is to find a solution in the present that is as easy as possible to adapt to solutions in the future. In this paper we study the problem where feasible solutions of the first stage are all p-element subsets of some finite set, and the solutions of the second stage are fixed p-element subsets. We present computational complexity results and algorithms for two versions of the two-stage flexible-choice problem. We formally define both problems, i.e., the sum-flexibility problem and the max-flexibility problem. For the sum-flexibility problem we describe an exact polynomial-time algorithm for the 3-scenario version, and we show non-approximability for the 4-scenario version. For the max-flexibility problem we show that the 3-scenario version is NP-hard, but approximable within a constant performance guarantee. Additionally, we prove non-approximability for the 4-scenario version of the problem. Author Affiliation: (a) Faculty of Computer and Information Science, University of Ljubljana, Ljubljana, Slovenia (b) UTIC, Higher School of Sciences and Techniques of Tunis, Tunis, Tunisia (c) G-SCOP Laboratory, Grenoble, France Article History: Received 11 March 2008; Accepted 12 March 2009

Published
2010

21. An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints

Author

Sadfi, Cherif, Penz, Bernard, Rapine, Christophe, Blazewicz, Jacek, and Formanowicz, Piotr

Subjects
Machinery -- Usage, Magneto-electric machines -- Usage, Mathematical models -- Usage, Scheduling (Management), Business, Business, general, Business, international
Abstract

A mathematical model is presented for single machine scheduling duly taking into account the availability constraints, period of maintenance, and the worst-case error bounds.

Published
2005

23. Exact and approximation algorithms for multi-level in series lot-sizing problems with batch deliveries

Author

Goisque, Guillaume, Rapine, Christophe, and Goisque, Guillaume

Subjects
Computer Science::Machine Learning, dynamic programming, capacitated lot-sizing, multi-level lot-sizing, [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO]
Abstract

We present an exact dynamic algorithm running in polynomial time for the multi-level in series lot-sizing problem with batch deliveries where batch sizes are identical and stationary and an approximation algorithm for the case with time-dependent/level dependent batch sizes

Published
2017

24. Polynomial time algorithm for multi-level in series capacitated lot-sizing problems with constant batch size

Author

Goisque, Guillaume, Rapine, Christophe, and Goisque, Guillaume

Subjects
[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], Dynamic programing, Multi-level lot-sizing, Capacitated lot-sizing
Abstract

We consider a multi-level lot-sizing problem in a serial distribution network. Customers demands are to be satisfied at the last level of the network. At each level, units can be carried in stock, and the inventory is replenished from the upstream level using batch deliveries, where a fixed cost is incurred for each batch ordered. In addition, we also consider a limitation on the number of batches that can be ordered at any period. As far as we know, the status of this multi-level lot-sizing problem with batch deliveries and capacities on the size of the orders is open. Assuming stationary and identical batch sizes and capacities for all the levels, we derive some structural properties on the optimal policy, and propose a polynomial time algorithm based on a decomposition of the problem into induced connected components. Our algorithm is polynomial both in the length of the planning horizon and in the number of levels.

Published
2016

26. Approximation results for the two machine cross-docking problem

Author

Prot, Damien, Rapine, Christophe, Goldschmidt, Olivier, Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), and Rapine, Christophe

Subjects
[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2010

27. Connecting maximum air traffic density and colouration problems

Author

Prot, Damien, Rapine, Christophe, Constans, Sophie, Fondacci, Rémy, Rapine, Christophe, Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'ingénierie circulation transports (LICIT), and Institut National de Recherche sur les Transports et leur Sécurité (INRETS)-École Nationale des Travaux Publics de l'État (ENTPE)

Subjects
[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Published
2009

28. Graph decomposition into paths under length constraints

Author

Teypaz, Nicolas, Rapine, Christophe, Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), BQR INPG 'Optimisation du transport de fret par l'utilisation de plateformes logistiques', and Rapine, Christophe

Subjects
[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract

Given 2 integers a and b, we define an (a,b)-decomposition of a graph G =(V,E) as a partition of E into paths where the length of each path lies between a and b. In this definition paths are requested to be simple but not necessarily elementary. In other words an (a,b)-decomposition corresponds to a partition E1,...,Ek of E with a = 3, we identify 2 classes of graphs, trees and Eulerian graphs, for which the (a,b)-decomposition problem remains polynomial. However we prove that the (3,3)-decomposition problem is NP-complete, even on bipartite graphs. We give some evidence to conjecture that the more general H-decomposition problem into a given family H = H1,...,Hn of connected graphs is NP-complete if and only if all Hi-decomposition problems are NP-complete.

Published
2008

29. Polynomial time algorithms for constant capacitated lot sizing problems with equal length step-wise linear costs

Author

Akbalik, Ayse, Rapine, Christophe, Laboratoire des technologies de la microélectronique (LTM), Université Joseph Fourier - Grenoble 1 (UJF)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Centre National de la Recherche Scientifique (CNRS), Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Joseph Fourier - Grenoble 1 (UJF)-Centre National de la Recherche Scientifique (CNRS), and Rapine, Christophe

Subjects
[SPI.OTHER]Engineering Sciences [physics]/Other, [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], step-wise costs, [SPI.OTHER] Engineering Sciences [physics]/Other, Single-item capacitated lot sizing problem, polynomial time dynamic programming algorithm, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract

This paper presents polynomial time algorithms for three extensions of the classical capacitated lot sizing problem (CLSP). We consider a constant batch size production with a fixed cost associated to each batch, additionally to the production setup cost and a unit holding cost. The production cost can then be considered as a step-wise function where the step length corresponds to the batch size. We can no more use the efficient methods proposed for the CLSP with concave costs in order to solve the CLSP with step-wise costs. We propose several properties of optimal solutions. Based on these properties, three polynomial time algorithms are provided under the assumptions of constant production capacity and constant batch sizes, as well as linear and non-increasing production costs over time. The uncapacitated case is solved in time complexity O(T^3). For the constant capacitated case, with a production capacity multiple of the batch size, the algorithm has a time complexity in O(T^4). The final algorithm concerns the general constant capacitated case, and has a time complexity in O(T^6).

Published
2008

30. Multi-product location problem in a distribution network : fixed single product study

Author

Sripathomswat, K., De Laere, B., Rapine, Christophe, Cung, Van-Dat, Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), and Rapine, Christophe

Subjects
[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Published
2007

34. Parametrized complexity for single machine scheduling with forbidden start and completion times

Author

Gabay, Michaël, Brauner, Nadia, Rapine, Christophe, Gabay, Michaël, Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Génie Industriel, de Production et de Maintenance (LGIPM), and Université de Lorraine (UL)

Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], High Multiplicity, [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], Scheduling, Forbidden times, Parametrized Complexity, [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract

International audience; We consider a problem where tasks are independent and can neither begin nor end at some dates. The objective is to schedule the tasks on a single machine in order to minimize the makespan. This problem is NP-hard and does not belong to APX. We propose a fixed-parameter algorithm for a particular case of this problem. We show that this case is FPT even under High Multiplicity encoding.

Published
2013

35. Complexité paramétrée pour le problème d'ordonnancement sur une machine avec instants de début et fin interdits

Author

Gabay, Michaël, Brauner, Nadia, Rapine, Christophe, Gabay, Michaël, Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Génie Industriel, de Production et de Maintenance (LGIPM), and Université de Lorraine (UL)

Subjects
Contraintes de disponibilité, [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], Ordonnancement, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Complexité, High multiplicity
Abstract

National audience; Nous considérons le problème d'ordonnancement avec multiplicité des tâches et instants de début et fin des tâches interdits. Nous proposons un algorithme de résolution exacte en temps constant pour ce problème lorsque le nombre d'instants interdits est fixé et égal au nombre de type de tâches.

Published
2013

37. Approximation algorithms for continuous-review inventory problems with time-varying parameters

Author

Massonnet, Guillaume, Gayon, Jean-Philippe, Rapine, Christophe, Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Gestion et Conduite des Systèmes de Production (G-SCOP_GCSP), Laboratoire de Génie Industriel, de Production et de Maintenance (LGIPM), Université de Lorraine (UL), and Massonnet, Guillaume

Subjects
[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2012

38. A Constant Approximation for the One-Warehouse Multiretailers problem with backorder

Author

Massonnet, Guillaume, Gayon, Jean-Philippe, Rapine, Christophe, Stauffer, Gautier, Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Gestion et Conduite des Systèmes de Production (G-SCOP_GCSP), Laboratoire de Génie Industriel, de Production et de Maintenance (LGIPM), Université de Lorraine (UL), Optimisation Combinatoire (G-SCOP_OC), and Perruet, Marie Josèphe

Subjects
[MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2012

40. Modélisation et prise en compte de l'incertitude des conflits aériens dans la régulation de vitesse

Author

Rey, David, Rapine, Christophe, Fondacci, Rémy, Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Ingénierie Circulation Transport (LICIT), Institut Français des Sciences et Technologies des Transports, de l'Aménagement et des Réseaux (IFSTTAR)-École Nationale des Travaux Publics de l'État (ENTPE)-Université de Lyon, and Rey, David

Subjects
régulation de vitesse, trafic aérien, programmation mathématique, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], incertitude
Abstract

National audience; Dans cette communication nous abordons le problème de la régulation de vitesse des aéronefs sous la forme d'un problème d'optimisation avec le soucis de prendre en compte l'incertitude liée aux conflits aériens.

Published
2011

41. A simple and fast 2-approximation algorithm for the one warehouse multi-retailer problem

Author

Stauffer, Gautier, Massonnet, Guillaume, Rapine, Christophe, Gayon, Jean-Philippe, Reformulations based algorithms for Combinatorial Optimization (Realopt), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Gestion et Conduite des Systèmes de Production (G-SCOP_GCSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Informatique et Distribution (ID-IMAG), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Institut National Polytechnique de Grenoble (INPG)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut National Polytechnique de Grenoble (INPG)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF), and Stauffer, Gautier

Subjects
[SPI]Engineering Sciences [physics], [SPI] Engineering Sciences [physics], ComputerApplications_COMPUTERSINOTHERSYSTEMS
Abstract

International audience; We consider a well-known NP-hard deterministic inventory control problem: the One-Warehouse Multi-Retailer (OWMR) problem. We present a simple combinatorial algorithm to recombine the optimal solutions of the natural single-echelon inventory subproblems into a feasible solution of the OWMR problem. This approach yields a 3approximation. We then show how this algorithm can be improved to a 2-approximation by halving the demands at the warehouse and at the retailers in the subproblems. Both algorithms are purely combinatorial and can be implemented to run in linear time for traditional linear holding costs and quadratic time for more general holding cost structures. We finally show that our technique can be extended to the Joint Replenishment Problem (JRP) with backorders and to the OWMR problem with non-linear holding costs.

Published
2011

42. Technical Report on the Minimization of Potential Air Conflicts using Speed Control

Author

Rey, David, Rapine, Christophe, Fondacci, Rémy, El Faouzi, Nour-Eddin, Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Ingénierie Circulation Transport (LICIT), and Institut Français des Sciences et Technologies des Transports, de l'Aménagement et des Réseaux (IFSTTAR)-École Nationale des Travaux Publics de l'État (ENTPE)-Université de Lyon

Subjects
Air traffic management, speed control, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], optimization, mathematical programming
Abstract

This report provides an insight into the mathematical methods developed to model the speed regulation problem in Air Traffic Flow Management. The speed regulation problem aims at optimizing aircraft speeds along their flights in order to smooth the air traffic flow. We chose to develop a linear framework for the speed regulation problem therefore most of the techniques presented aim at providing a linear formulation of the model.

Published
2011

44. A MIP for potential conflicts minimization by speed regulations

Author

Rey, David, Rapine, Christophe, Constans, Sophie, Fondacci, Rémy, Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'ingénierie circulation transports (LICIT), Institut National de Recherche sur les Transports et leur Sécurité (INRETS)-École Nationale des Travaux Publics de l'État (ENTPE), and Rey, David

Subjects
[MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], ComputerApplications_COMPUTERSINOTHERSYSTEMS, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
Abstract

International audience; We address the speed regulation problem in air traffic management. Increasing the airspace capacity has become a priority in order to deal with future air traffic demand. We investigate automatic speed modulations for en-route flights. Focusing on aircraft crossing times at intersection points to ensure separation, speed regulation is turned into travel time control. We propose a mixed integer linear model to minimize potential conflicts, i.e. when two or more aircraft are below the separation norm. The promising results pave the way for reducing the air traffic controllers' workload.

Published
2010

45. A Mixed Integer Linear Model for Potential Conflict Minimization by Speed Modulations

Author

Rey, David, Rapine, Christophe, Constans, Sophie, Fondacci, Rémy, Rey, David, Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'ingénierie circulation transports (LICIT), and Institut National de Recherche sur les Transports et leur Sécurité (INRETS)-École Nationale des Travaux Publics de l'État (ENTPE)

Subjects
[MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC]
Abstract

International audience; As air traffic volume is growing around 5% each year in Europe it has become a priority to improve air traffic control in order to deal with tomorrow's air traffic configuration. In 2007 the SESAR (Single European Sky ATM Research) project was created under European Community law as an initiative to design the future of air traffic management over Europe. One of the objective of SESAR is to increase air traffic density and optimize flight route plans. This can be achieved through en-route deconfliction. Reducing the global number of conflicts through speed regulation has been tested in the ERASMUS project (En-Route Air traffic Soft Management Ultimate System) and efficiency of the concept has been analysed through tests and simulations. It provided many insights related to en-route control using speed variations hence becoming a solid reference. In this paper we develop a mixed integer linear model for a speed regulation problem that suits SESAR requirements. We focus on flights crossing times at intersection points rather than distance to ensure separation along our resolution. Speed regulation is thus converted into travel time control. Finally we propose an integer linear program aiming at minimizing the global potential conflict quantity by speed modulations.

Published
2010

46. Some graph issues for a sequenced air traffic flow

Author

Prot, Damien, Rapine, Christophe, Constans, Sophie, Fondacci, Rémy, Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'ingénierie circulation transports (LICIT), Institut National de Recherche sur les Transports et leur Sécurité (INRETS)-École Nationale des Travaux Publics de l'État (ENTPE), and Prot, Damien

Subjects
[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2008

47. Sensitivity analysis for one and m machines

Author

Mahjoub, Amine, Moukrim, Aziz, Rapine, Christophe, Sanlaville, Eric, Technologie de l'Information et de la Communication (UTIC), École Supérieure des Sciences et Technologies de Tunis, Heuristique et Diagnostic des Systèmes Complexes [Compiègne] (Heudiasyc), Université de Technologie de Compiègne (UTC)-Centre National de la Recherche Scientifique (CNRS), ROSP, Laboratoire de Génie Industriel, de Production et de Maintenance (LGIPM), Université de Lorraine (UL)-Université de Lorraine (UL), Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes (LIMOS), Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Université d'Auvergne - Clermont-Ferrand I (UdA)-SIGMA Clermont (SIGMA Clermont)-Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS), Université Le Havre Normandie (ULH), Normandie Université (NU)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA), J-C Billaut and A Moukrim and E Sanlaville, Sanlaville, Eric, SIGMA Clermont (SIGMA Clermont)-Université d'Auvergne - Clermont-Ferrand I (UdA)-Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Blaise Pascal - Clermont-Ferrand 2 (UBP), Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Université Le Havre Normandie (ULH), and Normandie Université (NU)

Subjects
[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2008

48. Lot-sizing in a serial distribution system with capacited in-system production flow

Author

Boissiere, Julien, Frein, Yannick, Rapine, Christophe, Laboratoire d'Informatique, Systèmes, Traitement de l'Information et de la Connaissance (LISTIC), Université Savoie Mont Blanc (USMB [Université de Savoie] [Université de Chambéry]), Gestion et Conduite des Systèmes de Production (G-SCOP_GCSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), and Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP)

Subjects
[SPI.OTHER]Engineering Sciences [physics]/Other, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2008
Full Text
View/download PDF

49. Une approche robuste pour la minimisation des risques de conflits aériens

Author

Prot, Damien, Rapine, Christophe, Constans, Sophie, Fondacci, Rémy, Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'ingénierie circulation transports (LICIT), Institut National de Recherche sur les Transports et leur Sécurité (INRETS)-École Nationale des Travaux Publics de l'État (ENTPE), and Prot, Damien

Subjects
[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Abstract

2p.; International audience

Published
2007

50. Operator Non-Availability Periods

Author

Brauner, Nadia, Finke, Gerd, Lehoux-Lebacque, Vassilissa, Rapine, Christophe, Potts, Chris, Strusevich, Vitaly, Brauner, Nadia, Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), University de Southampton, University of Southampton, University of Greenwich, and This research has been financed in part by the INTAS network 03-51-5501

Subjects
list algorithms, [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], G.2.1 Combinatorics, One-machine scheduling, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], operator non-availability, complexity
Abstract

12 pages; In scheduling literature, the notion of machine non-availability periods is well known, for instance for maintenance. In our case of planning chemical experiments, we have special periods (the week-ends, holidays, vacations) where the chemists are not available. However, human intervention by the chemists is required to handle the starting and termination of the experiments. This gives rise to a new type of scheduling problems, namely problems of finding schedules that respect the operator non-availability periods. These problems are analyzed on a single machine with the makespan as criterion. Properties are described and performance ratios are given for list scheduling algorithms.

Published
2007

Catalog

Books, media, physical & digital resources
See catalog results