In deep space missions, scientific data generated by onboard instruments must be temporarily stored in local memory buffers before being downlinked to Earth during limited communication windows. Efficient scheduling of these data transfers is essential to prevent buffer overflows and data loss, particularly in the presence of uncertainties. Previous work has considered the overlapping Memory Dumping Problem (oMDP), which consists in assigning transfer priorities to the memory buffers and minimize the peaks memory usage, which reduces the risk of overflow. In this paper, we consider a dditional decisions in the transfer plans that are implementable in practice: data transfer from each buffer can be interrupted after a given time, once per downlink window, preventing it from dumping data until the next window, but redistributing the unused bandwidth to the other buffers. The new problem is called oMDPi (oMDP with interruptions). We obtain new complexity results, showing that oMDPi is NP-complete for at least two windows. While the complexity status of the single window oMDPi remains open, we propose a polynomial-time heuristic to solve it. We propose a hybrid heuristic to solve the general oMDPi, embedding a flow relaxation and a single window heuristic. The results on both real and realistic generated instances show that our heuristic achieves a significant reduction of memory peaks in a reasonable time compared to previous works, making the new policy attractive for future space missions.

Meilleur papier étudiant de la conférence ICORES-2024

International audience

We introduce a variant of the cumulative scheduling problem (CuSP) characterized by continuous modes, time windows, and a criterion that involves safety margin maximization. The study of this variant is motivated by the Geospatial based Environment for Optimisation Systems Addressing Fire Emergencies Horizon 2020 Project, which is devoted to the design of evacuation plans in the face of natural disasters and more specifically, wildfire. People and goods have to be transferred from endangered places to safe places, and evacuation planning consists of scheduling evacuee moves along precomputed paths under arc capacities and deadlines. The resulting model is relevant in other contexts, such as project or industrial process scheduling. We consider here several formulations of the continuous time-resource trade-off scheduling problem (CTRTP-TW) with a safety maximization objective. We establish a complete complexity characterization distinguishing polynomial and NP-hard special cases depending on key parameters. We show that the problem with fixed sequencing (i.e., with predetermined overlap or precedence relations between activities) is convex. We then show that the preemptive variant is polynomial, and we propose lower and upper bounds based on this relaxation. A flow-based mixed-integer linear programming formulation is presented, from which a branch-and-cut exact method and an insertion heuristic are derived. An exact dedicated branch-and-bound algorithm is also designed. Extensive computational experiments are carried out to compare the different approaches on evacuation planning instances and on general CTRTP-TW instances. The experiments also show the interest of the continuous model compared with a previously proposed discrete approximation. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This work was funded by the Horizon 2020 Marie Skłodowska-Curie Research and Innovation Staff Exchange European Project 691161 GEO-SAFE (Geospatial based Environment for Optimisation Systems Addressing Fire Emergencie). This work has also been supported by ANITI, the Artificial and Natural Intelligence Toulouse Institute. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0142 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0142 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Multi skill resource-constrained project scheduling Problems (MS-RCPSP) have been object of studies from many years. Also, preemption is an important feature of real-life scheduling models. However, very little research has been investigated concerning MS-RCPSPs including preemption, and even less research moving out from academic benchmarks to real problem solving. In this paper we present a solution to those problems based on a hybrid method derived from large neighborhood search incorporating constraint programming components tailored to deal with complex scheduling constraints. We also present a constraint programming model adapted to preemption. The methods are implemented in a new open source python library allowing to easily reuse existing modeling languages and solvers. We evaluate the methods on an industrial case study from aircraft manufacturing including additional complicating constraints such as generalized precedence relations, resource calendars and partial preemption on which the standard CP Optimizer solver, even with the preemption-specific model, is unable to provide solutions in reasonable times. The large neighborhood search method is also able to find new best solutions on standard multi-skill project scheduling instances, performing better than a reference method from the literature.

The Hydro Unit Commitment problem (HUC) specific to hydroelectric plants is part of the electricity production planning problem, called Unit Commitment Problem (UCP).More specifically, the studied case is that of the HUC with a single plant, denoted 1-HUC.The plant is located between two reservoirs.The horizon is discretized in time periods.The plant operates at a finite number of points defined as pairs of the generated power and the corresponding water flow.Several constraints are considered.Each reservoir has an initial volume, as well as window resource constraints, defined by a minimum and maximum volume per time period.At each time period, there is an additional positive, negative or zero intake of water in the reservoirs.The case of a price-taker revenue maximization problem is considered.An efficient exact A* variant, so called HA*, is proposed to solve the 1-HUC accounting for window constraints, with a reduced search space and a dedicated optimistic heuristic.This variant is compared to a classical Resource Constrained Shortest Path Problem (RCSPP) algorithm and a Mixed Integer Linear Programming formulation solved with CPLEX.Results show that the proposed algorithm outperforms both concurrent alternatives in terms of computational time in average on a set of realistic instances, meaning that HA* exhibits a more stable behavior with a larger number of instances solved.

Long range space missions, such as Rosetta, require robust plans of data-acquisition activities and of the resulting data transfers. In this paper we revisit the problem of assigning priorities to data transfers in order to maximize safety margin of onboard memory. We propose a fast sweep algorithm to verify the feasibility of a given priority assignment and we introduce an efficient exact algorithm to assign priorities on a single downlink window. We prove that the problem is NP-hard for several windows, and we propose several randomized heuristics to tackle the general case. Our experimental results show that the proposed approaches are able to improve the plans computed for the real mission by the previously existing method, while the sweep algorithm yields drastic accelerations.

