Stéphane Dauzère-Pérès

Knowledge-Based Systems 300 s. 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 312(3) s. 890-909 Doi: https://doi.org/10.1016/j.ejor.2023.07.036

This paper addresses an extension of the flexible job-shop scheduling problem where transportation resources are explicitly considered when moving jobs from one machine to another. Operations should be assigned to and scheduled on machines and vehicles and the routes of vehicles should be determined. We extend the classical disjunctive graph model to include transportation operations and exploit the graph in an integrated approach to solve the problem. We propose a metaheuristic using a neighborhood function that allows a large set of moves to be explored. As the exact computation of the makespan of every move is time-consuming, we present a move evaluation procedure that runs in constant time (which does not depend on the size of the instance) to choose a promising move in the neighborhood of a solution. This move evaluation procedure is used in a tabu search framework. Computational results show the efficiency of the proposed approach, the quality of the move evaluation procedure and the relevance of explicitly modeling transportation resources. New benchmark instances are also proposed.

Computers & Operations Research 157 Doi: https://doi.org/10.1016/j.cor.2023.106237

This paper considers the flexible job-shop scheduling problem with stochastic processing times. To find a sequence insensitive to shop floor disturbances, the available probabilistic information related to the variability of processing times is taken into account by maximizing the makespan service level for a given deadline. This corresponds to the probability of the makespan to be smaller than a given threshold. After showing why this criterion makes sense compared to minimizing the average makespan, a solution approach relying on a tabu search and a Monte Carlo sampling-based approximation is presented. Then, new instances are generated by extending the deterministic benchmark instances. Extensive computational experiments are conducted to evaluate the relevance of the makespan service level and the performance of the proposed solution method. The drawbacks of a number of reference scenarios, including worst-case and best-case scenarios, in addressing effectively the problem under study are presented. A numerical analysis is also performed to compare the scope of the proposed criterion against the minimization of the expected makespan. The accuracy of the proposed solutions induced by the hyper-parameters of the Monte Carlo approximation is explicitly analyzed.

European Journal of Operational Research 310(3) s. 992-1016 Doi: https://doi.org/10.1016/j.ejor.2023.03.041

This paper studies the problem of determining energy efficient schedules in a flexible job shop. The goal is to minimize the total energy cost, given a time-of-use pricing scheme, while ensuring that the schedule does not violate a maximum makespan. The problem is first formalized as a mixed integer program. Because it is already difficult to solve, the simpler problem with a fixed sequence of operations is then extensively studied. Some properties are derived for the specific problem with a fixed sequence. These properties show that the complexity of the problem depends on the structure of the energy pricing scheme. They are also used to propose two heuristic approaches. Relying on these heuristics, we further develop an iterative tabu search for the general problem. Extensive computational experiments are carried out to evaluate the solution methods and the potential gains on the total energy cost, depending on the flexibility associated to the maximum allowed makespan and on the time-of-use structures.

Production and operations management 32(7) s. 2322-2330 Doi: https://doi.org/10.1111/poms.13977

This paper aims at linking the work presented in Dauzère-Pérès et al. (1998) and more recently in Kasapidis et al. (2021) on the multiresource flexible job-shop scheduling problem with nonlinear routes or equivalently with arbitrary precedence graphs. In particular, we present a mixed integer linear programming (MIP) model and a constraint programming (CP) model to formulate the problem. We also compare the theorems introduced in Dauzère-Pérès et al. (1998) and Kasapidis et al. (2021) and propose a new theorem extension. Computational experiments were conducted to assess the efficiency and effectiveness of all propositions. Lastly, the proposed MIP and CP models are tested on benchmark problems of the literature and comparisons are made with state-of-the-art algorithms.

International Journal of Production Economics 265 s. 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.

Computers & Operations Research 155 Doi: https://doi.org/10.1016/j.cor.2023.106245

In wafer fabrication, production quality is a key performance index and is subject to machine condition deterioration. This paper studies a parallel-machine scheduling problem that can typically be found in the photolithography process. To solve the problem, a lexicographic optimization approach is proposed where the total quality loss is firstly minimized and the second objective is to minimize total tardiness. An optional maintenance activity is also considered to restore the machine condition to a certain level. Optimality properties are discussed, based on which an exact scheduling algorithm is developed. Experimental analyses derived from real data demonstrate the effectiveness of the proposed algorithm and support some managerial insights.

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.

International Journal of Production Research s. 8291-8308 Doi: https://doi.org/10.1080/00207543.2023.2168083

