This paper tackles the Green Vehicle Routing Problem (GVRP), where vehicles with limited driving range must visit customers while recharging at Alternative Fuel Stations (AFSs). We propose a Multi-Start Tabu Search with Set Partitioning (MSTS-SP) approach structured in two phases. In the first phase, MSTS-SP uses a new constructive heuristic, Randomized Sectoring with Repair, to generate diverse initial solutions, which are then improved through multiple independent tabu search runs. The high-quality routes found during these runs are collected into a global pool. In the second phase, an exact set partitioning model is applied to this pool to select the best combination of routes. Computational experiments on 52 GVRP benchmark instances show that MSTS-SP matches 46 known best solutions (88%) and improves upon the best known solution for one large instance. These results demonstrate that MSTS-SP offers a competitive balance between solution quality and computational efficiency compared to state-of-the-art methods.

In this study, we investigate the real-world scheduling problem of the Medical Day Unit of the Emergency Department (MDU-ED) of Jeanne de Flandres University Hospital in Lille (France). We implemented a heuristic (PRH) based on hospital practitioners' rules we collected by observing the operation of MDU-ED. We propose an Integer Linear Programming (ILP) formulation that makes it feasible to solve small instances. We propose an Adaptive Iterative Destruction Construction Heuristic (IDCH) solution approach. The IDCH obtains better solutions than the PRH within reasonable processing times. We report on experiments performed on instances generated using real-world patient pathways of the MDU-ED.

The Two-Echelon Vehicle Routing Problem (2E-VRP) is a variant of the classical vehicle routing problem arising in the context of city logistics. In the 2E-VRP, freight from a main depot is delivered to final customers using intermediate facilities, called satellites. In this paper, we propose a new hybrid heuristic method for solving the 2E-VRP that relies on two components. The first component effectively explores the search space in order to discover a set of interesting routes. The second recombines the discovered routes into high-quality solutions. Experimentations on benchmark instances show the performance of our approach: our algorithm achieves high-quality solutions in short computational times and improves the current best known solutions for several large scale instances.

We address the flow-shop scheduling problem with two machines and time delays in order to minimize the makespan, i.e, the maximum completion time. We propose an exact algorithm based on a branch-and-bound enumeration scheme, for which we introduce a heuristic method based on a local search technique and three dominance rules. Finally, we present a computer simulation of the branch-and-bound algorithm, which was carried out on a set of 360 instances. The results show that our branch- and-bound method outperforms the state of the art exact method.

This paper describes an efficient exact algorithm to solve the Resource Constrained Project Scheduling Problem (RCPSP). We propose an original and efficient branch and price procedure which involves minimal interval order enumeration as well as constraint propagation and which is implemented with the help of the generic SCIP software. We perform tests on the famous PSPLIB instances which provide very satisfactory results.

An examination timetabling problem taken from real world universities was proposed at the International Timetabling Competition (ITC2007). The aim was to establish a common base for comparing different solution approaches. This paper presents new preprocessing methods that disclose hidden constraints and significantly increase the number of new edges that can be added to the conflict graph. Results show that the size of the maximum clique of the obtained conflict graph has been more than doubled for two instances as a result of our preprocessing. These larger cliques mean that instances can be analyzed in advance of a solution and end users gain useful information for making decisions. In addition, we have looked at the different criteria that compose the objective function, in order to provide more useful insights into the difficulty of problems in practice. We propose new integer programming formulations using clique inequalities to compute optimal solutions for 4 criteria and to obtain lower bounds for the 3 others. Results are presented and discussed for all the benchmark instances.

We consider the problem of determining whether a given set of rectangular items can be cut from a larger rectangle using so-called guillotine cuts only. We introduce a new class of arc-colored directed graphs called guillotine graphs and show that each guillotine graph can be associated with a specific class of pattern solutions that we call a guillotine-cutting class. The properties of guillotine graphs are examined, and some effective algorithms for dealing with guillotine graphs are proposed. As an application, we then describe a constraint programming method based on guillotine graphs, and we propose effective filtering techniques that use the graph model properties in order to reduce the search space efficiently. Computational experiments are reported on benchmarks from the literature: our algorithm outperforms previous methods when solving the most difficult instances exactly.

Scheduling of unit execution time (UET) task systems on parallel machines with minimal schedule length is known to be NP-complete. The problem is polynomially solvable for some special cases. For a fixed number of parallel machines m > 2, the complexity of the problem is still open, but the problem becomes NP-hard if m is arbitrary. In this paper we characterize a new order class that properly contains quasi-interval orders and we prove that the Coffman--Graham algorithm yields optimal schedules for this new class on any number of machines. Finally, some extensions are discussed for a larger order class and for scheduling in the presence of unit communication delays.

Scheduling of Unit Execution Time task systems on parallel machines, aiming at minimal schedule length is known to be NP-complete. The problem is polynomially solvable for some special cases. For a fixed number of parallel machines , the complexity of the problem is still open, but the problem becomes NP-hard if is arbitrary. In this paper we characterize a new order class that contains properly quasi-interval orders and prove that Coffman-Graham algorithm yields to optimal schedules for this new order class on any number of machines. Finally, some extensions are discussed for a larger order class and for scheduling in presence of unit communication delays.