Résumé

Bi-level optimization is a challenging research area that has received significant attention from researchers to model enormous NP-hard optimization problems and real-life applications. In this paper, we propose a new evolutionary bi-level algorithm for Flexible Job Shop Problem with Sequence-Dependent Setup Time (SDST-FJSP) and learning/deterioration effects. There are two main motivations behind this work. On the one hand, learning and deterioration effects might occur simultaneously in real-life production systems. However, there are still ill posed in the scheduling area. On the other hand, bi-level optimization was presented as an interesting resolution scheme easily applied to more complex problems without additional modifications. Motivated by these issues, we attempt in this work to solve the FJSP variant using the bi-level programming framework. We suggest firstly a new bi-level mathematical formulation for the considered FJSP; then we propose a bi-level evolutionary algorithm to solve the problem. The experimental study on well-established benchmarks assesses and validates the advantage of using a bi-level scheme over the compared approaches in this research area to solve such NP-hard problem.

Résumé

For the most schedulling problems studied in literature, job processing times are assumed to be known and constant over time. However, this assumption is not appropriate for many realistic situations where the employees and the machines execute the same task in a repetitive manner. They learn how to perform more efficiently. As a result, the processing time of a given job is shorter if it is scheduled later, rather than earlier in the sequence. In this paper, we consider the flexible job-shop problem (FJSP) with two kinds of constraint, namely, the sequence-dependent setup times (SDST) and the learning effects. Makespan is specified as the objective function to be minimised. To solve this problem, an adaptive genetic algorithm (AGA) is proposed. Our algorithm uses an adaptive strategy based on: 1) the current specificity of the search space; 2) the preceding results of already used operators; 3) their associated parameter settings. We adopt this strategy in order to maintain the balance between exploration and exploitation. Experimental studies are presented to assess and validate the benefit of the incorporation of the learning process to the SDST-FJSP over the original problem.

Résumé

In this article, the multi-depot heterogeneous fleet vehicle routing problem with time window (MDHFVRPTW) is considered. The objective of this work is to minimize the total traveled distance while delivering goods to geographically dispersed customers. In our research we solved the MDHFVRPTW with a multi-agent approach based on the hybridization of three meta-heuristics which are a particle swarm optimization algorithm (PSO), a genetic algorithm (GA) and a memetic algorithm (MA). A mathematical programming model for the problem is presented. In order to show the performance of the proposed approach we tested it on different benchmarks and we compared it with other results obtained from the literature.

Résumé

Cloud computing has reached huge popularity for delivering on-demand services on a pay-per-use basis over the internet. However, since the number of cloud users evolves, multi-cloud environment has been introduced where clouds are interconnected in order to satisfy customers' requirements. Task scheduling in such environments is very challenging mainly due to the heterogeneity of resources. In this paper, a budget-constrained dynamic Bag-of-Tasks scheduling algorithm for heterogeneous multi-cloud environment is proposed. By performing experiments on synthetic data sets that we propose, we demonstrate the effectiveness of the algorithm in terms of makespan.

Résumé

Résumé

Flexible Job Shop Problem (FJSP) has an important significance in both fields of production management and combinatorial optimization. This problem is decomposed into two sub-problems: the assignment problem and the scheduling problem. Following this structure, we consider in this work the FJSP as a bilevel problem. For that, we are interested to solve this problem with bilevel optimization method in which the upper level optimizes the assignment problem and the lower level optimizes the scheduling problem. Therefore, we propose, for the first time, an hybrid bilevel optimization model named HB-FJSP based on both exact and approximate methods to solve the FJSP in order to minimize the makespan. The computational results confirm that our model HB-FJSP provides better solutions than other models.

Résumé

Job-shop scheduling problem is one of the most important fields in manufacturing optimization where a set of n jobs must be processed on a set of m specified machines. Each job consists of a specific set of operations, which have to be processed according to a given order. The Flexible Job Shop problem (FJSP) is a generalization of the above-mentioned problem, where each operation can be processed by a set of resources and has a processing time depending on the resource used. The FJSP problems cover two difficulties, namely, machine assignment problem and operation sequencing problem. This paper addresses the flexible job-shop scheduling problem with sequence-dependent setup times to minimize two kinds of objectives function: makespan and bi-criteria objective function. For that, we propose a hybrid algorithm based on genetic algorithm (GA) and variable neighbourhood search (VNS) to solve this problem. To evaluate the performance of our algorithm, we compare our results with other methods existing in literature. All the results show the superiority of our algorithm against the available ones in terms of solution quality.

Résumé

Flexible job shop problems (FJSP) are among the most intensive combinatorial problems studied in literature. These latters cover two main difficulties, namely, machine assignment problem and operation sequencing problem. To reflect as close as possible the reality of this problem, two others constraints are taken into consideration which are: (1) The sequence dependent setup time and (2) the learning effects. For solving such complex problem, we propose an evolutionary algorithm (EA) based on genetic algorithm (GA) combined with two efficient local search methods, called, variable neighborhood search (VNS) and iterated local search (ILS). It is well known that the performance of EA is heavily dependent on the setting of control parameters. For that, our algorithm uses a self-adaptive strategy based on: (1) the current specificity of the search space, (2) the preceding results of already applied algorithms (GA, VNS and ILS) and (3) their associated parameter settings. We adopt this strategy in order to detect the next promising search direction and maintain the balance between exploration and exploitation. Computational results show that our algorithm is more effective and robust with respect to other well known effective algorithms.

