Search

Part II - Hybrid Approaches for Production Planning and Scheduling; International audience; This study tackles an unrelated parallel machines rescheduling problem. Sequence and machine dependent setup times and limited resources are taken into consideration. The study focuses on the objective of proposing an efficient and stable rescheduling solution. The resolution approach is explained and illustrated. Different indicators to optimize the rescheduling planning are tested and results are analyzed. The problem is inspired from a concrete case of textile industry.

International audience; In this paper, the capacitated lot-sizing and scheduling problem with sequence-dependent setups and backlogging with energy consideration is studied. A new mixed-integer programming model is proposed. The planning horizon is split into T periods where each one is characterized by a duration, an allowed maximal power, a price of electricity and power and demands of products. The objective is to find a production scheduling that minimizes the total production cost. As this problem is known to be NP-hard, a Fix-and-Relax heuristic is developed. Computational experiments demonstrate that this method provides good quality results.

International audience; While many children walk or cycle to and from school, buses and minibuses are major modes of travel for children. A typical journey of these pupils involves walking to and from the bus stop, waiting at bus stops, and boarding. The school bus routing problem, which consists of a set of students spread in a region who must be brought to and from their schools every school day, is considered in this paper. This paper describes the application of an efficient optimization software, Opta Scholar, to solve the school bus routing and scheduling problem. The application of this software showed major improvements in terms of the number of buses used and travelling costs. Furthermore, the embedded algorithm outperforms existing benchmark results on relaxed forms of the problem.

International audience; This paper presents a problem from the textile industry wich consists of designing the layout of a knitting workshop. Machine groups are created to balance the operators’ workload and the layout is designed to create group cells. New models are proposed in this paper with two approaches. The first is an aggregated model and the second one proposes a two-step sequential method. The two models were implemented using CPLEX-ILOG software and compared to provide preliminary results. Future directions for research are outlined to further address this issue.

International audience; In this paper, a single-item capacitated lot-sizing problem in a flow-shop system with energy consideration is addressed. The planning horizon is split into T periods where each one is characterized by a duration, an electricity cost, a maximum peak power and a demand. This problem is NP-hard, since its simple version is known to be NP-hard. Therefore, to deal with the complexity and to find good quality solutions in a reasonable time, a fix-and-relax heuristic and a genetic algorithm are developed. Computational experiments are performed on different instances to show the efficiency of these proposed heuristics. To evaluate their performances, problems of different scales have been studied and analyzed.

International audience; In this paper, a single-item capacitated lot-sizing problem in a flow-shop system with energy consideration is studied. The planning horizon is defined by a set of periods where each one is characterised by a length, an allowed maximal power, an electricity price, a power price and a demand. The objective is to determine the quantities to be produced by each machine at each period while minimising the production cost in terms of electrical, inventory, set-up and power required costs. For medium- and large-scale problems, lot-sizing problems are hard to solve. Therefore, in this study, two heuristics are developed to solve this problem in a reasonable time. To evaluate the performances of these heuristics, computational experiments are presented and numerical results are discussed and analysed.

International audience; The coordination of the electrical vehicles (EV) charging becomes an important research subject in the actual context with the growth of the EV usage. This is due to the harmful impacts of the grid and the overspending price of uncoordinated charging procedure. This work tries to provide a framework to configure and formulate the EV charging problem by the theoretical research on scheduling problem with an additional resource. Given the numerous works in the both domains, this would be advantageous to address such a general algorithm framework. This chapter also introduces our configurations, named ACPF/ACPV, to formulate and solve an actual EV charging problem for residential parking—our case study. The purpose of this case study is to illustrate how the framework would be implemented for real-life cases.