Motivated by a practical problem, this paper investigates the integrated planning of maintenanceoperations and workload allocation on a set of machines in a workshop. Given quantities of productsto be produced per period on a planning horizon must be processed on unrelated flexible machines.Moreover, each machine has to undergo one or more maintenance operations that must be plannedwithin a given time window and impact products differently. The main goal is to find a feasible planthat satisfies the machine capacity by allocating the production quantities to machines and assign-ing maintenance operations as late as possible in their time windows. Various original mathematicalmodels are presented. In particular, we propose models that allow maintenance operations andsome production quantities to overlap two consecutive periods. Computational experiments basedon industrial data show that allowing this overlapping helps the earliness of maintenance opera-tions to be significantly reduced in the most difficult instances, going for example from a total of 14periods to only 1 period, and by more than 35% on average.

European Journal of Operational Research 311(2) s. 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.

4OR Doi: https://doi.org/10.1007/s10288-022-00508-2

This paper outlines a mathematical model to solve a scheduling problem for a company engineering and producing propellers to order. Nonås and Olsen (Comput Oper Res 32(9):2351–2382, 2005) have previously introduced a Mixed Integer Programming model for this production setting with the objective of minimizing the total tardiness. The mathematical model could however not be used to solve realistic sized problem instances, because of the very large solution time. We propose a new time indexed formulation that can solve most industrial problem instances in less than 10 min. This work is further extended by taking into account limited storage capacity and by proposing different methods to balance between total tardiness and maximum tardiness. We illustrate how the solution time and the criteria change for different setups of the mathematical model and suggest which setup to use for different scenarios. The paper also discusses how the new model can be extended to include unexpected events such as emergency orders and unavailable production equipment.

European Journal of Operational Research 302(1) s. 203-220 Doi: https://doi.org/10.1016/j.ejor.2021.12.017

This paper first analyzes the negative impact of the end-of-horizon effect when solving the capacitated multi-item lot-sizing problem with setup costs and times on a rolling horizon. Maximum ending inventories for items and a global minimum ending inventory are considered to define a new optimization problem whose optimal solutions are much less impacted by the end-of-horizon effect. Then, a generation scheme is proposed to create new instances with initial inventories and ending inventories. This scheme relies on the analysis of the cyclical production planning problem to derive relevant parameters. Computational experiments are carried out to compare the solutions obtained for original instances of the literature and for the new instances, and to analyze the relevance of the new instances on a rolling horizon.

Computers & Operations Research 151 Doi: https://doi.org/10.1016/j.cor.2022.106092

This paper is motivated by the development of Industry 4.0 and the need to better integrate production and maintenance decisions. Our problem considers a single machine on which jobs of different families are scheduled to minimize the sum of completion times. The machine has a health index which decreases when jobs are processed. To restore the machine health, maintenance operations must be scheduled. Moreover, to be scheduled, each job requires the machine to have a minimum health index which depends on the job family. Two cases are studied: (1) The daily case with a single flexible maintenance operation, and (2) The weekly case with two flexible maintenance operations. The second case is shown to be NP-complete. Two Mixed Integer Linear Programming models are presented for each case. The first model uses ‘‘classical’’ positional variables, while the second model improves the first model by using the notion of master sequence. Different valid inequalities are also proposed. Computational experiments show that the second model is much more efficient than the first model when solved with a standard solver, and the impact of the valid inequalities is discussed.

International Journal of Production Research 61(17) Doi: https://doi.org/10.1080/00207543.2022.2118387

In this paper, a practical relevant operational production planning problem in complex manufacturing systems is addressed. In this problem, lots are planned individually to provide a more detailed plan than approaches that only consider production quantities. A three-step approach, which is currently fully integrated and used in a Decision Support System, is then introduced. This work follows the one of Mhiri et al. [2018. “Heuristic Algorithm for a WIP Projection Problem at Finite Capacity in Semiconductor Manufacturing.” IEEE Transactions on Semiconductor Manufacturing 31 (1): 62–75] who addressed this problem. We push the approach a step further by introducing new optimisation possibilities through new smoothing rules, whose performance is studied according to different indicators. Furthermore, we present the production planning process in which the decision support tool is embedded and how it bridges the gap between the upper and lower planning levels.

Omega. The International Journal of Management Science 106 Doi: https://doi.org/10.1016/j.omega.2021.102537

