Technical Sessions A7 - D7

SESSION A7: GOTHA: Applied Models for Scheduling Problems


[200] A branch and bound algorithm for one supplier and multiple heterogeneous customers to solve a coordinated scheduling problem
Hammoudan Zakaria, Olivier Grunder, Toufik Boudouh and Abdellah El Moudni

Considerable attention had previously been given to the single-vendor single-customer integrated inventory problem, but there had been very little work on the integrated single-vendor multi-customer and multi-product consideration. Here, we develop a generalized single-vendor multi-customer with multi-product consideration supply chain model with one transporter available to deliver the products from the supplier to the customers. The objective is to solve the proposed model and to find the minimized total cost, while guaranteeing a certain customer service level. A mathematical formulation of the problem is given in a general way. Then, we propose a branch and bound algorithm as an exact method and an efficient heuristic greedy algorithm. Both procedures are then compared through computational experiments which show that the heuristic algorithm is capable of generating near-optimal solutions within a short amount of CPU time.

[241] An effective iterative lower bound algorithm for the single machine scheduling problem with unavailability constraint and release date jobs and tails for maximum lateness minimization
Hfaiedh Walid, Chérif Sadfi, Kacem Imed and B. Hadj-Alouane Atidel

We consider the single machine scheduling problem with release date and delivery time jobs where the machine is unavailable during a known period, named hole. The problem is strongly NP-hard even in the case without unavailability period. We present in this paper a comparison study of an extension of Schrage algorithm as an upper bound and Jackson Preemptive Schedule as a lower bound. Then, we propose an improvement lower bound which is based on iterative procedure. Computational results are provided to show the efficiency of the approach.

[219] On the single-processor scheduling problem with time restrictions
Rachid Benmansour, Oliver Braun and Abdelhakim Artiba

This paper presents a time-indexed mixed integer programming formulation for the single-processor scheduling problem with time restrictions that has been formulated at first by Braun et al. in [1]. The problem is as follows. A set of n independent jobs are simultaneously available for processing at the beginning of the planning horizon, and their processing times are fixed and known in advance. The jobs have to be processed non-preemptively on a single processor that can handle only one job at a time. Furthermore, during any time period of length a > 0 the number of jobs being executed is less than or equal to a given integer value B >= 2. The objective is to minimize the completion time of the last job in the optimal sequence (i.e. the makespan). To our knowledge, this is the first time that a mathematical model is given to solve the single processor scheduling problem with time restrictions exactly. The performance of the model is tested by running it on randomly generated instances. The computational analysis shows that the proposed model, without any valid cuts, performs considerably well for small instances and a relatively large value of the integer B.

[213] A Bi-objective optimization model for single-machine batch scheduling considering energy cost
Junheng Cheng, Feng Chu, Weili Xia, Jianxun Ding and Xiang Ling

Electricity is one of most widely used energies and encouraged to be saved by scientific management and new technologies such as Time-of-Use policy. Batch scheduling can significantly improve production efficiency and is used in many high electricity consumption and high technology industries. This paper investigates a new bi-objective single machine batch scheduling problem with TOU policy. The first objective is to improve productivity and the second aims to minimize the total electricity cost. For the problem, a bi-objective mixed integer nonlinear programming model is formulated. Its corresponding single objective optimization problems are linearized by analyzed properties such that the multiobjective ε-constraint method can be used to obtain Pareto solutions.

SESSION B7: Control and Supervision


[38] Fault Detection in Nonlinear Systems using Genetic Algorithms and Principal Curves
Tawfik Najeh, Abdelkader Mbarek and Lotfi Nabli

This paper suggests a new approach for fault detection using Genetic Algorithms (GAs). GAs are used to find the principal curve that summarize the data. The principal curve is a generation of linear Principal Component Analysis (PCA) introduced by Hastie as a parametric curve. The existing principal curves methods employ the first component of the data as an initial estimation of principal curve that passes satisfactorily through the middle of data. However the needing of an initial line is the major inconvenient of this approach. In this work, we extend this problem in two ways. First, we introduce a new method based on GAs to find the principal curve. Second, potential application of principal curves in fault detection is proposed. An example is presented to prove the efficiency of the proposed algorithm to fault detection of nonlinear process.

[175] Multi-model Predictive Control Strategies for an Activated Sludge Model
Matoug Lamia and Khadir M. Tarek

