This paper studies the flexible job-shop scheduling problem (FJSP) with the objective of minimizing the total completion time. This problem is known to be strongly NP-hard [1]. Therefore, it is quite difficult to achieve an optimal solution to this problem with exact methods and heuristic approaches are generally used to find near optimal solutions within a reasonable computation time. The present work proposes a Random-Key based genetic algorithm for the joint resolution of the inherent assignment and sequencing subproblems. A new chromosome encoding method with some effective crossover and mutation operators are introduced. Also, a mixed integer linear program is developed and tested. Computational experiments are carried out on a large set of instances. The proposed algorithm is proved to be both effective and efficient in solving the studied problem.

The purpose of this work is to propose effective approximate algorithms capable to generate, in a very short time, feasible 2-dimensional configurations (interfaces) containing a set of given menus adapted to a certain user context (physical activity for example). As in some previous works, the proposed approach gives good solutions that minimize the used surface to pack all the tiles into a variable-size bin. Such a size should respect a fixed ratio for the screen between its width and its height. Moreover, the proposed approaches (based on shelf strategy), genetic algorithm are compared to an exact model. The exact resolution of this mathematical model gives an optimal solution only for small instances. For the other instances, it is difficult to reach the optimal value in a short running time, which shows the practical interest of the proposed approaches.

We consider the online time series search problem with interrelated prices. Using the already established UND algorithm of [5], we develop one new optimal online algorithm o-UND which improves the experimental performance of an optimal solution for selected parameter combinations. We conduct an experimental testing of UND and o-UND and establish the parameter combinations for which one algorithm is better than the other. We then combine these two algorithms into a new one called POUND. This algorithm incorporates the strengths of UND and o-UND and is also optimal.

In this paper, we consider the two-parallel machine scheduling problem with a non-availability interval. We aim to minimize the maximum lateness when every job has a positive tail. We show that the problem has a constant polynomial approximation algorithm. We present a dynamic programming algorithm and we show that the problem has an FPTAS (Fully Polynomial Time Approximation Algorithm). The proposed FPTAS has a strongly polynomial running time. Finally, we present some numerical experiments and we analyze the obtained results.

In this paper, we present a genetic algorithm for the open shop scheduling problem. We use a simple and efficient chromosome representation based on the job's occurrence and the fitness function reflect the length of the schedule. The solutions obtained after performing the different operators of the genetic algorithm are always feasible. Heuristic approaches are also developed to generate the initial population and to improve the obtained solutions. The algorithm was implemented and computational results show interesting result.

In this paper, we consider four single-machine scheduling problems with release times, with the aim of minimizing the maximum lateness. In the first problem we have a common deadline for all the jobs. The second problem looks for the Pareto frontier with respect to the two objective functions maximum lateness and makespan. The third problem is associated with a non-availability constraint. In the fourth one, the non-availability interval is related to the operator who is organizing the execution of jobs on the machine (no job can start, and neither can complete during the operator non-availability period). For each of the four problems, we establish the existence of a polynomial time approximation scheme.

This paper considers the problem of scheduling on a heterogeneous CPU/FPGA architecture with communication delays, with the aim of minimizing the makespan (or the schedule length). For this strongly NP-hard problem, we present two iterative algorithms based on simulated annealing (SA) and genetic algorithms (GAs), which are used to run in the MPSoC an application described in a data flow graph. The performance of the proposed algorithms are evaluated and compared on a set of instances with up to 50 tasks. Computational experiments indicate that the innovative proposed algorithms provide competitive results for the studied problem and that the objective function values obtained are optimal or very close to a lower bound in a reasonable computation time.

In this paper we present a mathematical formulation for solving open shop scheduling problem. We derived different classes of valid inequalities to strength the model. Exhaustive computational experiments on the well known sets of Taillard's benchmarks are presented. The derived valid inequalities show a good improvement to the computational time for the proposed model.

This talk will summarize the main characteristics of the scheduling problems and introduce the non-availability constraints' context. More precisely, we will focus on the description of two scenarios: the offline and the semi-online contexts. The first part of this talk will be devoted to the presentation of the considered optimization problems and their applications. In the second part, we will show that the performance evaluation of some heuristics can be analytically done in the context of the polynomial approximation theory. The differential and absolute approximation measures will be described. As an illustration, we will show analytically some guaranteed performance ratios of approximation algorithms and schemes for solving scheduling problems under non-availability constraints. The studied criterion is the maximum lateness in offline and semi-online contexts.