In some flexible manufacturing systems, such as semiconductor manufacturing systems, machines must be qualified, i.e. certified and eligible, to process a product. This paper investigates a tactical capacity planning problem that consists in minimizing the number of (product, machine) qualifications to ensure that the manufacturing system is robust against the uncertainty on the product mix. First, we propose a deterministic modeling of the problem, followed by a robust modeling based on the robust optimization paradigm when demand uncertainty is characterized by product cannibalization. Then, a mathematical model, also based on the robust optimization paradigm, to characterize the robustness of a set of qualifications is introduced. Finally, in the computational study on industrial data, we show that the price of uncertainty is small, often less than a few additional qualifications by machine whereas the robustness of the qualifications determined for the nominal product mix often lead to capacity constraint violations. We also show that a restricted number of new relevant qualifications out of all possible new qualifications is required to achieve the same robustness as the case where all new qualifications are performed. Considering demand uncertainty in qualification management is therefore critical since robustness is relatively cheap.

International Journal of Production Research Doi: https://doi.org/10.1080/00207543.2022.2145516

The complexity of decision-making for companies buying transportation services has increased due to the presence of more options and pricing schedules for transportation. Many companies make transportation and inventory decisions in an uncoordinated way and select only one transportation mode, missing opportunities for logistics cost savings. The experimental study in this paper is based on a real-world decision problem faced by a Scandinavian company that distributes fast-moving consumer goods and wants to determine its transportation strategy. We propose a novel multi-mode lot-sizing model with dynamic deterministic demand to illustrate the cost impact of accurately modelling piecewise-linear transportation costs and allowing a more flexible usage of transportation modes when planning order replenishments. We compare three transportation strategies with increasing degrees of flexibility: two single mode strategies, where one strategy is more flexible than the other, and a multi-mode strategy. We conclude that managers can significantly reduce costs by increasing the flexibility of mode selection in transportation strategies.

Computers & Operations Research 144 Doi: https://doi.org/10.1016/j.cor.2022.105813

In some manufacturing contexts, such as semiconductor manufacturing, machines must be qualified, or eligible, to process a product, and machines cannot be qualified for all products. This paper investigates the problem of optimizing a given number of new qualifications of products to machines to maximize a flexibility measure that evaluates the balance of the qualification configuration of a work center in terms of utilization rate of machines on a set of non-identical parallel machines. Motivated by empirical observations, new solution approaches, notably inspired by heuristics for discrete location problems and based on the analysis of dual variables, are proposed and compared on industrial data from a semiconductor manufacturing facility and on randomly instances. The use of dual variables leads to heuristics that are effective both in terms of solution quality and computational time. The best proposed approach is currently used in the decision support system of a semiconductor manufacturing facility.

IEEE Transactions on Evolutionary Computation 27(5) s. 1470-1484 Doi: https://doi.org/10.1109/TEVC.2022.3222791

Improving productivity at the expense of heavy energy consumption is often no longer possible in modern manufacturing industries. Through efficient scheduling technologies, however, we are able to still maintain high productivity while reducing energy costs. This paper addresses a flexible job shop scheduling problem under Time-Of-Use electricity tariffs with the objective of minimizing total energy consumption while considering a predefined makespan constraint. We propose a novel two-individual-based evolutionary (TIE) algorithm, which incorporates several distinguishing features such as a tabu search procedure, a topological order based recombination operator, a new neighborhood structure for this specific problem, and an approximate neighborhood evaluation method. Extensive experiments are conducted on widely used benchmark instances, which show that the proposed TIE outperforms traditional trajectory-based and population-based methods. We also analyze the key features of TIE to identify its critical success factors, and discuss the impact of varying key parameters of the problem to derive practical insights.

European Journal of Operational Research 302(1) s. 221-229 Doi: https://doi.org/10.1016/j.ejor.2021.12.027

In this paper, a novel way of modeling uncertainty on demand in the single-item dynamic lot sizing problem is proposed and studied. The uncertainty is not related to the demand quantity, but rather to the demand timing, i.e., the demand fully occurs in a single period of a given time interval with a given probability and no partial delivery is allowed. The problem is first motivated and modeled. Our modeling naturally correlates uncertain demands in different periods contrary to most of the literature in lot sizing. Dynamic programs are then proposed for the general case of multiple demands with stochastic demand timing and for several special cases. We also show that the most general case where the backlog cost depends both on the time period and the stochastic demand is NP-hard.

International Journal of Production Research 61(2) Doi: https://doi.org/10.1080/00207543.2021.2010828

