Résumé

The continuous development of Internet infrastructures and the evolution of digital electronics, particularly Nano-computers, are making the Internet of Things (IoT) emergent. Despite the progress, these IoT objects suffer from a crucial problem which is their limited power supply. IoT objects are often deployed as an ad-hoc network. To minimize their consumption of electrical energy, clustering techniques are used. In this paper, a centralized clustering algorithm with single-hop routing based on a genetic algorithm and Improved k-means is proposed. The proposed approach is compared with the LEACH, K-means and OK-means algorithms. Simulation results show that the proposed algorithm performs well in terms of network lifetime and energy consumption.

Résumé

Multiple-job-class sequencing problems solve a group of jobs belonging to multiple classes, where to decrease the processing time, jobs in the same class tend to be performed together with the same setup time. In contrast, customer order scheduling problems focus on completing all jobs (belonging to different classes) in the same order at the same time to reduce shipping costs. Because related studies on multiple-job-class sequencing problems with more than one criterion are quite limited in the current research community, this study investigates tri-criteria scheduling problems with multiple job classes and customer orders on a single machine, where the goal is to minimize a linear combination of the makespan, total completion times of all jobs, and sum of the ranges of all orders. Due to the high complexity of the proposed problem, mixed integer programming is developed to formulate the problem, and a branch-and-bound method along with a lower bound and a property is utilized for finding the optimal schedules. Then, two heuristics and a simulated annealing algorithm are proposed to solve the problem approximately. The simulation results of the proposed heuristics and algorithm are evaluated through statistical methods.

Résumé

Hyperheuristics represent a generic method that provides a high level of abstraction, enabling solving several problems in the combinatorial optimization domain while reducing the need for human intervention in parameters tuning. This category consists in managing a set of low-level heuristics and attempting to find the optimal sequence that produces high-quality results. This paper proposes a hyperheuristic that simulates the honey bees mating behavior called “Honey bee Mating Optimization HyperHeuristic”  to solve the Patient Admission Scheduling Problem (PASP). The PASP is an NP-hard problem that represents an important field in the health care discipline. In order to perceive the influence of low-level heuristics on the model’s performance, we implemented two versions of the hyperheuristic that each one works on a different set of low-level heuristics. The results show that one of the versions generates better results than the other, revealing the important role of low-level heuristics’ quality leading to enhancing the hyperheuristic performance.

Résumé

Among the well-known scheduling problems, the customer order scheduling problem (COSP) has
always been of great importance in manufacturing. To reflect the reality of COSPs as much as
possible, this study considers that jobs from different orders are classified in various classes. This
paper addresses a tri-criteria single-machine scheduling model with multiple job classes and
customer orders on which the measurement minimizes a linear combination of the sum of the ranges
of all orders, the tardiness of all orders, and the total completion times of all jobs. Due to the NPhard complexity of the problem, a lower bound and a property are developed and utilized in a
branch-and-bound for solving an exact solution. Afterward, four heuristics with three local
improved searching methods each and a water wave optimality algorithm with four variants of
wavelengths are proposed. The tested outputs report the performances of the proposed methods

Résumé

The multiple job class scheduling problem arises in contexts where a group of jobs belong to multiple classes and in which if all jobs in the same class are operated together, extra setup times would not be needed. On the other hand, the customer order scheduling problem focuses on finishing all jobs from the same order at the same time in order to reduce shipping costs. However, works on customer orders coupled with class setup times do not appear often in the literature. Hence we address here a bicriteria single machine customer order scheduling problem together with multiple job classes. The optimality criterion minimizes a linear combination of the sum of the ranges and sum of tardiness of all customer orders. In light of the high complexity of the concerned problem, we propose a lower bound formula and a property to be used in a branch-and-bound method for optimal solutions. To find approximate solutions, we then propose four heuristics together with a local search method, four cloudy theoretical simulated annealing and a cloudy theoretical simulated annealing hyperheuristic along with five low-level heuristics. The simulation results of the proposed heuristics and algorithms are analyzed.

Résumé

Green manufacturing imposes higher expectations on manufacturing engineering, not only with respect to classic competitive factors such as cost, time and quality, but also with sustainable factors such as resources and energy. In this paper, we investigate green flexible job shop scheduling problem (GFJSP) with variable processing speeds. To solve the GFJSP problem, we propose an adaptive Variable Neighborhood Search to minimize the makespan and the total energy consumption. A number of experiments have been conducted to evaluate the performance of our proposed adaptive VNS algorithm. A comparative study was presented and have verified the out performance of the proposed algorithm against other VNS variants.