International audience; In this paper, we consider an identical parallel machine scheduling problem with a single additional resource. The processing rate of a job is defined by a linear resource consumption function. The addressed problem takes into consideration two new constraints. The first is the time-varying total available resource. The second new constraint limits the resource consumption incrementation of each job on two consecutive periods of time. Moreover, jobs have bounded resource consumption, arrival times and deadlines. Many practical applications, such as the electrical charging scheduling, can find interests in our works. Our contributions are two-folds. First, we introduce a Mixed-Integer-Linear-Program (MILP) to formulate the problem. Then, we present a heuristic consisting of two phases: a feasible solution construction phase using geometrical strip packing and a solution improvement phase. The heuristic is proven to be very efficiency for dealing with the problem throughout the numerical experiments.

International audience; This paper addresses the cumulative scheduling problem with time-dependent total resource availability. In this problem, tasks are completed by accumulating enough amounts of resources. Our model is time-indexed due to the variation of the total resource availability. A Large neighborhood search (LNS) approach is developed. As an extension of our previous work, this paper contributes a new request removal method and an integration of a simulated annealing procedure to the LNS. Through the computational results, those modifications reduce the derived gap between the worst solutions and also the average derived gap.

International audience; Uncertainties are among the biggest challenges to the electric vehicles (EV) charging scheduling problem. In this paper, we propose a predictive-reactive scheduling method to deal with those disturbances. This study is limited to the charging management of the dedicated residential zone parking. Hence the set of charging tasks is finite (static) and the random distributions of the arrival times and the daily charging demands are known. We propose a reactive partial reschedule strategy to tackle the online scheduling problem. The experimentation is set up to measure the performance of the method in two aspects: the objective value minimisation and the stability. Data used to conduct tests are collected throughout our industrial project. The reactive rescheduling method is implementable in standalone schedulers. Also, it is proved to be very efficient to solve the proposed problem.

International audience; Several researches have been investigated on Multi-Objective Redundancy Allocation Problems (MORAPs), but none of them have considered the redundant dependency at the design stage. This latter which is a special kind of failure dependency can affect significantly the system performance. Due to this fact, this paper deals with the multi-objective system design optimisation with dependent components by focusing on two objectives: maximisation of system availability and minimisation of system cost with components choice and weight constraints. A system consisting of many k-out-of-n repairable subsystems connected in series is considered. The components of a subsystem are supposed to be identical and may be dependent. They are selected from a set of available component types. In addition to the redundancy level and the number of repair teams allocated to each subsystem, the choice of components type and the dependency level are also considered as decision variables. Since the described problem is NP hard, we propose three multi-objective meta-heuristic algorithms based on Non-dominated Sorting Genetic Algorithm (NSGA II) and Strength Pareto Evolutionary Algorithm (SPEA II) with different constraints handling. An exact method is also applied. To analyse their performances, numerical applications are provided and comparisons based on different well-known metrics are presented.

International audience; System availability optimization is one of the most challenging problems for modern complex systems. Basically, availability can be enhanced by increasing redundant components and the set of available maintenance teams which may lead to a dramatic increase in the overall system cost. In this context, this paper proposes an efficient optimization approach to get the best system design of series k - out - of - n : G system achieving the maximal possible steady system availability. A maximum system cost constraint should not be exceeded. The system cost is assumed composed of components purchase cost and repair cost. Moreover, since dependency is essential for reliability optimization problems, the redundant dependency which is a specific kind of failure dependency is taken into account. To solve the optimization problem, a resolution approach based on Genetic Algorithms (GA) is presented. Finally, a numerical application is carried out. The GA results are compared with the results given by LINGO which is a dedicated optimization software. It is used to validate the efficiency of the proposed approach.

International audience; This paper discusses a multi-item capacitated lot-sizing and scheduling problem in a flow-shop system with energy consideration. A mixed integer linear programming is formulated. The planning horizon is defined by a set of periods where each one is characterized by a length, an electricity price, a maximal allowed power and an external demand. Since the capacitated lot-sizing problems are NP-hard, a fix-and-relax heuristic is developed. To evaluate the effectiveness of the proposed heuristic, computational experiments are presented and numerical results are discussed and analyzed. The obtained results are promising.

International audience; In this paper we report two mixed integer linear programming models to resolve the malleable jobs scheduling problem with single resource. Jobs’ release dates and deadlines are taken into account. The total amount of available resource of the system is variable at different times. Numerical experimentation is conducted to evaluate the performance variability between two introduced models. The objective of this optimization problem is to minimize the total weighted completion time.

