The growing adoption of electric vehicles (EVs) demands efficient scheduling of charging resources, particularly in multi-station networks with heterogeneous chargers and limited grid capacities. This study tackles the Multi-Station Electric Vehicle Charging Scheduling Problem (EVCSP), aiming to maximize satisfied charging demands while adhering to operational constraints. A novel mathematical model is proposed, extending single-station frameworks to accurately represent multi-station complexities. To address the scalability challenges of large instances, a hybrid memetic algorithm is developed, integrating evolutionary optimization with mathematical programming for energy allocation at individual stations. Computational experiments reveal that the mathematical model is highly effective for small-scale instances, providing optimal solutions efficiently. For larger scenarios, the hybrid memetic algorithm outperforms the model in scalability and solution quality, demonstrating its robustness for real-world applications. The proposed approaches advance the optimization of EV charging networks, offering scalable and practical solutions for modern transportation systems.

Electric vehicles (EVs) are pivotal to reducing greenhouse gas emissions, yet their growing adoption presents major challenges for power grid management. This paper addresses the NP-hard problem of scheduling EV charging at public stations, considering vehicles’ arrival/departure times and user-defined charging demands. Under power and charger constraints, the goal is to minimize the total deviation between requested and achieved state-of-charge levels. We propose a hybrid optimization framework that integrates a genetic algorithm with mathematical programming. To reduce computational cost, we further introduce a multi-surrogate-assisted approach that approximates the mathematical model. Simulation results demonstrate the effectiveness and efficiency of the proposed methods in solving large-scale EV charging scheduling problems.

The growing adoption of electric vehicles (EVs) necessitates efficient scheduling of charging operations to optimize limited infrastructure and maximize demand satisfaction. This study addresses the Electric Vehicle Charging Scheduling Problem (EVCSP) with the objective of maximizing the number of fulfilled charging requests. We propose two complementary solution frameworks. The first is an enhanced global mathematical programming model that captures the full problem structure and delivers high-quality solutions, even for large-scale instances. The second is a hybrid optimization approach that decomposes the problem into two interrelated components: EV-to-charger assignment and energy delivery optimization. A tabu search (TS) algorithm explores diverse assignment configurations, while each generated assignment is evaluated via exact mathematical programming to optimize energy allocation. Computational experiments show that both frameworks significantly outperform conventional approaches in solution quality and efficiency. These results highlight the potential of the proposed methods for scalable and effective EV charging management, supporting the operational needs of increasingly complex EV networks.

International audience

Large Neighborhood Search (LNS) is a widely used metaheuristic for solving complex combinatorial optimization problems, iteratively destroying and repairing parts of the solution to explore promising regions. In this paper, we introduce LNS-RL, an extension of LNS that enhances the search process by integrating a Deep Reinforcement Learning-based destroy operator. Our approach employs a Graph Attention Network (GAT) to capture spatial relationships among nodes and routes, trained using Proximal Policy Optimization (PPO). Experiments on Capacitated Vehicle Routing Problem (CVRP) benchmarks show that LNS-RL outperforms traditional LNS methods and surpasses state-of-the-art learning-based LNS approaches. Notably, incorporating route-level metrics into LNS-RL yields greater improvements compared to using node features alone. These results highlight the effectiveness of attention mechanisms and reinforcement learning, as well as the benefits of simultaneously integrating route- and node-level knowledge in LNS, which enhances information propagation during the search process, leading to more impactful destroy operator in complex routing problems.

In this paper, we present an improved methodology for scheduling electric vehicle (EV) charging at a single charging station, taking into account vehicle arrival and departure times, as well as drivers' charging requirements. The objective is to minimize the difference between desired and final state-of-charge levels while adhering to constraints on power capacity and charger availability. As electric vehicles increasingly contribute to mitigating greenhouse gas emissions, efficient charging strategies become crucial to manage their impact on the electrical grid. Our study delves into the complex task of scheduling EV charging at public stations, where drivers pre-communicate their charging needs. This study proposes improved solution methods, including a standalone mathematical programming model for scheduling, a hybrid heuristic algorithm for assignment, which combines mathematical modeling techniques for evaluation and energy allocation, and a hybrid tabu search algorithm, which uses the same mathematical model employed in the heuristic. Our results demonstrate the effectiveness of our approach in tackling the challenges of EV charging scheduling, highlighting its relevance for sustainable energy management.