Résumé

Efficient inventory management (IM) presents an
important key driver for supply chain (SC) sustainability.
This latter becomes a crucial concern for decision-makers and
managers in all domains, particularly in the matter of sensitive
areas that affect human well-being, namely the pharmaceutical
industry. Medicines IM for a sustainable Pharmaceutical Sup-
ply Chain (PSC) brought further particularities compared to
the traditional SCs. Besides the economic preoccupation, social
and environmental issues might be considered. In this work, we
assess the impact of the Lateral Transshipment (LT) strategy on
the sustainability of the IM process. We compare the total costs
of two cases, IM with and without LT strategy. We propose an
IM model that seeks the optimal replenishment order quantity
of multiple types of products and the shipment time in a
two-echelon PSC under a centralized setting. The considered
PSC consists of a pharmaceutical company (PC), a Pharma-
distributor (PD), and multiple hospitals. The mathematical
model takes into account the transportation costs including LT
costs -in the case when LT is included- as well as shortage,
and products with high deterioration rate costs. We attempt
to minimize unused medicines leftover by minimizing the
deterioration rate of products at both distributor and hospital
sites.

Résumé

This paper studies a single-machine multitasking scheduling problem together with two-agent consideration. The objective
is to look for an optimal schedule to minimize the total tardiness of one agent subject to the total completion time of another
agent has an upper bound. For this problem, a branch-and-bound method equipped with several dominant properties and a
lower bound is exploited to search optimal solutions for small size jobs. Three metaheuristics, cloud simulated annealing
algorithm, genetic algorithm, and simulated annealing algorithm, each with three improvement ways, are proposed to fnd the
near-optimal solutions for large size jobs. The computational studies, experiments, are provided to evaluate the capabilities for
the proposed algorithms. Finally, statistical analysis methods are applied to compare the performances of these algorithms.

Résumé

Time-dependent scheduling problems, where the real processing time of jobs is dependent on the starting time, have received growing attention in recent decades. In particular, scheduling problems on a single machine have been widely studied in many facets that address the learning effect and diverse processing environments or time-dependent processing scheduling. Motivated by this observation, we introduce a variant based on the industrial procedure consideration; that is, owing to due date pressure, the processing time of the remaining jobs should be shortened after a period of manufacturing process. We consider a new single-machine scheduling problem with step-improving processing times where the objective function is to find a schedule to minimize a linear combination of the total weighted completion time and total tardiness of all jobs. The proposed problem without a critical date is an NP-hard problem. Therefore, a mixed integer programming model as well as a branch-and-bound (B&B) along with several dominance properties and a lower bound on the completion of an active partial schedule is utilized for solving the problem under study. Subsequently, four variants of the water wave optimization algorithm and four variants of the simulated annealing algorithms were proposed to solve this problem. The simulation results showed that the branch-and-bound method can solve instance problems for up to twelve jobs. The results also showed that all four variants of the wave optimization algorithm did not perform uniformly better than all three variants of the simulated annealing algorithms.

Résumé

Electric Vehicles (EVs) are regarded to be among the most environmentally and economically efficient transportation solutions. However, barriers and range limitations hinder this technology’s progress and deployment. In this paper, we examine EV route planning to derive optimal routes considering energy consumption by analyzing historical trajectory data. More specifically, we propose a novel approach for EV route planning that considers real-time traffic incidents, road topology, charging station locations during battery failure, and finally, traffic flow prediction extracted from historical trajectory data to generate energy maps. Our approach consists of four phases: the off-line phase which aims to build the energy graph, the application of the A* algorithm to deliver the optimal EV path, the NEAT trajectory clustering which aims to produce dense trajectory clusters for a given period of the day, and finally, the on-line phase based on our algorithm to plan an optimal EV path based on real traffic incidents, dense trajectory clusters, road topology information, vehicle characteristics, and charging station locations. We set up experiments on real cases to establish the optimal route for electric cars, demonstrating the effectiveness and efficiency of our proposed algorithm.

Résumé

