Technical Sessions A5 - E5

SESSION A5: Heuristics and Metaheuristics for Scheduling


[194] An Evolutionary Approach for Multi-Objective Optimization in Cyclic Hoist Scheduling Problem
Adnen El Amraoui and Khaled Mesghouni

In automated electroplating facilities, computer-controlled hoist is used to ensure the transport of jobs between tanks. Each job is mounted on a carrier and each carrier is immersed successively in several chemical baths, following a given processing sequence. The aim of this paper is to present an evolutionary approach to solve a multi-objective Cyclic Hoist Scheduling Problem (CHSP). The criteria which are considered here are to maximize the line production, by minimizing the cycle time; and to minimize the environmental waste in addition to energy consumption. Some experiments are carried out to show the reliability of this multi-objective approach.

[62] Simple constructive heuristics for the Distributed Assembly Permutation Flowshop Scheduling Problem with Sequence Dependent Setup Times
Sara Hatami, Ruben Ruiz and Carlos Andres Romano

As of late, there has been a growing interest in the scheduling literature on multi-factory scheduling. In this paper we consider a realistic production setting, referred to as the Distributed Assembly Permutation Flowshop Scheduling Problem or DAPFSP in short. As an extension of the recent work by [6], we add the additional consideration of sequence-dependent setup times (SDST) on both the distributed manufacturing stage as well as in the final assembly stage. The resulting problem is very close to the reality of multi-factory scheduling. In the DAPFSP the production is split into two stages: production and assembly. The first stage is composed of f identical flowshop production factories that produce the different jobs. In the assembly stage, all produced jobs are assembled into final products. The objective is to minimize the overall makespan. As this problem is known to be NP-hard, we propose two simple constructive heuristics to solve the problem. In this paper we detail the proposed heuristics and carry out a comprehensive computational.

[238] Optimization of Integrated Employee Timetabling and Hybrid Job Shop Scheduling under Time Lag Constraints
Mohamed Frihat, Chérif Sadfi and Atidel B. Hadj-Alouane

This paper studies two important problems, often encountered in the manufacturing industry in general and especially in the tanneries: human resources planning and production scheduling. In this work, we focus on the problem integrating Employee Timetabling [ETP] by considering their skills under various constraints and Hybrid Job-Shop scheduling [HJS] under time lags constraints. After presenting and formulating our problem as a Mixed Linear Program, we propose a resolution method based on decomposition and cuts generation by combining Mixed Linear Programming and Constraint Programming. Using numerical expermintations, we show the advantage of decomposition and cut generation, in terms of resolution time.

[220] A case study of a two-stage flow shop with dedicated machines and a single robot
Nacira Chikhi, Rachid Benmansour, Abdelghani Bekrar, Said Hanafi and Moncef Abbas

This paper considers a two-stage robotic flow shop scheduling problem. The objective is to minimize the makespan. The problem consists of two dedicated machines at the first stage and one common machine at the second stage. Each job is defined by two operations processed on the two-stages in series. Depending on its type, each job is executed on a dedicated machine at the first stage, then it is transported, by a robot or a conveyor, to be executed on the common machine at the second stage. We propose two mixed-integer program (MIP) models to solve this problem which is NP-Hard. These two models can be improved using valid inequalities based on three lower bounds. In addition, due to the NP-hardness of this case, a heuristic is developed to solve approximately large-size problems. The results indicate that the obtained solutions are of high quality and the corresponding CPU time is acceptable.

SESSION B5: POC : Polyhedra and Combinatorial Optimization


[123] Facets of order polytopes
Selim Rexhep, Samuel Fiorini and Jean-Paul Doignon

The order polytopes we consider here are the linear order polytope, the interval order polytope, the semiorder polytope and the partial order polytope. Among their known facet defining inequalities (FDIs), many have their coefficients in {-1, 0, 1}. We consider the problem of finding all of these particular FDIs. The problem is easy for the partial order polytope. For the interval order polytope, we prove that the solution consists of the so-called io-clique inequalities of Müller and Schulz [2]. We present a characterization of the {-1, 0, 1}-FDIs for the semiorder polytope. The similar problem for the linear order polytope remains open and seems harder to solve because of the large amount of FDIs which fall in this class.