This paper deals with the mathematical modeling of a scheduling problem for unrelated parallel machines with precedence constraints in order to minimize the makespan (Cmax). This study was motivated by the quality of the Integer Program based on the interval graph. Three families of inequalities are proposed. The first two inequalities based on the idea of the precedence jobs and the third based on the shortest processing time(SPT). We studied the validity of the new inequalities and strength them by checking the linear combination. After an exhaustive computational and statistical analysis we can conclude that the addition of these inequalities decreases the computational requirements to obtain the optimal solution in many cases.

Many applications in wireless sensor network (WSN) involve the execution of multiple computationally heavy in-network processing tasks. Collaborative in-network processing among different sensor nodes is critical due to the limited capability of a single node. Task allocation is required to assign efficiently the workload of each task. In this paper, Logic Gate-based Evolutionary Algorithm (LGEA) is introduced which implements the logic gate mechanism in order to solve the task allocation problem. Each individual stands for a potential task allocation solution. The overall problem is formulated as a binary multiobjective optimization problem. The task workload and connectivity are the constraints that must be satisfied. The aim is to minimize the number of active nodes, the computation and the communication load distribution. Simulations confirm the potential of the logic gate mechanism to find the optimized task allocation scheme. The LGEA also outperforms the binary approach based on the Binary Particle Swarm Optimization (BPSO). Therefore, the Logic operation represents an original strategy and an efficient procedure for the binary optimization.

Diffusion action is a key behavior of users in online social networks. This action may further propagate to other connections of the users and affect their actions. Recent research has focused on studying the diffusion action of users, particularly, predicting information diffusion in future. However, most of current diffusion models mainly focus on giving general model of diffusion. In this paper, we propose a model of information diffusion prediction which analyzes all factors affecting users' diffusion decision such as user features, link features and crowd-features. In addition, we take into account the presence of multi-topics in the content item. We validate our model by conducting experiments on a snapshot of Twitter containing tweets and retweets involving French media, which demonstrates the interest of our model.

We consider bi-directional non-preemptive conversion with interrelated conversion rate bounds. We solve this conversion problem with two on-line algorithms BUND and RUN and give their competitive ratio. We further observe optimality of both on-line algorithms. We also use empirical data of the Johannesburg Stock Exchange to get further insights into RUN and BUND.