Improving sustainability in Pharmaceutical Supply Chain (PSC) becomes theprimary concern for its involved members. It lends major challenges to its management as it haseconomic, social, and environmental responsibilities more weighed than other supply chains.Providing the day-to-day need for medicines must be satisfied while taking into account theuse of the economic resource, customer satisfaction, and the impact of pharmaceutical wasteon the environment. Medicines waste affects healthcare expenses and harms the environment.Therefore, avoiding unused medication leftover through the pharmaceutical chain presents anefficient approach to attaining a sustainable supply of medicines. This article aims to deal withthe sustainability of a PSC by minimizing the deterioration rate of medicines at both distributorand hospitals sites. We propose an inventory management model based on a mixed-integernon-linear program (MINLP) that seeks the optimal replenishment order quantity of multipletypes of products and the shipment time in a two-echelon PSC consisting of a pharmaceuticalcompany (PC), a central pharmacy (CP), and multiple hospitals over a planning horizon, whileconsidering shipment costs, perishability, and shortage constraints.

Résumé

Bag-of-Tasks is a well-known model that processes big-data applications supporting embarrassingly parallel jobs with independent tasks. Scheduling Bag-of-Tasks in a dynamic multi-cloud environment is an NP-hard problem that has attracted a lot of attention in the last years. Such a problem can be modeled using a bi-level optimization framework due to its hierarchical scheme. Motivated by this issue, in this paper, an efficient bi-level multi-follower algorithm, based on hybrid metaheuristics, is proposed to solve the multi-objective budget-constrained dynamic Bag-of-Tasks scheduling problem in a heterogeneous multi-cloud environment. In our proposed model, the objective function differs depending on the scheduling level: The upper level aims to minimize the makespan of the whole Bag-of-Tasks under budget constraints; while each follower aims to minimize the makespan and the execution cost of tasks belonging to the Bag-of-Tasks. Since multiple conflicting objectives exist in the lower level, we propose an improved variant of the Non-dominated Sorting Genetic Algorithm II (NSGA-II) called Efficient NSGA-II (E-NSGA-II), applying a recently proposed quick non-dominated sorting algorithm (QNDSA) with quasi-linear average time complexity. By performing experiments on proposed synthetic datasets, our algorithm demonstrates high performance in terms of makespan and execution cost while respecting budget constraints. Statistical analysis validates the outperformance of our proposal regarding the considering metrics.

Résumé

In the last few years, there has been an increasing interest in Random Constraint Satisfaction Problems (CSP) from both experimental and theoretical points of view. To consider a variant instance of the problems, we used a random benchmark. In the present paper, some work has been done to find the shortest Hamiltonian circuit among specified nodes in each superimposed graph (SGs). The Hamiltonian circuit is a circuit that visits each node in the graph exactly once. The Hamiltonian path may be constructed and adjusted according to specific constraints such as time limits. A new constraint satisfaction optimization problem model for the circuit Hamiltonian circuit problem in a superimposed graph has been presented. To solve this issue, we propose amelioration for the genetic algorithm using Dijkstra’s algorithm, where we create the improved genetic algorithm (IGA). To evaluate this approach, we compare the CPU and fitness values of the IGA to the results provided by an adapted genetic algorithm to find the shortest Hamiltonian circuit in a superimposed graph.

Résumé

Résumé

Vehicular Ad Hoc Networks (VANETs) are a particular class of Mobile Ad Hoc Networks (MANETs). The VANETs provide wireless communication among vehicles and vehicle-to-road-side units. Even though the VANETs are a specific type of MANETs, a highly dynamic topology is a main feature that differentiates them from other kinds of ad hoc networks. As a result, designing an efficient routing protocol is considered a challenge.  The performance of vehicle-to-vehicle communication depends on how better the routing protocol takes in consideration the particularities of the VANETs. Swarm Intelligence (SI) is considered as a promising solution to optimize vehicular communication costs. In this paper, we explore the SI approach to deal with the routing problems in the VANETs. We also evaluate and compare two swarming agent-based protocols using numerous QoS parameters, namely the average end-to-end delay and the ratio packet loss which influence the performance of network communication.

Résumé

This study examines a two-stage three-machine flow-shop assembly scheduling model in which job processing time is considered as a mixed function of a controlled truncation parameter with a sum-of-processing-times-based learning effect. However, the truncation function is very limited in the two-stage flow-shop assembly scheduling settings. To overcome this limitation, this study investigates a two-stage three-machine flow-shop assembly problem with a truncation learning function where the makespan criterion (completion of the last job) is minimized. Given that the proposed model is NP hard, dominance rules, lemmas and a lower bound are derived and applied to the branch-and-bound method. A dynamic differential evolution algorithm, a hybrid greedy iterated algorithm and a genetic algorithm are also proposed for searching approximate solutions. Results obtained from test experiments validate the performance of all the proposed algorithms.