This paper proposes a novel global scheduling approach for cycle time control strategy in large complex manufacturing systems with multiple workcentres, such as semiconductor manufacturing systems. The interaction between workcentres is taken into account by using global information such as release quantities, the Work-In-Process (WIP), cycle time targets and machine capacities. Local scheduling decisions in workcentres are steered by production targets, i.e. quantities of products to complete in each operation and each period on a scheduling horizon. These global production targets are determined by a mathematical model (global scheduling model), which optimises the satisfaction of cycle time targets. One of the major innovations of the proposed model is that it relies on the temporal trace of the WIP. The mathematical model is coupled with a generic multi-method simulation model for evaluation purpose. Computational experiments conducted on industrial data show that our global scheduling approach efficiently controls the cycle times of products.

International Journal of Production Research 60(19) Doi: https://doi.org/10.1080/00207543.2021.1969048

Motivated by real challenges on energy management faced by industrial firms, we propose a novel way to reduce production costs by including the pricing of electricity in a multi product lot-sizing problem. In incentive-based programs, when electric utilities face power consumption peaks, they request electricity-consuming firms to curtail their electric load, rewarding the industrial firms with incentives if they comply with the curtailment requests. Otherwise, industrial firms must pay financial penalties for an excessive electricity consumption. A two-stage stochasticformulation is presented to cover the case where a manufacturer wants to satisfy any curtailment request. A chance-constrained formulation is also proposed, and its relevance in practice is discussed. Finally, computational studies are conducted to compare mathematical models and highlight critical parameters and show potential savings when subscribing incentive-based programs. We show that the setup cost ratio, the capacity utilisation rate, the number of products and the timing of curtailment requests are critical parameters for manufacturers.

European Journal of Operational Research 300(2) Doi: https://doi.org/10.1016/j.ejor.2021.08.011

In complex systems that can be found in semiconductor manufacturing, linear programming production planning models must consider many products with hundreds of production steps to be performed on hundreds of machines. To deal with this complexity and solve problems with flexible lead times in a reasonable CPU time, the new concept of timed route is introduced. In a timed route, each production step of a product is associated with a specific time period. A new formulation relying on timed routes is then proposed. Because the number of feasible timed routes can grow exponentially, a column generation approach is presented. Algorithms to generate relevant timed routes are given, and their complexity analyzed. Computational experiments on industrial data with different lead time profiles, fixed lead times and flexible lead times, show that computational times are very significantly reduced when using our approaches, by 92% on average and even divided by more than 1,000 in some cases. The advantages of timed routes are also discussed.

Computers & Operations Research 132 Doi: https://doi.org/10.1016/j.cor.2021.105291

In this paper, a scheduling problem on non-identical parallel machines with auxiliary resources and sequence-dependent and machine-dependent setup times is studied. This problem can be found in various manufacturing contexts, and in particular in workshops of wafer manufacturing facilities. Three different criteria are defined and analyzed: The number of products completed before the end of a given time horizon, the weighted sum of completion times and the number of auxiliary resource moves. The first criterion is maximized, while the two others are minimized. The first and the third criteria are not classical in scheduling theory, but are justified in industrial settings. The complexity of the problem with each of the new criteria is characterized. Integer linear programming models are also proposed and numerical experiments are conducted to analyze their behavior.

International Journal of Production Research 60(10) Doi: https://doi.org/10.1080/00207543.2021.1910746

In modern production systems, considering machine conditions is becoming essential to achieving an overall optimisation of the production schedule. This paper studies a single machine scheduling problem, where the actual processing times of jobs depend on their position in the production sequence and maintenance is considered. Moreover, the machine is subject to an uncertain condition variation. There is a trade-off between rejecting a maintenance action, resulting in longer processing times, and accepting a maintenance action, leading to higher processing efficiency for future jobs. The problem is formulated as a finite-horizon Markov Decision Process. The objective is to minimise the makespan. Optimality properties are analysed, based on which a dynamic optimisation approach is developed. Computational experiments demonstrate the effectiveness of the proposed approach.

European Journal of Operational Research 296(1) s. 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.

International Journal of Production Research 58(9) s. 2822-2840 Doi: https://doi.org/10.1080/00207543.2020.1727041

