# SESSION A2: Operational Research and Applications

## [208] Traffic Control Model and
Algorithm Based on Decomposition of MDP

Biao Yin, Mahjoub Dridi and Abdellah El Moudni

In this paper, a new method based on decomposition of Markov Decision Process (MDP) for traffic control at isolated intersection is proposed. The conflicting traffic flows should be grouped into different combinations which can occupy the conflict zone concurrently. Thus, for purpose of traffic delay reduction, the optimal policy of signal sequence and duration among different combinations is studied by minimizing the number of vehicles waiting in the queue. In order to reduce the computation of probabilities in large state transition matrix, the decomposition method proposed classifies states into several parts as rule of traffic signal transition. Each part contains the vehicle states in all traffic flows. This method firstly achieves the full-states calculation in stochastic traffic control system. Moreover, the simulation results indicate that MDP approach is more efficient to improve the performance of traffic control than other comparing methods, such as fixed-time control and actuated control.

## [77] Traffic-aware Virtual Machine Placement in
Geographically Distributed Clouds

Hana Teyeb, Ali Balma, Nejib Ben Hadj-Alouane, Samir Tata
and Atidel B. Hadj-Alouane

In this work, we focus on the problem of virtual machines (VMs) placement in geographically distributed data centers, where tenants may require a set of networking VMs. The aim of the present work is to plan and optimize the placement of tenant’s VMs in a distributed Cloud environment while considering location and system performance constraints. Thus, we propose ILP formulations which have as objective the minimization of traffic generated by networking VMs and circulating on the backbone network. The different experiments conducted on the proposed formulations show the effectiveness of our model for large-scale Cloud systems in terms of running time and computational resources.

## [103] A mixed integer linear programming approach for a
new form of facility layout problem

Yipei Zhang and Ada Che

This paper aims to study a new form of facility layout problem, in which the building has already been constructed and the specific room layout inside has been determined. Unlike the traditional facility layout problem, what we take into account is how to assign a certain number of rooms to a given number of departments with the purpose of maximizing the utilization rate of the rooms. This is equivalent to minimizing the total difference value between the extra area of different departments after satisfying their required area, thus reducing the space waste. To solve this special combinatorial optimization problem, we develop a Mixed-Integer Linear Programming (MILP) model. The model is solved using commercial software CPLEX14.0. Computational results on several randomly generated instances demonstrate the effectiveness of the proposed approach.

## [85] Lagrangian relaxation for the permutation flowshop
scheduling problem with minimal and maximal time lags

Imen Hamdi and Taicir Loukil

In this research, we are interested in the permutation flowshop scheduling problem with minimal and maximal time lags while minimizing the total tardiness. The processing order of jobs is to be the same for each machine. The time lag is defined as the waiting time between two consecutive operations of each job. It is greater than or equal to a prescribed value called minimal time lag and smaller than or equal to a prescribed value called maximal time lag. A new mathematical formulation is proposed. Then, a new lower bound is derived by applying the Lagrangian relaxation. In order to make this technique a viable approach to the considered problem, an auxiliary formulation is adopted and the Lagrangian multipliers are updated using the subgradient algorithm. Then, results of the computational experiments are reported.