This paper investigates the use of Model Predictive Control (MPC) and more precisely Generalized Predictive control (GPC) on an Activated Sludge Reactor. The reduced bio-reactor activated sludge ASM1 model, which describes the biological degradation of an activate sludge reactor, is designed based on several simplifications, as a Takagi Sugeno fuzzy model (TS). The TS model structure is based on a set of linear sub models, covering the process input-output space, interpolated by a nonlinear weighting function. In the case of the ASM1 model, as specified in this paper, the linear sub models turn out to be nonminimal phase, and therefore the system needs to be decoupled prior to design the control formulation. The classical Multi- Input Multi-Output (MIMO) GPC formulation is then modified to integrate the TS formulation as the controller internal model. Finally the performances under input constraints of the GPC controller are compared to a benchmark PID in terms of error and response dynamics.

[186] Trajectory closed loop control experiment for a two-link elastic manipulator in presence of load
M.H. Korayem, M. Doosthoseini, B. kadkhodaei Elyaderani, A.M. Shafei

Surveying behavior of a 2-link elastic robotic arm as a manipulator has been our purpose, so we have gathered all parts of an experimental set up and manufactured that robot and it’s interface as a combination of aluminum links, AC servo motor and its driver, DC motor, strain gauge sensors, high speed digital to analog convertor (DAC) components on an electrical interface board and National Instrument’s LABVIEW software package. In this paper we’ve focused on trajectory close loop control of robot end effector in presence of load with and without PID controller. Getting decrease in power consumption in industrial heavy robot and manipulation needs to getting lower the weight of the robot’s links, then it causes more deflection and vibration in end effector of robot. Hence eliminating the deflection and vibration of end effector trajectory is a substantial goal in robotic and control researches. Here we try to propose ideas for this problem and it works better if all offered theoretical ideas exam on an actual set up that we have prepared. For the first step a PID linear controller has been tested on experimental set up. Eventually it will caused that getting enhancement in some terms of PID will improve some deviations of the direction due to link’s vibrations. On the other hand increasing load on the robot end effector is caused to vibration intensification.

[154] A Piezo Servo Hydraulic Actuator for Use in Camless Combustion Engines and its Control with MPC
Benedikt Haus, Paolo Mercorelli and Nils Werner

In this paper a model of a hybrid actuator is proposed. It consists of a piezo-mechanical structure (including a hydraulic transmission ratio) and a hydraulic aggregate. Moreover, a cascade control strategy based on Model Predictive Control (MPC) is proposed to track periodic valve trajectory signals. The proposed cascade control structure consists of an internal and an external controller. The secondary, internal controller is needed to accomplish a Soft Landing. The MPCs are combined with two feed forward control actions, one for each part of the model. Simulation results carried out the suitability of the control approach.

SESSION C7: POC: Polyhedra and Combinatorial Optimization


[222] On minimal two-edge connected graphs
Denis Cornaz, Youcef Magnouche and Ali Ridha Mahjoub

Given G = (V, E) an undirected graph and a nonnegative cost function c : E → Q, the 2-edge connected spanning subgraph problem (TECSP for short) is to find a two-edge connected subgraph H = (V, F) of G with minimum cost. If c(e) > 0 for all e ∈ E then every optimal solution for TECSP is an inclusionwise minimal two-edge connected subgraph. In this paper we provide preliminary results, from a polyhedral point of view, concerning the inclusionwise minimal solutions of TECSP. We propose an ILP formulation for the problem and study the associated polytope for the wheels. Morever, we describe some valid inequalities and propose a branch-and-cut algorithm for the problem.

[231] On star forest polytope
Lamia Aoudia, Viet Hung Nguyen, Ali Ridha Mahjoub and Méziane Aider

A star forest of a graph G is spanning subgraph of G where each component is star. To each star forest in G, it corresponds a dominating set since the set of centers of stars defines a dominating set. In this paper we interest to complete description of star forest in some class of graphes then we give a complete description of SFP(G) when G is a cycle. We introduce new facet defining inequalities for SFP(G). We prove that these inequalities, called the matching cycle inequalities, can be separated in polynomial time. We also give a linear time algorithm for MWSFP when G is a cycle.

[31] Sharp Bounds on the Spectral Radius of Halin Graphs and Other k-Outerplanar Graphs
Patrick Healy

We provide upper and lower bounds on the spectral radius of Halin graphs and other k-outerplanar graphs. For both the Halin and k-outerplanar cases we provide examples where the bounds are met, thus demonstrating sharpness. The upper bound in the Halin case, improves upon Shu et al.'s claimed bound for a very wide class of graphs. A consequence of the upper bound is a generalization that holds for all graphs and which bounds the largest eigenvalue based on a graph partition; to the best of our knowledge this result is new also.

[170] Linear Index Coding via Graph Homomorphism
Javad B. Ebrahimi and Mahdi Jafari Siavoshani