This research combines deep neural network (DNN) and Markov decision processes (MDP) for the dynamic dispatching of re-entrant production systems. In re-entrant production systems, jobs enter the same workstation multiple times and dynamic dispatching oftentimes aims to dynamically assign different priorities to various job groups to minimise weighted cycle time or maximise throughput. MDP is an effective tool for dynamic production control, but it suffers from two major challenges in dynamic control problems. First, the curse of dimensionality limits the computational performance of solving large MDP problems. Second, a different model should be built and solved after system configuration is changed. DNN is used to overcome both challenges by learning directly from optimal dispatching policies generated by MDP. Results suggest that a properly trained DNN model can instantly generate near-optimal dynamic control policies for large problems. The quality of the DNN solution is compared with the optimal dynamic control policies through the standard K-fold cross-validation test and discrete event simulation. On average, the performance of the DNN policy is within 2% of optimal in both tests. The proposed artificial intelligence algorithm illustrates the potential of machine learning methods in manufacturing applications.

International Journal of Production Research s. 1-25 Doi: https://doi.org/10.1080/00207543.2020.1711984

For the sake of product yield and quality considerations, Time Constraints (TCs) are imposed between process operations in various multi-product manufacturing systems. Often spanning a number of operations, time constraints tend to follow each other in close succession and overlap, forming thus Time Constraint Tunnels (TCTs). The regulation problem of releasing lots in these time constraint tunnels is particularly challenging in semiconductor manufacturing systems, because of re-entrant flows, machine heterogeneity and High Mix Low Volume (HM-LV) production configurations, which are typical in many wafer fabrication facilities. In such an evolving and time-varying context, this paper proposes a sequential sampling-based approach to estimate the probability that, prior to its release, a lot leaves a given time constraint tunnel on time. The proposed approach proves to be competitive in various respects by: (i) taking into account industry specific features, (ii) being industrially tractable, and (iii) being sensitive and responsive to the current manufacturing system. Based on real-life instances, numerical experiments highlight the computational effectiveness and the industrial soundness of the proposed problem modeling together with the solution approach.

Winter simulation conference : proceedings Doi: https://doi.org/10.1109/WSC48552.2020.9384001

Computers & Operations Research 115 s. 1-21 Doi: https://doi.org/10.1016/j.cor.2019.104838

Production planning optimization remains a major challenge in almost all industries, particularly in high-tech manufacturing. A critical task to support such optimization is performance evaluation, wherein an accurate estimation of the cycle time as a function of the throughput rate plays a key role. This paper develops a novel aggregation model based on a queueing network approach, so-called queue-based aggregation (QAG) model, to estimate the cycle time of a job-shop production system that consists of several processing workstations, and in which products are transferred via an Automated Material Handling System (AMHS). The proposed model aggregates both production and automated material handling systems and provides an accurate and fast estimation of the overall cycle time. The performance and superiority of the proposed model is validated by comparing its results with those of a detailed simulation model. Numerous sensitivity analyses are performed to provide valuable managerial insights on both the production and automated material handling systems.

European Journal of Operational Research 286(2) s. 662-672 Doi: https://doi.org/10.1016/j.ejor.2020.03.034

Rescheduling trains in dense railway systems to cope in real time with limited disturbances is a challenging problem with multiple conflicting objectives and various types of decisions. Based on the French railway system in the Paris region, this paper proposes an approach combining multi-objective optimization, to select rescheduling decisions, and macroscopic simulation, to compute the objectives associated to these decisions. Possible decisions include canceling or short-turning trains and skipping or adding stops. Three main objectives are optimized to propose multiple solutions to the decision makers: The recovery time, the quality of service for passengers and the number of decisions. Two greedy heuristics are presented whose results on actual data are compared with a full enumeration method. The multi- objective feature of the approach is also analyzed. The implementation and successful validation in real life of a decision-support tool, that is now implemented, is discussed.

International Journal of Production Research 58(9) s. 2730-2731 Doi: https://doi.org/10.1080/00207543.2020.1752488

European Journal of Operational Research 282(1) s. 267-276 Doi: https://doi.org/10.1016/j.ejor.2019.09.014

In-line quality control is a crucial and increasingly constraining activity, in particular in high technology manufacturing. In this paper, we study a single metrology tool assigned to control the production quality of multiple heterogeneous machines. We introduce, model and study the tradeoffbetween the quality loss resulting from the sampling policy, and the quality loss induced by delays in the metrology queue. An iterative approach is proposed to optimize sampling periods using the solution of a relaxed problem which assumes full synchronization between production and metrology, and which has been previously formalized and solved. Based on computational and simulation results, and a prediction model, the paper ends with recommendations to better manage metrology capacity utilization under various levels of variability.