Résumé

Task scheduling problem has attracted a lot of attention since it plays a key role to improve the performance of any distributed system. This is again more challenging, especially for multi-cloud computing environment, mainly based on the nature of the multi-cloud to scale dynamically and due to heterogeneity of resources which add more complexity to the scheduling problem. In this paper, we propose, for the first time, a new Hybrid Bi-level optimization model named HB-DBoTSP to solve the Dynamic Bag-of-Tasks Scheduling Problem (DBoTSP) in heterogeneous multi-cloud environment. The proposed model aims to minimize the makespan and the execution cost while taking into consideration budget constraints and guaranteeing load balancing between Cloud’s Virtual Machines. By performing experiments on synthetic data sets that we propose, we demonstrate the effectiveness of the algorithm.

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é

The two-stage assembly scheduling problem has received growing attention in the research community. Furthermore, in many two-stage assembly scheduling problems, the job processing times are commonly assumed as a constant over time. However, it is at odds with real production situations some times. In fact, the dynamic nature of processing time may occur when machines lose their performance during their execution times. In this case, the job that is processed later consumes more time than another one processed earlier. In view of these observations, we address the two-stage assembly linear deterioration scheduling problem in which there are two machines at the first stage and an assembly machine at the second stage. The objective is to complete all jobs as soon as possible (or to minimise the makespan, implies that the system can yield a better and efficient task planning to limited resources). Given the fact that this problem is NP-hard, we then derive some dominance relations and a lower bound used in the branch-and-bound method for finding the optimal solution. We also propose three metaheuristics, including dynamic differential evolution (DDE), simulated annealing (SA) algorithm, and cloud theory-based simulated annealing (CSA) algorithm for find near-optimal solutions. The performances of the proposed algorithms are reported as well.

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é

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é

Vehicular Ad hoc NETworks (VANETs) are a special kind of Mobile Ad hoc NETworks (MANETs), which can provide scalable solutions for applications such as traffic safety, internet access, etc. To properly achieve this goal, these applications need an efficient routing protocol. Yet, contrary to the routing protocols designed for the MANETs, the routing protocols for the VANETs must take into account the highly dynamic topology caused by the fast mobility of the vehicles. Hence, improving the MANET routing protocol or designing a new one specific for the VANETs are the usual approaches to efficiently perform the routing protocol in a vehicular environment. In this context, we previously enhanced the Destination-Sequenced Distance-Vector Routing protocol (DSDV) based on the Particle Swarm Optimization (PSO) and the Multi-Agent System (MAS). This motivation for the PSO and MAS comes from the behaviors seen in very complicated problems, in particular routing. The main goal of this paper is to carry out a performance evaluation of the enhanced version in comparison to a well-known routing protocol which is the Intelligent Based Clustering Algorithm in VANET (IBCAV). The simulation results show that integrating both the MAS and the PSO is able to guarantee a certain level of quality of service in terms of loss packet, throughput and overhead.

Résumé

Because of the rapid growth of air traffic, optimizing airport management is becoming necessary in order to improveairport's capacity and better align its resources to the received traffic. In this paper we study the assignment of the arriving aircrafts to the available gates using the fixed daily schedule. We introduce a new approach based on Genetic Algorithms (GA) to solve the gate assignment problem (GAP). The encoding strategy consists in representing the chromosome by a vector of integers. The index of each gene represents the flight number and its value represents the gate to which the flight will be assigned. The method used to generate the initial population is based on three different heuristics and a random sorting of the gates. The selection method is the “In fitness proportionate selection” known as “roulette wheel selection”. In addition to one point and two point Crossover operators, we designed a Greedy procedure Crossover (GPX) operator. The experimentation is based on the use of fictive scenarios generated in accordance with the physical characteristics of the Tunis Carthage Airport and using different flight schedules. The comparison between deterministic approach, simple heuristics and the GA has shown the efficiency of the last approach in terms of solution's quality when we aim at solving the problems of large size. In order to determine the best configuration of the GA, we compared the different crossover operators and we noticed that the use of GPX improves the speed of convergence of the algorithm towards better solutions.