[142] Branch-and-cut strategies for a multi-period network design and routing problem
Bernard Fortz and Dimitri Papadimitriou

The combined network design and (distributed) traffic routing problem can be formulated as a large-scale multiperiod mixed integer optimization problem. This problem combines network design decisions and routing decisions, with time-dependent traffic demands. In this paper, we consider different branch-and-cut strategies for solving the problem with the base and extended formulations proposed in our prior work.

[184] Bipartite Complete Matching Vertex Interdiction Problem: Application to Robust Nurse Assignment
Pierre Laroche, Sébastien Martin, Franc Marchetti and Zsuzsanna Róka

In this paper, we consider the Robust Nurse Assignment Problem. This consists in finding the maximum number of absences of qualified nurses still permitting an optimal treatment of patients, leading us to the notion of critical jobs. We introduce the Bipartite Complete Matching Vertex Interdiction Problem as the graph formulation of this problem. We show that it can be solved in polynomial time thanks to the integer polytope of an associated sub-problem. Then, we study the polytope associated with the Bipartite Complete Matching Vertex Interdiction Problem. We also extend the well-known Hall theorem to this problem.

[157] Polyhedral Study for the Maximum Bounded r-Tree Problem
Hervé Kerivin and Jinhua Zhao

Given an undirected graph G, a specific node r, and capacity on the nodes, the maximum bounded r-tree problem consists of finding a tree of G rooted at r containing as many nodes as possible with respect to the node capacities. This NP-hard optimization problem has been recently considered in the context of peer-to-peer networks. In this work, we study the associated polytope, in the space of edge variables. We introduced several family of facet-defining inequalities which lead to complete polyhedral descriptions of the polytope on trees and cycles. We also address their separation problems and present some computational results obtained by our branch-and-cut algorithm.

SESSION C5: Image, Image Processing


[107] Efficient Segmentation of Sub-Words within Handwritten Arabic Words
Faraz Khan, Ahmed Bouridane, Fouad Khelifi, Rasheed Almotaeryi and Sumaya Almaadeed

Segmentation is considered as a core step for any recognition or classification method and for the text within any document to be effectively recognized it must be segmented accurately. In this paper a text and writer independent algorithm for the segmentation of sub-words in Arabic words has been presented. The concept is based around the global binarization of an image at various thresholding levels. When each sub-word or Part of Arabic Word (PAW) within the image being investigated is processed at multiple threshold levels a cluster graph is obtained where each cluster represents the individual sub-words of that word. Once the clusters are obtained the task of segmentation is managed by simply selecting the respective cluster automatically which is achieved using the 95% confidence interval on the processed data generated by the accumulated graph. The presented algorithm was tested on 537 randomly selected words from the AHTID/MW database and the results showed that 95.3% of the sub-words or PAW were correctly segmented and extracted. The proposed method has shown considerable improvement over the projection profile method which is commonly used to segment sub-words or PAW.

[124] Minutiae Based Fingerprint Image Hashing
Rajesh Kumar Muthu, Ahmed Bouridane and Fouad Khelifi

This paper proposes a robust minutiae based fingerprint image hashing technique. The idea is to incorporate the orientation and descriptor in the minutiae of fingerprint images using SIFT-Harris feature points. A recent shape context based perceptual hashing method has been compared against the proposed technique. Experimentally, the proposed technique has been shown to deliver better robustness against image processing operations including JPEG lossy compression and geometric attacks such as rotation and translation.

[195] Handling uncertainties of models inputs in inverse problem: the U-discrete PSO approach
Dominique Barchiesi