European Journal of Operational Research 279(2) s. 419-428 Doi: https://doi.org/10.1016/j.ejor.2019.06.007

This paper presents an original approach for a practical workload balancing problem on non-identical parallel machines in manufacturing systems. After showing the limitations of an initial model, in particular to support relevant decisions, the min–max fairness workload balancing problem is motivated and positioned in the literature. The Iterated Min–Max (IMM) procedure is then presented, with its properties, and illustrated. The IMM consists in solving a succession of linear programs using information from dual variables obtained at each iteration. Computational results on industrial instances show the relevance of the approach when compared to the initial model. The current use of the IMM procedure in an industrial tool is discussed.

Computers & Operations Research 108 s. 187-200 Doi: https://doi.org/10.1016/j.cor.2019.04.012

In this paper, a general local search approach for the Multi-Objective Flexible Job-shop Scheduling Problem (MOFJSP) is proposed to determine a Pareto front for any combination of regular criteria. The approach is based on a disjunctive graph, a fast estimation function to evaluate moves and a hierarchical test to efficiently control the set of non-dominated solutions. Four search strategies using two neighborhood structures are developed. Numerical experiments are conducted on test instances of the literature with three sets of criteria to minimize and using metrics to evaluate and compare Pareto fronts. The results show that our approach provides sets of non-dominated solutions of good quality.

Computers & Operations Research 113 Doi: https://doi.org/10.1016/j.cor.2019.104779

A dynamic decision model that coordinates dispatching and preventive maintenance decisions for failure- prone parallel machines in make-to-order (MTO) production environments is developed in this research. The primary objective is to minimize the weighted long-run average waiting costs of MTO systems. Two common but seldom studied stochastic factors, namely, the dispatching-dependent deterioration of ma- chines and machine-health-dependent production rates, are explicitly modeled in the proposed dynamic dispatching and preventive maintenance (DDPM) model. Although the DDPM model is developed using Markov decision processes, it is equally effective in non-Markovian production environments. The per- formance of the DDPM model is validated in Markovian and non-Markovian production environments. Compared with several methods from the literature, simulation results show an improvement of at least 45.2% in average job waiting times and a minimum reduction of 48.9% in average machine downtimes. The comparison results between the optimal dynamic dispatching policies with and without coordinated preventive maintenance show that performance improvement can be mostly attributed to the coordina- tion between preventive maintenance and dispatching decisions.

International Journal of Production Research 58(4) s. 1222-1238 Doi: https://doi.org/10.1080/00207543.2019.1614693

Motivated by the high investment and operational metrology cost, and subsequently the limited metrology capacity, in modern semiconductor manufacturing facilities, we model and solve the problem of optimally assigning the capacity of several imperfect metrology tools to minimise the risk in terms of expected product loss on heterogeneous production machines. In this paper, metrology tools can differ in terms of reliability and speed. The resulting problem can be reduced to a variant of the Generalized Assignment Problem (GAP), the Multiple Choice, Multiple Knapsack Problem (MCMKP). A Lagrangian heuristic, including multiple feasibility heuristics, is proposed to solve the problem that are tested on randomly generated instances.

Computers & Operations Research 107 s. 61-76 Doi: https://doi.org/10.1016/j.cor.2019.03.004

This paper studies the scheduling of jobs of different families on parallel machines, where not all machines are qualified (eligible) to process all job families. Originating from semiconductor manufacturing, an important constraint imposes that the time between the processing of two consecutive jobs of the same family on a machine does not exceed a given time limit. Otherwise, the machine becomes disqualified for this family. The goal is to minimize both the flow time and the number of disqualifications of job families on machines. To solve this problem, an integer linear programming model and a constraint programming model are proposed, as well as two improvement procedures of existing heuristics: A Recursive Heuristic and a Simulated Annealing algorithm. Numerical experiments on randomly generated instances compare the performances of each method.

Computers in industry (Print) 110 s. 3-11 Doi: https://doi.org/10.1016/j.compind.2019.04.014

Semiconductor wafer fabrication probably includes the most complex and constrained manufacturing processes due to its intricate and time-varying environment. This paper focuses on time constraint tunnels (TCTs), which can have a very high impact on the yield and reliability of final products. More precisely, the original problem faced by managers of controlling the release of multiple lots in a TCT is addressed in the context of a wafer facility operating in a High-Mix Medium-Volume manufacturing environment. To support the management of TCTs in an industrially acceptable context, a scheduling based sampling method is proposed to estimate the probability that multiple lots released at the entrance of a given TCT leave this TCT on time. In order to investigate the industrial viability and identify the limitations of the probability-estimation approach, numerical experiments are conducted on real-life data and analyzed through the prism of several relevant performance criteria. Insights gathered from this numerical analysis are then used to discuss the specific management requirements that stem from the criticality of TCTs in semiconductor manufacturing facilities.