The connection between linear index coding problem and graph homomorphism problem was previously investigated in [1], [2]. In [1], [3] it is shown that the minimum broadcast rate of a linear index code over a finite field Fq is equal to an algebraic invariant of the underlying digraph, called minrankq. In [4], it has been proven that for F2 and any positive integer k, minrankq(G) k if and only if there exists a homomorphism from the complement of the graph G to the complement of a particular undirected graph family called “graph family {Gk}”. As observed in [1], by combining these two results one can relate the linear index coding problem of undirected graphs to the graph homomorphism problem. In [2], a direct connection between linear index coding problem and graph homomorphism problem is introduced. In contrast to the former approach, the direct connection holds for digraphs as well and applies to any field size. More precisely, in [2], a graph family {H_q^k} has been introduced and shown that whether or not the scalar linear index of a digraph G is less than or equal to k is equivalent to the existence of a graph homomorphism from the complement of G to the complement of H_q^k. In this paper, we first study the structure of the digraphs H_q^k defined in [2]. Analogous to the result of [1] about undirected graphs, we prove that H_q^k’s are vertex transitive digraphs. Using this, and by applying a lemma of Hell and Nesetril [5], we derive a class of necessary conditions for digraphs G to satisfy lindq(G) k. Particularly, we obtain new lower bounds on lindq(G). Our next result is about the computational complexity of scalar linear index of a digraph. It is known that the deciding whether the scalar linear index of a undirected graph is equal to k or not is NP-complete for k 3 and is polynomially decidable for k = 1, 2 [4]. However, using the graph homomorphism framework, we show that this decision problem is NP-complete even for k = 2 if we consider digraphs.

SESSION D7: Renewal Energy and Power Systems


[164] Intelligent Decision Support for Renewable Energy Providers
Ioana Stanescu, Antoniu Stefan, Dumitru Stefan, Florin Dragomir, Nicolae Olariu and Otilia Dragomir

Renewable Energy Sources (RES) have evolved into an international success story. Even if, based on the policy and legislative support from the European Commission and national governments, the number of Renewable Energy Providers (REP) has increased substantially, RES are far from being readily usable. Numerous factors limit their efficiency. This paper discusses the emergence of supporting technologies that increase the performance of REP and present as a solution a cloud-based intelligent decision support and control system for low voltage power grids with distributed generation from RES.

[225] A Li-Ion cell testbench for fast Characterization and modeling
Lucas Cicero, Camel Tanougast, Harry Ramenah, Loic Sieler and Frederic Lecerf

To develop efficient Li-ion powered systems, Cell testing and charactering are required to evaluate cell performance. However, testbenches are really expensive and test procedures provided are not the ones expected. In this article, we propose a testbench design based on Instrumentation software and hardware co-design. A efficient charging and discharging hardware has been proposed and developed by using a remotable laboratory supply as main virtual component. Software mechanisms are explained where the test procedures are detailed. in a second part. Acquisition constraints for measuring equipment are also specified in order to obtain relevant and valid data.

[1] Synergy of Particle Swarm Optimization and Bacterial Foraging for Power System Stability Enhancement
Sahar Eldeep and Ehab Ali

A novel hybrid approach involving Particle Swarm Optimization (PSO) and Bacterial Foraging Optimization Algorithm (BFOA) called Bacterial Swarm Optimization (BSO) is illustrated for designing Static Var Compensator (SVC) in a multimachine power system. In BSO, the search directions of tumble behavior for each bacterium are oriented by the individual’s best location and the global best location of PSO. The proposed hybrid algorithm has been extensively compared with the original BFOA algorithm and the PSO algorithm. Simulation results have shown the validity of the proposed BSO in tuning SVC compared with BFOA and PSO. Moreover, the results are presented to demonstrate the effectiveness of the proposed controller to improve the power system stability over a wide range of loading conditions.

[182] Hybrid Petri Nets for Modeling and Control of Multi-source Energy Conversion Systems
Alexandre Sava, Kondo Hloindo Adjallah and Honoré Lagaza

This paper proposes an approach of hybrid Petri nets modeling of hybrid renewable energy production systems structured in micro-grids. This approach is original in the sense that it enables to study the behavior of such systems under various reconfiguration constraints in order to fulfill energy demands of customers. The proposed Petri net model allows to considering the discreet events related to the availability of energy sources or to components' failures in the system as well as the discreet reconfiguration (structural or functional), for control strategies specification. In addition, operational research model for cost minimization and availability maximization through reconfiguration is also proposed. The joint implementation of both models should lead to a new approach of design of hybrid renewable energy systems and of their effective cost optimization.