Despite the rapid pace of gadgets released on the market, research in the area of usable interfaces for wearables is lagging behind. Smartglasses are new wearables that embed diverse sensors but also have small displays, and this makes it hard for the wearer to visualize real-time data. To bridge this gap, the contribution of this paper is threefold. First, we propose a data representation model to combine applications and services that match user activities and contexts. Second, we present an approach of showing relevant services to the user based on `tiles' (such as those in recent Microsoft Windows interfaces) while considering the device constraints. Finally, we suggest that combining those two aspects can open the way to personalized services for the end user, creating new ways of interacting with applications and devices.

The main aim of this paper is to express the techniques which can solve reactive scheduling problem in operating room and then compare them for ranking. On the one hand importance of scheduling for operating rooms in hospitals is increasing for the reasons like hospitals reputations and expenses and on the other hand in real world, scheduling of operating rooms is not often static. Hence, the authors have made an endeavor to show the reactive scheduling in this field. There are many techniques and methods to solve the problem, but academics and practitioners are concerned with the best techniques in this field. Therefore, an attempt has been made to represent and compare and rank the most common techniques by applying the analytic hierarchy process (AHP) and fuzzy technique for order preference by similarity to ideal solution (TOPSIS).

We consider the single machine scheduling problem with release dates and tails, provided that the machine is unavailable during a fixed interval. This problem is strongly NP-hard. We use the Jackson's preemptive algorithm with precedence constraints to compute a lower bound and the Schrage's sequence as an upper bound. Then, we propose an improved lower bound which is based on an iterative procedure. Numerical experiments show the effectiveness of the bounds.

In this paper, we propose a new hierarchical method for the flexible job-shop scheduling problem (FJSP). This approach is mainly adapted to a job-shop problem (JSP) with high flexibility and is based on the decomposition of the problem in an assignment subproblem and a sequencing subproblem. For the first subproblem, we propose two methods: the first one is based successively on a heuristic approach and a local search; the second one, however, is based on a branch-and-bound algorithm. The quality of the assignment is evaluated by a lower bound. For the second subproblem we apply a hybrid genetic algorithm to deal with the sequencing problem. Computational tests are finally presented.

In this paper we consider the single machine scheduling problem with availability constraints in order to minimize the total completion times of jobs. We propose two exact approaches to solve the problem: a dynamic programming and a branch and bound method. The study of these approaches is carried out in this article and a concluding analysis based on several experimental results allows us to select the most suitable method according to the studied instance.

In this paper, we are interested in the multiobjective optimization of the schedule performance in the flexible job shops. The flexible job shop scheduling problem (FJSP) is known in the literature as one of the hardest combinatorial optimization problems and presents many objectives to be optimized. In this way, we aim to solve such a problem according to a set of some criteria, which characterize the feasible solutions of such a problem. The studied criteria are the following: the makespan, the workload of the critical machine, and the total workload of all the machines. Our study relates to the determination of a practical method using genetic algorithm in order to obtain the best performance of the production system. The solution performance is evaluated by comparing the values of the different values of the criteria with the corresponding lower bounds.

In this paper, we deal with the flexible job shop scheduling problem. We propose an efficient heuristic method for solving the assignment problem. Indeed, we propose a worst case analysis to evaluate the performance of such a heuristic. The second specificity of the problem studied is the sequencing property. Our approach consists in the application of an evolutionary algorithm based on a set of adapted operators to solve the sequencing step. Some lower bounds for the problem (previously proposed in Ref. 1) will be used in order to evaluate the quality of our method and the solutions according to the different criteria.

In our previous work (2002), we have proposed a Pareto-optimality approach for solving multiobjective optimization problems (MOPs) based on the hybridization of fuzzy logic and evolutionary algorithms (EAs). Such an approach makes it possible to construct a set of satisfactory solutions in order to provide flexibility to the decision-maker. In this work, we aim to enhance the suggested approach and propose a new variant of such a hybridization. Thereafter, we show how a uniform design can be used for finding a set of Pareto optimality solutions uniformly scattered. We briefly describe the Pareto-optimality concepts used for solving MOPs and those especially applied in EAs. Then, the mathematical formulation of FJSP is presented. The proposed hybrid approach is described. We illustrate the suggested approach by applying it to solving FJSP and highlights some practical aspects of the application of such an approach for solving hard combinatorial problems. Finally, we conclude with some future research directions.

Traditionally, assignment and scheduling decisions are made separately at different levels of the production management framework. The combining of such decisions presents additional complexity and new problems. We present two new approaches to solve jointly the assignment and job-shop scheduling problems (with total or partial flexibility). The first one is the approach by localization (AL). It makes it possible to solve the problem of resource allocation and build an ideal assignment model (assignments schemata). The second one is an evolutionary approach controlled by the assignment model (generated by the first approach). In such an approach, we apply advanced genetic manipulations in order to enhance the solution quality. We also explain some of the practical and theoretical considerations in the construction of a more robust encoding that will enable us to solve the flexible job-shop problem by applying the genetic algorithms (GAs). Two examples are presented to show the efficiency of the two suggested methodologies.

International audience

Traditionally, assignment and scheduling decisions are separately made at different levels of the production management framework. The combining of these decisions presents additional complexity and new problems. We present two approaches to solve the assignment and job-shop scheduling problems (with total or partial flexibility). The first one is the approach by localization : it makes it possible to solve the problem of resources allocation and build an ideal assignments model (assignments scheme). The second one is an evolutionary approach controlled by the assignments model (generated by the first approach). In this approach, we apply advanced genetic manipulations in order to enhanced solutions quality. We Also explain some of the practical and theoretical considerations to the construction of a more robust encoding that will allow us to consider the sequencing and the assignment problems jointly.