International Journal of Production Research 56(13) s. 4521-4523 Doi: https://doi.org/10.1080/00207543.2018.1464680

Computers & industrial engineering 120(June) s. 450-459 Doi: https://doi.org/10.1016/j.cie.2018.04.053

Monitoring the Equipment Health Indicator (EHI) of critical machines helps effectively to maintain process quality and reduce wafer scrap, rework, and machine breakdowns. To model and illustrate the integration of EHI in scheduling decisions to balance between productivity and quality risk, this paper presents two mixed integer linear programs to schedule jobs on heterogeneous parallel batching machines. The capability of a machine to process a job is categorized as preferred, acceptable, and unfavorable based on the job requirements. The quality risk of processing a job by a machine is a function of its EHI and the capability level of the machine for the job, which is modeled as a penalty in the objective function of trading-off between productivity and quality risk. The first model is static and assumes constant EHI of machines on the scheduling horizon, whereas the second model considers the EHI dynamics, i.e., the machine condition deteriorates over time based on the scheduled jobs. Numerical experiments indicate the potential applications of using EHI-integrated scheduling approaches to analyze and optimize the trade-off between productivity and quality risk.

Computers & Operations Research 96(August) s. 108-119 Doi: https://doi.org/10.1016/j.cor.2018.04.010

In this paper, we consider the integration of production, inventory and distribution decisions in a sup- ply chain composed of one production facility supplying several retailers located in the same region. The supplier is far from the retailers compared to the distance between retailers. Thus, the traveling cost of each vehicle from the supplier to the region is assumed to be fixed and there is a fixed delivery (service) cost for each visited retailer. The objective is to minimize the sum of the costs at the production facility and at the retailers. The problem is more general than the One-Warehouse Multi-Retailer problem and is a special case of the Production Routing Problem. Five heuristics based on a Genetic Algorithm are proposed to solve the problem. In particular, three of them include the resolution of a Mixed Integer Pro- gram as subproblem to generate new individuals in the population. The results show that the heuristics can find optimal solutions for small and medium size instances. On large instances, the gaps obtained by the heuristics in less than 300 s are better than the ones obtained by a standard solver in two hours.

European Journal of Operational Research 265(2) s. 503-516 Doi: https://doi.org/10.1016/j.ejor.2017.08.021

This paper addresses the flexible job shop scheduling problem with sequence-dependent setup times and where the objective is to minimize the makespan. We first present a mathematical model which can solve small instances to optimality, and also serves as a problem representation. After studying structural properties of the problem using a disjunctive graph model, we develop a tabu search algorithm with specific neighborhood functions and a diversification structure. Extensive experiments are conducted on benchmark instances. Test results first show that our algorithm outperforms most existing approaches for the classical flexible job shop scheduling problem. Additional experiments also confirm the significant improvement achieved by integrating the propositions introduced in this study.

European Journal of Operational Research 269(2) s. 633-646 Doi: https://doi.org/10.1016/j.ejor.2018.01.052

We consider the Production Routing Problem where production planning, inventory management and distribution planning decisions must be taken. We compare two sequential approaches, one in which production decisions are optimized first and one in which distribution decisions are optimized first, with an integrated approach where all decisions are simultaneously optimized. Some properties of the solutions obtained with the different approaches are shown. Computational experiments are performed on instances of different size which are generated using two critical parameters. The numerical results illustrate the properties and show that the benefits of the integrated approach over the two sequential ones depend on the trade-off between production and distribution costs and on the trade-off between setup and inventory costs in production.

Winter simulation conference : proceedings

Computers & industrial engineering Doi: https://doi.org/10.1016/j.cie.2018.08.008

Computers & industrial engineering 125 s. 1-8 Doi: https://doi.org/10.1016/j.cie.2018.08.008

This paper addresses the job-shop scheduling problem in which the machines are not available during the whole planning horizon and with the objective of minimizing the makespan. The disjunctive graph model is used to represent job sequences and to adapt and extend known structural properties of the classical job-shop scheduling problem to the problem at hand. These results have been included in two metaheuristics (Simulated Annealing and Tabu Search) with specific neighborhood functions and diversification structures. Computational experiments on problem instances of the literature show that our Tabu Search approach outperforms Simulated Annealing and existing approaches.