International audience

International audience

International audience

International audience

In this paper, we study an integrated production an outbound delivery scheduling problem with a predefined sequence. The manufacturer has to process a set of jobs on a single machine and deliver them in batches to multiple customers. A single vehicle with limited capacity is used for the delivery. Each job has a processing time and a specific customer location. Starting from the manufacturer location, the vehicle delivers a set of jobs which constitute a batch by taking into account the transportation times. Since the production sequence and delivery sequence are fixed and identical, the problem consists in deciding the composition of batches. We prove that for any regular sum-type objective function of the delivery times, the problem in NP-hard in the ordinary sense and can be solved in pseudopolynomial time. A dynamic programming algorithm is proposed.

In this article, we address a real life optimization problem, the rail track inspection scheduling problem. This problem consists of scheduling railway network inspection tasks. The objective is to minimize the total deadhead distance while performing all inspection tasks. Different 0–1 integer formulations for the problem are presented. A heuristic based on both Benders and Dantzig‐Wolfe decompositions is proposed to solve this rich arc routing problem. Its performance is analyzed on a real life dataset provided by the French national railway company. The proposed algorithm is compared to a dynamic programming‐based heuristic. Its ability to schedule the inspection tasks of 1 year on a sparse graph with thousand nodes and arcs is assessed. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(1), 40–56 2015

Carpooling is an appropriate solution to address traffic congestion and to reduce the ecological footprint of the car use. In this paper, we address an essential problem for providing dynamic carpooling: how to compute the shortest driver's and passenger's paths. Indeed, those two paths are synchronized in the sense that they have a common subpath between two points: the location where the passenger is picked up and the one where he is dropped off the car. The passenger path may include time-dependent public transportation parts before or after the common subpath. This defines the 2 Synchronization Points Shortest Path Problem (2SPSPP). We show that the 2SPSPP has a polynomial worst-case complexity. However, despite this polynomial complexity, one needs efficient algorithms to solve it in realistic transportation networks. We focus on efficient computation of optimal itineraries for solving the 2SPSPP, i.e. determining the (optimal) pick-up and drop-off points and the two synchronized paths that minimize the total traveling time. We also define restriction areas for reasonable pick-up and drop-off points and use them to guide the algorithms using heuristics based on landmarks. Experiments are conducted on real transportation networks. The results show the efficiency of the proposed algorithms and the interest of restriction areas for pick-up or drop-off points in terms of CPU time, in addition to its application interest.

Column generation has been very useful in solving single objective vehicle routing problems (VRPs). Its role in a branch-and-price algorithm is to compute a lower bound which is then used in a branch-and-bound framework to guide the search for integer solutions. In spite of the success of the method, only a few papers treat its application to multi-objective problems and this paper seeks to contribute in this respect. We study how good lower bounds for bi-objective VRPs in which one objective is a min-max function can be computed by column generation. A way to model these problems as well as a strategy to effectively search for columns are presented. We apply the ideas to two VRPs and our results show that strong lower bounds for this class of problems can be obtained in "reasonable" times if columns are intelligently managed. Moreover, the quality of the bounds obtained from the proposed model are significantly better than those obtained from the corresponding "standard" approach.

Spatial Division Multiple Access (SDMA) is a principle of radio resource sharing that separates communication channels in space. It relies on adaptive and dynamic beam-forming technology and well-designed algorithms for resource allocation. As satellite communication systems move towards greater capacity in both the number of users and throughput, SDMA becomes one of the most promising techniques that can achieve these two goals. This paper studies static Frequency Assignment Problem (FAP) in a satellite communication system involving a satellite and a number of users located in a service area. The objective is to maximize the number of users that the system can serve while maintaining the signal to interference plus noise ratio of each user under a predefined threshold. Traditionally, interference is binary and fixed. In this paper, the interference is cumulative and variable depending on how the frequency is assigned. To solve the problem, we work on both discrete and continuous optimizations. Integer linear programming formulations and greedy algorithms are proposed for solving the discrete frequency allocation problem. The solution is further improved by beam moving algorithm which involves continuous adjustment of satellite beams and deals with non-linear change of interference.

In this paper we address a real world optimisation problem, the Rail Track Inspection Scheduling Problem (RTISP). This problem consists of scheduling network inspection tasks. The objective is to minimise total deadhead distance. A mixed integer formulation of the problem is presented. A column generation based algorithm is proposed to solve this rich arc routing problem. Its performance is analysed by benchmarking a real world dataset from the French national railway company (SNCF). The efficiency of the algorithm is compared to an enhanced greedy algorithm. Its ability to schedule one year of inspection tasks on a sparse graph with thousand nodes, arcs and edges is assessed.

We propose a cooperation method between constraint programming and integer programming to compute lower bounds for the resource-constrained project scheduling problem (RCPSP). The lower bounds are evaluated through linear-programming (LP) relaxations of two different integer linear formulations. Efficient resource-constraint propagation algorithms serve as a preprocessing technique for these relaxations. The originality of our approach is to use additionally some deductions performed by constraint propagation, and particularly by the shaving technique, to derive new cutting planes that strengthen the linear programs. Such new valid linear inequalities are given in this paper, as well as a computational analysis of our approach. Through this analysis, we also compare the two considered linear formulations for the RCPSP and confirm the efficiency of lower bounds computed in a destructive way.