This study delves into the electric vehicle charging scheduling problem within a public charging service station. The scheduling task entails managing charging demands from drivers, including arrival and departure times, current battery state-of-charge, and desired state-of-charge at departure. The scheduler must determine whether to accept or reject charging requests based on charger availability and the maximum grid capacity of the station. The primary objective is to minimize the cumulative discrepancy between the desired and final state-of-charge levels for all electric vehicles. To address this challenge, we introduce a novel architecture that harnesses the capabilities of population-based meta-heuristics as a promising method for identifying near-optimal solutions.

International audience

International audience

International audience

The Cloud computing paradigm is adopted for its several advantages like reduction of cost incurred when using a set of resources. Despite the many proven benefits of using a Cloud infrastructure to run business processes, it is still faced with a major problem that can compromise its success: the lack of guidance for choosing between multiple offerings. To ensure this, we propose a set of algorithms for business process scheduling in Cloud computing environments. More precisely, we propose an extension of our previous approaches taking into account the fact that several instances of the same process can run simultaneously, and they may have to share the same resources. The proposed approaches take into account the Cloud elasticity feature on the one hand, and on the other hand, they consider the two most important quality of service criteria when running business process in Clouds environment, namely (i) the overall execution time and (ii) the cost incurred using a set of resources. In addition they allow to ensure fairness between the different concurrent business process instances.

Although there are few efficient algorithms in the literature for scientific workflow tasks allocation and scheduling for heterogeneous resources such as those proposed in grid computing context, they usually require a bounded number of computer resources that cannot be applied in Cloud computing environment. Indeed, unlike grid, elastic computing, such asAmazon's EC2, allows users to allocate and release compute resources on-demand and pay only for what they use. Therefore, it is reasonable to assume that the number of resources is infinite. This feature of Clouds has been called âillusion of infiniteresourcesâ. However, despite the proven benefits of using Cloud to run scientific workflows, users lack guidance for choosing between multiple offering while taking into account several objectives which are often conflicting. On the other side, the workflow tasks allocation and scheduling have been shown to be NP-complete problems. Thus, it is convenient to use heuristic rather than deterministic algorithm. The objective of this paper is to design an allocation strategy for Cloud computing platform. More precisely, we propose three complementary bi-criteria approaches for scheduling workflows on distributed Cloud resources, taking into account the overall execution time and the cost incurred by using a set of resources.

Resources allocation and scheduling has been recognised as an important topic for business process execution. However, despite the proven benefits of using Cloud to run business process, users lack guidance for choosing between multiple offering while taking into account several objectives which are often conflicting. Moreover, when running business processes it is difficult to automate all tasks. In this paper, we propose three complementary approaches for Cloud computing platform. On the other side, elastic computing, such as Amazon EC2, allows users to allocate and release compute resources (virtual machines) on-demand and pay only for what they use. Therefore, it is reasonable to assume that the number of virtual machine is infinite while the number of human resources is finite. This feature of Clouds has been called “illusion of infinite resources”. In this paper, we design an allocation strategy for Cloud computing platform taking into account the above characteristics. More precisely, we propose three complementary bi-criterion approaches for scheduling business process on distributed Cloud resources.

In most manufacturing and distribution systems, semi-finished jobs are transferred from one processing facility to another and finished jobs are delivered to customers or warehouse by vehicles such as trucks. The paper investigates flow shop scheduling problems that explicitly consider constraints on both transportation and buffer capacities. These elements enable the flexible manufacturing systems (FMS) to process different types of parts. The finished jobs leave the processing facility to be delivered to customers or sent to warehouses by vehicles such as trucks. The objective function that is considered is makespan C/sub max/. We prove that this problem is strongly NP-hard when the capacity of truck is equal to two with unlimited buffer behind each machine. This problem with additional constraints, such as blocking, is also proved to be NP-hard.