European Journal of Operational Research 279 s. 1-25 Doi: https://doi.org/10.1016/j.ejor.2018.11.067

Despite the significant share of transportation costs in logistics costs and the importance of considering transportation in inventory models, the majority of the existing models either neglect or simplify transportation costs and capacities, often assuming that only one transportation option is available. The complexity of modeling and choosing the optimal transportation mode or combination of modes has increased due to the increased variety of transportation options and pricing schedules after deregulation. In this paper, we review and classify inventory models with multiple transportation modes focusing on the freight cost functions, mode characteristics and the methods for modeling multiple modes. To our knowledge, no such review has previously been published. We discuss the benefits and weaknesses of each modeling method and, based on industrial practices, identify new areas for research.

International Journal of Production Research 57(5) s. 1497-1523 Doi: https://doi.org/10.1080/00207543.2018.1492163

Performance evaluation, and in particular cycle time estimation, is critical to optimise production plans in high-tech manufacturing industries. This paper develops a new aggregation model based on queuing network, so-called queue-based aggregation (QAG) model, to estimate the cycle time in a production system. Multiple workstations in serial and job-shop configurations are aggregated into a single-step workstation. The parameters of the aggregated workstation are approximated based on the parameters of the original workstations. Numerical experiments indicate that the proposed QAG model is computationally efficient and yields fairly accurate results when compared to other aggregation approaches in the literature.

International Journal of Production Economics 198 s. 25-37 Doi: https://doi.org/10.1016/j.ijpe.2018.01.014

In this paper, we investigate a multi-item production planning problem in which remanufacturable raw materials are used for manufacturing the final products. The used raw material (considered as a kind of by-product) needs to be remanufactured before being suitable to be used again to manufacture other final products. However, byproducts can be remanufactured only a given number of times. The manufacturing and remanufacturing processes are performed in separated production processes with limited capacity. Each product may be produced using specific raw material references (newly purchased and/or remanufactured). The original industrial case study is based on the supply chain of Silicon-On-Insulator fabrication units. The problem is modeled as a mixed integer linear mathematical program. Using numerical examples based on industrial data, the model is validated and its behavior is analyzed. Finally, some industrial and academic perspectives to this study are proposed.

European Journal of Operational Research 263(1) s. 50-61 Doi: https://doi.org/10.1016/j.ejor.2017.04.050

We consider a Flexible Job-Shop scheduling problem with batching machines, reentrant flows, sequence dependent setup times and release dates while considering different regular objective functions. Semicon- ductor manufacturing is probably one of the most prominent practical applications of such a problem. Existing disjunctive graph approaches for this combined problem rely on dedicated nodes to explicitly represent batches. To facilitate modifications of the graph, our new modeling reduces this complexity by encoding batching decisions into edge weights. An important contribution is an original algorithm that takes batching decisions “on the fly”during graph traversals. This algorithm is complemented by an inte- grated move to resequence and reassign operations. This combination yields a rich neighborhood that we apply within a local search and a Simulated Annealing (SA) metaheuristic. The latter is embedded in a Greedy Randomized Adaptive Search Procedure (GRASP) which is the most efficient approach. Numerical results for benchmark instances of different problem types show the generality and applicability of our approach. The conciseness of our idea facilitates extensions towards further complex constraints needed in real-world applications.

Transportation Research Part C: Emerging Technologies 79 s. 73-84 Doi: https://doi.org/10.1016/j.trc.2017.03.012

European Journal of Operational Research 263(3) s. 838-863 Doi: https://doi.org/10.1016/j.ejor.2017.05.008

Following our previous paper (Brahimi, Dauzère-Pérès, Najid, & Nordli, 2006), we present an updated and extended survey of Single-Item Lot-Sizing Problems with focus on publications from 2004 to 2016. Exact and heuristic solution procedures are surveyed. A concise and comprehensive summary of different extensions of the problem is given. The classification of the extensions is based on different characteristics such as resource limitations, assumptions on demand and cost structure. The large number of surveyed papers shows the increased interest of researchers in lot-sizing problems in general and in single-item problems in particular. The survey and the proposed classification should help researchers to identify new research topics, to propose relevant problems and/or novel solution approaches.

International Journal of Production Research 54(20) s. 6082-6091 Doi: https://doi.org/10.1080/00207543.2016.1187775