The inverse problem of non constrained physical systems consists in finding the set of continuous inputs for its model that minimize fitness function measuring the distance between a target and the result of the model. However either the characterization of the sensitivity of model to each input or a preliminary knowledge on the uncertainties on parameters can reveal different required precision on each input. Therefore a blind search of the best set of parameters could be unnecessarily costing in terms of computational effort on the determination of non significative digits. To overcome this problem a solution consists in searching the best parameter sets within a predefined discrete space of search that is designed from the significative number of digits. The strategy consists in transforming the continuous problem into a discrete one that falls within combinatorial optimization eventually before ending the search of the best continuous inputs if required. The performance of continuous and discrete PSO are compared by their application to the inverse problem of the purple color of the Lycurgus cup. The structure of this ancient glass is recovered from photograph by using a direct model of color generation. The discussion of results is also an opportunity to convince that the heuristic approaches provide solutions to the inverse problem unlike nested loops, from a pedagogical point of view.

[223] Segmentation of Abnormal Cells by Using Level Set Model
Hawraa Haj-Hassan, Ahmad Chaddad, Camel Tanougast and Youssef Harkouss

Segmentation of image is used from a long time in medical image applications and its study is increased for enhanced the medical diagnosis. This paper concerns a deformable segmentation method for abnormal cells detection by using an improved Level set model which is solved several problems and disadvantages of others segmentation technique. Our approach employed by using real data of carcinoma cells obtained from optical microscopy. Preliminary simulation results showed high performance metrics of the proposed model. Comparative study with manual segmentation demonstrated and confirmed that the level set can be a promise model of abnormal cells detection and in a particularly an irregular shape like carcinoma cells type.

SESSION D5: Emotion Modelling and Recognition for Human Machine System


[41] Remarks on Fuzzy Reasoning-Based Brain Activity Recognition with a Compact Near Infrared Spectroscopy Device and Its Application to Robot Control Interface
Kazuhiko Takahashi, Syota Maekawa and Masafumi Hashimoto

This paper presents a method for recognizing the state of a user's brain activity by applying fuzzy reasoning to signals measured by a two-channel compact near-infrared spectroscopy (NIRS) device and investigates its feasibility and characteristics with regards to developing a compact brain-machine interface that utilizes NIRS. Distance-type fuzzy reasoning with membership functions of a singleton fuzzy number in the antecedent/consequence parts is applied to the oxyhaemoglobin concentration change obtained recorded by the compact NIRS device to recognize active and calm brain activity states. In the experiments in which subjects are assigned the tasks of reading silently to themselves, an average recognition rate of 64% can be achieved by the proposed method. As a practical application of the proposed method, experiments to control a robot arm using brain activity recognition result are conducted. Experimental results indicate that a recognition rate of 70% or higher can be achieved by utilizing a feedback interface that allows users to visually understand the state of their own brain activity even when a user is unfamiliar with the system.

[114] Negative emotion detection using EMG signal
Khadidja Gouizi, Fethi Bereksi and Choubeila Maaoui

Generally, Negative emotions can lead to health problems. In order to detect negative emotions, an advanced method of the EMG signal analysis is presented. Negative emotions of interest in this work are: fear, disgust and sadness. These emotions are induced with presentation of IAPS (International Affective Picture System) images. The EMG signal is chosen to extract a set of characteristic parameters to be used for classification of emotions. The analysis of EMG signal is performed using the wavelet transform technique to extract characteristic parameters while the classification is performed using the SVM (Separator Vector Machine) technique. The results show a good recognition rates using these characteristic parameters.

[153] Remote assessment of physiological parameters by non-contact technologies to quantify and detect mental stress states
Frédéric Bousefsaf, Choubeila Maaoui and Alain Pruski