Résumé

Traditionally, the processing times of jobs are assumed to be fixed and known throughout the entire process. However, recent empirical research in several industries has demonstrated that processing times decline as workers improve their skills and gain experience after doing the same task for a long time. This phenomenon is known as learning effects. Recently, several researchers have devoted a lot of effort on scheduling problems under learning effects. Although there is increase in the number of research in this topic, there are few review papers. The most recent one considers solely studies on scheduling problems with learning effects models prior to early 2007. For that, this paper focuses on reviewing the most recent advances in this field. First, we attempt to present a concise overview of some important learning models. Second, a new classification scheme for the different model of scheduling under learning effects is proposed and discussed. Next, a cartography showing the relation between some well-known models is proposed. Finally, our viewpoints and several areas for future research are provided.

Résumé

Flexible Job Shop Problem (FJSP) has an important significance in both fields of production management and combinatorial optimization. This problem is decomposed into two sub-problems: the assignment problem and the scheduling problem. Following this structure, we consider in this work the FJSP as a bilevel problem. For that, we are interested to solve this problem with bilevel optimization method in which the upper level optimizes the assignment problem and the lower level optimizes the scheduling problem. Therefore, we propose, for the first time, an hybrid bilevel optimization model named HB-FJSP based on both exact and approximate methods to solve the FJSP in order to minimize the makespan. The computational results confirm that our model HB-FJSP provides better solutions than other models.

Résumé

The flexible job shop problem (FJSP) has an important significance in both fields of production management and combinatorial optimization. This problem covers two main difficulties, namely, machine assignment problem and operation sequencing problem. To reflect as close as possible the reality of this problem, the sequence dependent setup time is taken into consideration. For solving such a complex problem, we propose a hybrid algorithm based on a genetic algorithm (GA) combined with iterated local search (ILS). It is well known that the performance of an algorithm is heavily dependent on the setting of control parameters. For that, our algorithm uses a self-adaptive strategy based on : (1) the current specificity of the search space, (2) the preceding results of already applied algorithms (GA and ILS) and (3) their associated parameter settings. We adopt this strategy in order to detect the next promising search

Résumé

Job shop scheduling problems (JSSP) are among the most intensive combinatorial problems studied in literature. The flexible job shop problem (FJSP) is a generalization of the classical JSSP where each operation can be processed by more than one resource. The FJSP problems cover two difficulties, namely, machine assignment problem and operation sequencing problem. This paper investigates the flexible job-shop scheduling problem with sequence-dependent setup times to minimize two kinds of objectives function: makespan and bi-criteria objective function. For that, we propose a genetic algorithm (GA) to solve this problem. To evaluate the performance of our algorithm, we compare our results with other methods existing in literature. All the results show the superiority of our GA against the available ones in terms of solution quality.

Résumé

No doubt, the flexible job shop problem (FJSP) has an important significance in both fields of production management and combinatorial optimization. For this reason, FJSP continues to attract the interests of researchers both in academia and industry. In this paper, we propose a new multi-agent model for FJSP. Our model is based on cooperation between genetic algorithm (GA) and tabu search (TS). We used GA operators as a diversification technique in order to enhance the searching ability of TS. The computational results confirm that our model MAS-GATS provides better solutions than other models.

Résumé

Flexible job shop scheduling problem (FJSP) is an important extension of the classical job shop scheduling problem, where the same operation could be processed on more than one machine and has a processing time depending on the machine used. The objective is to minimize the makespan, i.e., the total duration of the schedule. In this article, we propose a multi-agent model based on the hybridization of the tabu search (TS) method and particle swarm optimization (PSO) in order to solve FJSP. Different techniques of diversification have also been explored in order to improve the performance of our model. Our approach has been tested on a set of benchmarks existing in the literature. The results obtained show that the hybridization of TS and PSO led to promising results.

Résumé

The Flexible Job Shop problem (FJSP) is an important extension of the classical job shop scheduling problem, in that each operation can be processed by a set of resources and has a processing time depending on the resource used. The objective is to minimize the make span, i.e., the time needed to complete all the jobs. This works aims to propose a new promising approach using multi-agent systems in order to solve the FJSP. Our model combines a local optimization approach based on Tabu Search (TS) meta-heuristic and a global optimization approach based on genetic algorithm (GA).

Résumé

The Flexible Job Shop problem is among the hardest scheduling problems. It is a generalization of the classical Job Shop problem in that each operation can be processed by a set of resources and has a processing time depending on the resource used. The objective is to assign and to sequence the operations on the resources so that they are processed in the smallest time. In our previous work, we have proposed two Multi-Agent approaches based on the Tabu Search (TS) meta-heuristic. Depending on the location of the optimisation core in the system, we have distinguished between the global optimisation approach where the TS has a global view on the system and the local optimisation approach (FJS MATSLO) where the optimisation is distributed among a collection of agents, each of them has its own local view. In this paper, firstly, we propose new diversification techniques for the second approach in order to get better results and secondly, we propose a new promising approach combining the two latter ones. Experimental results are also presented in this paper in order to evaluate these new techniques.