International audience; This paper proposes a new optimization approach to find the best redundancy allocation of dependent repairable series k—out—of—n : G system using ant colony optimization. A model for the failure redundant dependency between the system components is formulated. It is considered in the system performance evaluation. An optimization model is then derived to be solved using the software LINGO and the proposed ACO algorithm. The objective consists of minimizing the system cost while satisfying a required level of system availability. The best system configuration in terms of number of components and number of repair teams in each subsystem is to be determined. The components are characterized by their failure rate, repair rate, unit acquisition cost and unit repair cost. In order to validate the proposed approach, an illustrative example is applied. A comparison between LINGO and ACO results is facilitated. The results show that the redundant dependency may positively affect the design configuration and the system cost. Furthermore, the proposed ACO outperforms LINGO for large scale systems in term of solution quality.

International audience; Parallel redundancy is a fundamental concept widely used to maximize system reliability/availability. However, any enhancement in the system reliability requires resources which consequently increases the costs. Hence, it is important to optimize the system configuration at the design phase. It is demonstrated that modeling the dependency between system components can be an effective option to improve system reliability in an economic way. But, the resolution of the optimization problem by analytic methods may be difficult and expensive in terms of computational time especially for large scale and complex systems. This paper proposes a rapid and effective approach to optimize the cost of a reparable system with dependent components under the availability constraint. The optimization model is solved using the software tool LINGO and the genetic algorithm (GA). A comparison between LINGO and the GA results is established. The results show the superiority of the GA in term of speed with a small difference in the exactitude of the obtained solutions.

International audience; This paper deals with a pick and place robotic system design problem. The objective is to present an efficient method which is able to optimize the performances of the robotic system. By defining the suitable combination of scheduling rules, our method allows each robot to perform the assigned pick and place operations in real time in order to maximize the throughput rate. For that, we have developed different resolution methods which define the scheduling rule for each robot in order to seize the products from the first side of the system and to place them on the second side. We suggest three metaheuristics which are the ant colony optimization, the particle swarm optimization and the genetic algorithm. Then, we try to select the best algorithm which is able to get the best solutions with the lowest execution times. This is the main advantage of our methods compared to exact methods. This fact represents a great interest taking in consideration that our methods must respect a strong industrial constraint regarding the functioning of a real industrial robotic system. This constraint states that the answer time to manage the seizing strategies of the robots must be less than 1 second. Numerical results show that the different algorithms perform optimally for the tested instances in a reasonable computational time.

International audience; This paper deals with a multiobjective parallel machines scheduling problem. It consists in scheduling n independent jobs on m identical parallel machines. The job data such as processing times, release dates, due dates and sequence dependent setup times are considered. The goal is to optimize two different objectives: the makespan and the total tardiness. A mixed integer linear program is proposed to model the studied problem. As this problem is NP-hard in the strong sense, a metaheuristic method which is the second version of the non dominated sorting genetic algorithm (NSGA-II) is proposed to solve this problem. Since the parameters setting of a genetic algorithm is difficult, a fuzzy logic controller coupled with the NSGA-II (FLC-NSGA-II) is therefore proposed. The role of the fuzzy logic is to better set the crossover and the mutation probabilities in order to update the search ability. After that, an exact method based on the two phase method is also developed. We have used four measuring criteria to compare these methods. The experimental results show the advantages and the efficiency of FLC-NSGA-II.

International audience; This paper reports on a new Multi-Level Capacitated Lot-Sizing Problem (MLCLSP) taking into account the energetic aspect. A linear mixed integer programming model is proposed to solve this problem. Since the MLCLSP is NP-hard ([10]), two heuristics, that provide solutions in a reasonable computational time, are developed. In this study, the horizon is split into T periods where each one is characterized by a duration, an electricity cost, a maximum peak power and a demand. To evaluate the performance of the model and the heuristics, computational experiments are presented and numerical results are discussed.