Search results for "Operation"

Drivers-Inspired Ants for Solving the Vehicle Routing Problem with Time Windows

2016

International audience; In our study, we develop a method that merges two information sources within ants colony optimization heuristic. Namely artificial ants which occurs for short term optimization and transporter's vehicles that occurs in long term and continuous optimization toward solving the real-world vehicle routing problem. This study is supported by a transporter (Upsilon) of the region of l'Yonne in France and a transport and logistics software development company (Tedies). Our method suits for transporters that use human planners to make decisions about their tours and intending to move to computer planners without drastically upsetting the drivers habits. Hence, the pledge of …

in Informatique graphique, modélisation géométrique et animation

2007

International audience; no abstract

Scheduling independent stochastic tasks under deadline and budget constraints

2018

This article discusses scheduling strategies for the problem of maximizing the expected number of tasks that can be executed on a cloud platform within a given budget and under a deadline constraint. The execution times of tasks follow independent and identically distributed probability laws. The main questions are how many processors to enroll and whether and when to interrupt tasks that have been executing for some time. We provide complexity results and an asymptotically optimal strategy for the problem instance with discrete probability distributions and without deadline. We extend the latter strategy for the general case with continuous distributions and a deadline and we design an ef…

Scheduling coupled-tasks with incompatibility constraint: a bin-packing related problem

2014

International audience; We tackle the makespan minimization problem of coupled- tasks in presence of compatibility constraint. In particular, we focus on stretched coupled-tasks, i.e. coupled-tasks having the same sub-tasks execution time and idle time duration. We show the relationship with bin packing problems for some configurations, and study several problems in framework of complexity and approximation for which the topology of the compatibility graph is specific (star, chain, bipartite, . . .).

Pre-processings and Linear-Decomposition Algorithm to Solve the k-Colorability Problem

2004

International audience; We are interested in the graph coloring problem. We studied the effectiveness of some pre-processings that are specific to the k-colorability problem and that promise to reduce the size or the difficulty of the instances. We propose to apply on the reduced graph an exact method based on a linear-decomposition of the graph. We present some experiments performed on literature instances, among which DIMACS library instances.

Tourism-km: A variant of MMKP applied to the tourism domain

2012

International audience; We are interested in an original real-world problem coming from tourism field. We describe a modelling of the problem and propose a first approach that mixes knowledge management and operational research methods. Our algorithms have been implemented in order to produce tourism solutions that are not unique for a given request but that take into account the preferences of the tourist user and provide a personalized solution. We report computational results obtained on real-world instances.

Theoretical Aspects of Scheduling Coupled-Tasks in the Presence of Compatibility Graph

2012

International audience; This paper presents a generalization of the coupled-task sche-duling problem introduced by Shapiro \cite{Shapiro}, where considered tasks are subject to incompatibility constraints depicted by an undirected graph. The motivation of this problem comes from data acquisition and processing in a mono-processor torpedo used for underwater exploration. As we add the compatibility graph, we focus on complexity of the problem, and more precisely on the boundary between $\mathcal{P}$ and $\mathcal{NP}$-completeness when some other input parameters are restricted (e.g. the ratio between the durations of the two sub-tasks composing a task): we adapt the global visualization of …

Stratified Autocalibration of Cameras with Euclidean Image Plane

2020

International audience; This paper tackles the problem of stratified autocalibration of a moving camera with Euclidean image plane (i.e. zero skew and unit aspect ratio) and constant intrinsic parameters. We show that with these assumptions, in addition to the polynomial derived from the so-called modulus constraint, each image pair provides a new quartic polynomial in the unknown plane at infinity. For three or more images, the plane at infinity estimation is stated as a constrained polynomial optimization problem that can efficiently be solved using Lasserre's hierarchy of semidefinite relaxations. The calibration parameters and thus a metric reconstruction are subsequently obtained by so…

Prise de décision dynamique dans la sélection des maintenances des tournées de techniciens

2022

Geometric Optimal Control of Simple Quantum Systems

2011

International audience