We present and investigate, in the first part of this paper, a set of published works that may be employed to remotely quantify mental stress based on physiological signals by non-contact means. Several techniques can be used to this purpose, thermal imaging being currently the most advanced in our knowledge. Webcams correspond to a ubiquitous and to the most accessible techniques in the particular purpose of mental stress detection. After all these theoretical reminders, we present a pilot study based on a new framework that was developed to detect mental workload changes using video frames obtained from a low-cost webcam. To induce stress, we have employed a computerized Stroop color word test on twelve subjects. The results offer further support for the applicability of mental workload detection by remote and low-cost means, providing an alternative to conventional contact techniques.

[183] Optimization of an Electronic Nose for Rapid Quantitative Recognition
Mohamed Diaa Ahmadou, Losson Etienne, Maryam Siadat and Martine Lumbreras

This paper describes the optimization of an electronic nose (E-nose) equipped with metal-oxide gas sensors and dedicated to continuous concentration monitoring of volatile molecules. The optimization concerns particularly the selection of more appropriate characteristic features coupled with measurement conditions in order to minimize both the measurement time and the gas sensor drifts. First, a promising and fast feature corresponding to the maximum of the derivative curve of the sensor time-response is explored. The performance of this feature is demonstrated by comparison with a conventional steady-state feature, especially regarding its occurrence time, stability and sensitivity. Then the optimization of the measurement time (delay between two successive detections) has been illustrated and discussed. Optimized operating conditions and feature were finally validated by using non-supervised and supervised data mining analyses which show robust concentration discrimination. This optimization work constitutes an important step in real time applications for E-nose users.

SESSION E5: Identification and Control


[176] Contemporary Sinusoidal Disturbance Detection and Nano Parameters Identification Using Data Scaling Based on Recursive Least Squares Algorithms
Manuel Schimmack and Paolo Mercorelli

One-input single-output controlled autoregressive moving average system by using a scalar factor input-output data is considered. Through data scaling, a simple identification technique is obtained. Using input-output scaling factors a data Recursive Least Squares (RLS) method for estimating the parameters of a linear model and contemporary sinusoidal disturbance detection is deduced. For estimating parameters of a model in nano range a very high frequency input signal with a very small sampling rate is needed. The main contribution of this work consists of the use of a scaled Recursive Least Square with a forgetting factor. Using this proposed technique, a low input signal frequency and a wider sampling rate can be used to identify the parameters. In the meantime, the scaling technique reduces the effect of the external disturbance so that RLS can be applied to identify the disturbance without considering a model of it. The proposed technique is quite general and can be applied to any kind of linear systems. The simulation results indicate that the proposed algorithm is effective.

[180] Identification and observer synthesis of nonlinear systems using Laguerre multiple models
Ghassen Marouani, Abdelkader Mbarek, Tarek Garna and Hassani Messaoud

In this paper, we propose a new technique for identifying a non linear system using Laguerre multiple models. This model is characterized by a poles vector and a parameters vector. Then, this technique is composed by using a classical method to identifying the Fourier coefficients and a new optimization method to optimize the optimal poles. This method is based on the Newton Raphson algorithm. The model identified is used to synthesis a proportional observer for non linear systems.

[197] Tracking error estimation of uncertain Lur'e Postnikov systems
Amira Gharbi, Mohamed Benrejeb and Pierre Borne

This paper deals with an application of stability approach. In such a case, it is very important to able to estimate the maximum error induced by uncertainties and/or bounded perturbations. In this paper, is presented an approach which enables the estimation by overvaluation of this error between the evolution of Lur'e and Postnikov systems and of its model. It is based on the use of the aggregation techniques using vector norms and comparison systems.

[209] A New Approach on Angular Position Control of Fan and Plate System
Emre Dincel, Yaprak Yalçın and Salman Kurtulan

In this paper, a linear control technique based on a PID controller, which is the most used controller type in the industrial applications, is proposed for the angular position control of fan and plate system that has a nonlinear characteristic. Although the system is nonlinear, in the experimental studies, it is observed that for any small region in which the system can be considered as linear, the system (the linear model obtained around an operating point) has the same characteristic in the all operating regions. A new control approach is proposed by using this property of the system to guarantee the stability and operation without any overshoot.