Karim Tamssaouet

Knowledge-Based Systems 300 p. 1-14 Doi: https://doi.org/10.1016/j.knosys.2024.112149

Learning the structure of Bayesian networks (BNs) from data is an NP-hard problem as the solution space grows super-exponentially with the number of nodes. Many algorithms have been developed to efficiently find the best structures, with score-based algorithms being those that use heuristics or metaheuristics to explore potential structures in the search space. This paper proposes a new score-based algorithm that relies on a well-known metaheuristic called scatter search, which, to the best of our knowledge, has not been used in learning BN structure. The core of scatter search is to maintain a reference set that stores both high-quality and diverse solutions, thereby continuously tracking and improving the high-quality solutions, while exploring different search directions indicated by the diverse solutions. By incorporating a distance metric in the learning process, the exploration can be more systematic than purely random, as is often the case in most existing algorithms. The effectiveness and efficiency of the proposed algorithm are evaluated through computational experiments. In addition to learning higher-score structures, the results show that scatter search provides a higher degree of robustness compared with benchmark algorithms

European Journal of Operational Research Doi: https://doi.org/10.1016/j.ejor.2023.05.017

The flexible job shop scheduling problem (FJSP) is an NP-hard combinatorial optimization problem, which has wide applications in the real world. The complexity and relevance of the FJSP have led to numerous research works on its modeling and resolution. This paper reviews some of the research of the past 30 years on the problem, by presenting and classifying the different criteria, constraints, configurations and solution approaches that have been considered. Recent emerging topics on complex shop scheduling, multi-criteria optimization and uncertain and dynamic environments are discussed. Finally, future research opportunities are proposed.

European Journal of Operational Research 311(2) p. 455-471 Doi: https://doi.org/10.1016/j.ejor.2023.05.018

This article introduces a framework that unifies and generalizes well-known literature results related to local search for the job-shop and flexible job-shop scheduling problems. In addition to the choice of the metaheuristic and the neighborhood structure, the success of most of the influential local search approaches relies on the ability to quickly and efficiently rule out infeasible moves and evaluate the quality of the feasible neighbors. Hence, the proposed framework focuses on the feasibility and quality evaluation of a general move when solving the job-shop and flexible job-shop scheduling problems for any regular objective function. The proposed framework is valid for any scheduling problem where the defined neighborhood structure is appropriate, and each solution to the problem can be modeled with a directed acyclic graph with {non-negative weights on nodes and arcs}. The feasibility conditions and quality estimation procedures proposed in the literature rely heavily on information on the existence of a path between two nodes. Thus, based on an original parameterized algorithm that asserts the existence of a path between two nodes, novel generic procedures to evaluate the feasibility of a move and estimate the value of any regular objective function of a neighbor solution are proposed. We show that many well-known literature results are special cases of our results, which can be applied to a wide range of shop scheduling problems.

International Journal of Production Economics 265 p. 1-15 Doi: https://doi.org/10.1016/j.ijpe.2023.109001

This paper addresses a tactical joint inventory and transportation planning problem for multiple items with deterministic and time-varying demand, considering different transportation modes and item fragmentation. The latter corresponds to the splitting of the same item ordered quantity between several trucks or containers. On the one hand, fragmenting the items potentially reduces the number of containers used. On the other hand, loading the item lot fragments on several containers may negatively impact the handling and shipping operations. This new problem is proposed as a way to tackle such conflict. Several Mixed Integer Linear Programming models are proposed for the problem, which rely on two multi-item lot-sizing models with mode selection and two bin-packing models with item fragmentation. A relax-and-fix heuristic is also proposed. Using realistic instances, computational experiments are first conducted to identify the most efficient model in terms of computational time, to study the impact of key parameters on the computational complexity and to analyze the efficiency of the heuristic. Then, managerial insights are derived through additional computational experiments, in particular, to identify contexts requiring joint optimization of lot-sizing and bin-packing decisions, as well as the impact of item fragmentation constraints. Directions for future research are finally proposed.

European Journal of Operational Research 296(1) p. 87-100 Doi: https://doi.org/10.1016/j.ejor.2021.03.069

In this paper, we are concerned with the resolution of a multiobjective complex job-shop scheduling problem stemming from semiconductor manufacturing. To produce feasible and industrially meaningful schedules, this paper extends the recently proposed batch-oblivious approach by considering unavailability periods and minimum time lags and by simultaneously optimizing multiple criteria that are relevant in the industrial context. A novel criterion on the satisfaction of production targets decided at a higher level is also proposed. Because the solution approach must be embedded in a real-time application, decision makers must express their preferences before the optimization phase. In addition, a preference model is introduced where trade-off is only allowed between some criteria. Two a priori multiobjective extensions of Simulated Annealing are proposed, which differ in how the simultaneous use of a lexicographic order and weights is handled when evaluating the fitness. A known a posteriori approach of the literature is used as a benchmark. All the metaheuristics are embedded in a Greedy Randomized Adaptive Search Procedure. The different versions of the archived GRASP approach are compared using large industrial instances. The numerical results show that the proposed approach provides good solutions regarding the preferences. Finally, the comparison of the optimized schedules with the actual factory schedules shows the significant improvements that our approach can bring.

CityFreight Workshop

Finnish Operations Research Society

International Workshop on Lot Sizing (IWLS 2022)

NORS Annual Conference 2022

Annual NORS Conference 2021,Bergen

In Norway, the government has set 2025 as the end date for the entry of new fossil vehicles. Such an ambitious goal would require upgrading the current infrastructure by providing a sufficient number of charging stations that are appropriately distributed across a road network. Determining appropriate locations and capacities for such charging stations across the country is a challenging multi-objective optimization problem with many constraints. Among the various aspects to be considered when locating charging stations, the requirement that an electric car with medium battery capacity can travel anywhere without being stranded is the most fundamental, especially in a country like Norway with low population density and where the travel distances between population hubs can be large. It is proposed in the literature to compute domination models for a reachability graph derived from the original road network to model the problem of placing as few stations as possible so that on any shortest path, there are sufficiently many not to run out of energy. In this work, we show that the use of a dominating set to model the problem is insufficient to ensure reachability on a nationwide road network. There may be no possibility to reach a location with a charging station starting from another charging station location. The study proposes instead to model the problem with a connected dominating set. Heuristic approaches are proposed and applied to the case of the Norwegian road network using publicly available data. The proposed approach can help policymakers to estimate the minimal number of locations where charging stations should be built to facilitate long-distance travel, which is one of the last hurdles for mass adoption of electric passenger vehicles in Norway.