Marie-José Huguet

Pierre Lopez
email: lopez@laas.fr

Wafa Karoui
email: karoui.wafa@gmail.com

Weight-based heuristics for constraint satisfaction and combinatorial optimization problems

Keywords: Weight-based heuristics, tree search, constraint satisfaction, scheduling

In this paper, we propose mechanisms to improve instantiation heuristics by incorporating weighted factors on variables. The proposed weight-based heuristics are evaluated on several tree search methods such as chronological backtracking and discrepancy-based search for both constraint satisfaction and optimization problems. Experiments are carried out on random constraint satisfaction problems, car sequencing problems, and jobshop scheduling with time-lags, considering various parameter settings and variants of the methods. The results show that weighting mechanisms reduce the tree size and then speed up the solving time, especially for the discrepancy-based search method.

Introduction

This paper deals with the solving of combinatorial problems expressed in the Constraint Satisfaction Problem (CSP) formalism. A CSP is defined by a triple (X, D, C) where X = {X 1 , . . . , X n } is a finite set of variables, D = {D 1 , . . . , D n } is the set of domains for each variable, each D i being the set of discrete values for variable X i , and C = {C 1 , . . . , C m } is a set of constraints [START_REF] Dechter | Constraint Processing[END_REF][START_REF] Tsang | Foundations of Constraint Satisfaction[END_REF]. For optimization problems, an objective function f is added to the problem definition and we talk about a Constraint Satisfaction Optimization Problem (CSOP). An instantiation of a subset of variables corresponds to an assignment of these variables by a value taken from their domain. An instantiation is said to be complete when it concerns all the variables of X.

Otherwise, it is called a partial instantiation. A solution is a complete instantiation satisfying the constraints. An inconsistency in the problem is raised as soon as a partial instantiation cannot be extended to a complete one. For a CSOP, a solution s * is optimal if its cost f (s * ) is lower than or equal to the cost of all other solutions (for a minimization problem).

Following this definition, it is clear that CSPs can model a broad spectrum of decision problems, from satisfiability problems to optimization problems. Solving CSPs is a general research domain based on tree search methods embedding three main components: search tree expansion strategy, constraint propagation mechanisms, and variable/value ordering heuristics.

CSPs are known to be NP-complete problems and each component has a strong impact on the quality of the search method. CSPs appear in various domains and many search algorithms have been developed to solve them. In this paper, we are concerned with complete methods that have the advantage of finding at least a solution to a problem, if such a solution exists. A widely studied class of complete algorithms relies to depth first search and backtracking mechanisms.

More particularly, the purpose of this paper is to propose improving techniques for tree search. The method that we privileged here is discrepancy search, an alternative to depth first search (the principles and references are given in the next section on the scientific background).

We then propose to analyze the causes of failures in the search tree and derive variables weighting for ordering heuristics. In the first part of the paper, we use these techniques for constraint satisfaction problems, in particular randomly generated CSPs and car-sequencing instances.

A variant, named as YIELDS, of the seminal limited discrepancy search (LDS) method serves as a support for developing the search tree. In the second part, the techniques are adapted for handling combinatorial optimization problems. A climbing discrepancy search (CDS) variant with weighted factors is proposed for jobshop scheduling with time-lags. We selected this particular scheduling problem for its intrinsic genericity, as well as its practical relevance in the process industry.

The paper is organized as follows: The next section provides a brief overview and background on search methods and ordering heuristics. Section 3 describes a heuristic based on variable weighting and its integration in a discrepancy-based search method to solve different constraint satisfaction problems, namely random CSPs and car-sequencing benchmarks. Section 4 adapts the previous mechanisms for an optimization context (shop scheduling with makespan minimization). It reports computational results on jobshop scheduling problems with time-lags. The last section concludes this study and gives some ideas for further works in this area.

Background

In a tree search method, at each step, a partial solution is extended by assigning a value to an extra variable. When none of the values of a variable are consistent with the partial solution (dead-end), backtracking takes place. This kind of methods is usually stopped either as soon as a solution is obtained or when the complete tree has been explored. In the worst case, it needs an exponential time in the number of variables. Improvements of backtracking algorithm have focused on the three phases of the algorithm [START_REF] Dechter | Constraint Processing[END_REF]: ordering heuristics, moving forward (look-ahead schemes), and backtracking (look-back schemes). The most common principle for performing systematic search traverses the space of partial solutions in a depth-first manner.

Chronological Backtracking (CB) is a well-known method based on the depth-first search principle for solving combinatorial problems. The method CB extends a partial instantiation by assigning to a new variable a value, which is consistent with the previous instantiated variables.

When a dead-end appears, it goes back to the latest instantiated variable trying another value.

Forward-Checking (FC) and Arc-Consistency (AC) are two inference method types, which can be associated with (CB) (or any tree search methods), respectively denoted hereafter by CB-FC, and CB-AC a.k.a. MAC (Maintaining Arc-Consistency). For CB-FC, propagations are limited to variables in the neighborhood of the latest instantiation. MAC suppresses inconsistent values in the domain of all uninstantiated variables. Although CB-FC was considered as the best instantiation algorithm for a long time [START_REF] Sabin | Contradicting conventional wisdom in constraint satisfaction[END_REF], MAC is now recognized as one of the most performing existing method [START_REF] Zhang | Making AC-3 an optimal algorithm[END_REF].

Variable and value ordering heuristics may have a great impact for solving decision problems.

They were studied in many various fields like SAT, CSP, or combinatorial optimization [START_REF] Hooker | Logic-based Methods for Optimization: Combining Optimization and Constraint Satisfaction[END_REF][START_REF] Lecoutre | Using SAT encodings to derive CSP value ordering heuristics[END_REF].

They aim to provide an order on variables and values to speed up the search for obtaining a solution (possibly having good quality). The proposed order for the selection of the next variable or the next value for a variable instantiation can be static (i.e., the orders are definitively chosen at the beginning of the search) or dynamic (i.e., the orders may change during the search).

Variable and value ordering heuristics are generally based on opposite principles. Variable ordering heuristics exploit the fail-first principle [START_REF] Beck | Variable ordering heuristics show promise[END_REF][START_REF] Haralick | Increasing tree search efficiency for constraint satisfaction problems[END_REF]. It aims to reduce the tree size by selecting firstly most constrained variables, which can prune quickly some inconsistent branches.

On the contrary, value ordering heuristics commonly use the succeed-first principle for selecting values that can belong to a solution so as to restrict backtracks. Some generic (dynamic) variable ordering heuristics consider the concept of degree of a variable, defined as the number of constraints involving it. For example:

• dom/ddeg [START_REF] Bessière | MAC and combined heuristics: two reasons to forsake FC (and CBJ?) on hard problems[END_REF]: it selects first the variable having the minimal ratio between domain size and degree. The degree can be computed dynamically by the number of constraints linking a given variable to uninstantiate variables;

• dom/wdeg [START_REF] Boussemart | Boosting systematic search by weighting constraints[END_REF]: it selects first the variable having the minimal ratio between domain size and weighted degree. A weight factor is associated to each constraint. When a deadend occurs, the weight of inconsistent constraints is increased. For a given variable, its weighted degree (wdeg) is the sum of weights of constraints involving this variable and not yet instantiated variables.

The heuristic dom/wdeg was embedded into a MAC algorithm and has proved its efficiency on a large range of both random and real problems [START_REF] Boussemart | Boosting systematic search by weighting constraints[END_REF]. This method was improved by Grimes and Wallace [START_REF] Grimes | Learning from failure in constraint satisfaction search[END_REF] including restarts to the original method. The authors of MAC associated with dom/wdeg explain its efficiency by the fact that weights on constraints allow the search to be guided towards difficult parts of the problem and limit the redundancy during solving.

Another way to improve tree search methods was proposed with Last-Conflict (LC) analysis [START_REF] Lecoutre | Last conflict based reasoning[END_REF]. LC aims to backtrack on the variable having produced the last failure. For that purpose, this variable tends to be instantiated first whatever is the selection made by the ordering heuristics on variables. This analysis can be generalized to k last conflicts. The LC analysis has been proven to be efficient with classical ordering heuristics (such as dom/ddeg) but it is less interesting with heuristics using the weighted degree principle.

Limited Discrepancy Search (LDS) [START_REF] Harvey | Limited discrepancy search[END_REF] proposes an alternative way to backtrack when a dead-end occurs. Since a good value ordering heuristic cannot avoid bad guesses (i.e., choosing, for a given variable, a value that does not participate in any solution), LDS tackles this problem by gradually increasing the number of allowed discrepancies, where a discrepancy is associated with any decision point in a search tree when the choice goes against a value ordering heuristic. This method stops when a solution is found or when the maximum number of discrepancies is reached (in case of inconsistency).

Several variants of discrepancy-based methods were proposed. These methods differ by the manner discrepancies are applied: either first at the top of the search tree, or first at the end; and by the fact that redundancies are allowed or not during the search tree expansion. For instance, LDS applies discrepancies at the top first and has redundancy since a partial instantiation is visited more than once in successive iterations. Improved LDS (ILDS) [START_REF] Korf | Improved limited discrepancy search[END_REF] is a non-redundant variant applying discrepancy at the end first. Depth-bounded Discrepancy Search (DDS) [START_REF] Walsh | Depth-bounded discrepancy search[END_REF] first favors discrepancies at the top of the search tree authorizing the discrepancies only in the first levels of a given depth; it is non-redundant. Another variant is the method YIELDS [START_REF] Karoui | YIELDS: A yet improved limited discrepancy search for CSPs[END_REF], which is based on LDS and includes a mechanism to limit the exploration when the problem is inconsistent, even if the total number of discrepancies has not been used.

3 Weight-based heuristic for Constraint Satisfaction Problems

Variable weighting ordering heuristic

Let (X, D, C) be a binary CSP of n variables. W var (i) denotes the weight associated with each variable X i . The variable weight vector W var is the vector composed of weights of all variables of the problem:

W var = [W var (i)] n .
The proposed heuristic Wvar consists in associating a weight with each variable. This weight is increased whenever the corresponding variable is involved in a dead-end during search. The variable having the most important weight is selected for instantiation.

To illustrate this mechanism, we consider a CSP with three variables (X 0 , X 1 , X 2 ), all with domain {0,1,2,3,4}. The set of contraints C is represented by the following set of incompatible tuples:

{(X 0 , 0), (X 1 , 4)} ∪ {(X 0 , 0), (X 2 , 4)} ∪ {(X 0 , 1), (X 1 , 4)} ∪ {(X 0 , 1), (X 2 , 4)} ∪ {(X 0 , 2), (X 1 , 4)} ∪ {(X 0 , 2), (X 2 , 4)} ∪ {(X 0 , 3), (X 1 , 4)} ∪ {(X 0 , 3), (X 2 , 4)} ∪ {(X 0 , 4), (X 2 , 2)} ∪ {(X 0 , 4), (X 2 , 3)} ∪ {(X 1 , 0), (X 2 , 0)} ∪ {(X 1 , 0), (X 2 , 1)} ∪ {(X 1 , 0), (X 2 , 2)} ∪ {(X 1 , 0), (X 2 , 3)} ∪ {(X 1 , 1), (X 2 , 0)} ∪ {(X 1 , 1), (X 2 , 1)} ∪ {(X 1 , 1), (X 2 , 2)} ∪ {(X 1 , 1), (X 2 , 3)} ∪ {(X 1 , 2), (X 2 , 0)} ∪ {(X 1 , 2), (X 2 , 1)} ∪ {(X 1 , 2), (X 2 , 2)} ∪ {(X 1 , 2), (X 2 , 3)} ∪ {(X 1 , 3), (X 2 , 0)} ∪ {(X 1 , 3), (X 2 , 1)} ∪ {(X 1 , 3), (X 2 , 2)} ∪ {(X 1 , 3), (X 2 , 3)}.
In Figure 1, we represent the iterations of a discrepancy-based method using a weighting variable heuristic, for instance Wvar⊕Lexico, that is a heuristic based on vector W var and on the lexicographical order to break the ties. Table 1 gives the value of the weights of each variable after each iteration. Initially, W var (i) = 0, ∀i ∈ {0, 1, 2}. After iteration LDS(0) (i.e., the LDS method at hand with 0 discrepancy), W var (2) = 1 due to the dead-end on X 2 . The method then restarts with 1 discrepancy and a new ordering heuristic based on Wvar. Atfer iteration LDS(1), W var (1) = 3 due to three failures on X 1 . During the iteration LDS(2), based on the new ordering between variables, the method gets a solution.

1 LDS(1) LDS(2) LDS(0) : dead-end : solution X 0 X 1 X 2 X 2 X 0 X 1 X 0 X 2 X 1 0
W var (X 0 ) 0 0 W var (X 1 ) 0 +3
W var (X 2 ) +1 1

Integration in tree search methods

The heuristic presented previously can be grafted into tree search methods, such as discrepancy search or chronological backtracking. For discrepancy search and non-binary trees, two modes can be used to count discrepancies [START_REF] Gacias | Parallel machine scheduling with precedence constraints and setup times[END_REF][START_REF] Prcovic | Ensuring a relevant visiting order of the leaf nodes during a tree search[END_REF]. First, the binary way: exploring the branch associated with the best value, according to a value ordering heuristic, involves no discrepancy, while exploring the remaining branches implies a single discrepancy. Second, the non-binary way: the values are ranked according to a value ordering heuristic such that the best value has rank 1;

exploring the branch associated with a value of rank k > 1 leads to make k -1 discrepancies. In the following of this section, the heuristic is integrated into the YIELDS method proposed in [START_REF] Karoui | YIELDS: A yet improved limited discrepancy search for CSPs[END_REF] with a binary counting of discrepancies. In the YIELDS method, the Wvar_YIELDS_Probe algorithm (see Algorithm 1) is iterated either until a solution is found or until CurrentM axDiscr reached the maximum number of allowed discrepancies or until an inconsistency is detected.

Comparatively to the YIELDS_Probe algorithm, in Wvar_YIELDS_Probe the integration of the W var heuristic needs the function UpdateWeights to update weights of variables when a dead-end occurs; and the selection of a successor of a node (function Successors) is based on the variable weights.

Computational results

We propose to test the impact of the proposed variable weighting heuristic both in backtrack and in discrepancy search methods. The problems investigated in these experiments are car sequencing problems and random binary CSPs. The evaluation criteria are the number of expanded nodes and the CPU time. All algorithms were coded in C++. They were run on a Linux Fedora Core Duo 2.33 GHz PC having 4 Go of RAM.

Car sequencing problems

The car sequencing problem treats the placement of n cars in production on an assembly line that moves through various production units. Every production unit is responsible of installing on cars potential options like airbags, sunroofs, radios, etc. Each unit has a limited capacity (constraint of the form r cars out of s, i.e., the unit is able to produce at most r cars with a given option out of each sequence of s cars) and needs time to set up its associated option.

Every car does not require all options but leads to a class of cars, which correspond to a specific list of options. A solution of the decision variant of the car sequencing problem (considered in this paper) is to find an assignment of cars to the slot that satisfies both the demand and the capacity constraints, which is NP-complete [START_REF] Gent | Two results on car-sequencing problems[END_REF]. It was studied in many works [START_REF] Van Hentenryck | Constraint satisfaction using constraint logic programming[END_REF][START_REF] Van Hoeve | New filtering algorithms for combinations of among constraints[END_REF][START_REF] Régin | A filtering algorithm for global sequencing constraints[END_REF][START_REF] Smith | Succeed-first or fail-first: A case study in variable and value ordering heuristics[END_REF] and an optimization variant was considered in the 2005 ROADEF challenge [START_REF] Solnon | The car sequencing problem: Overview of state-of-the-art methods and industrial case-study of the ROADEF'05 challenge problem[END_REF]. To model this problem, we consider n class variables (one for each car), the domain of these variables is the set of car classes. We do not use any global constraint propagation among those proposed in [START_REF] Van Hoeve | New filtering algorithms for combinations of among constraints[END_REF] or in [START_REF] Régin | A filtering algorithm for global sequencing constraints[END_REF], but just FC propagation.

In these experiments, we consider the set of 70 satisfiable problems from the CSPLib [7] with a timeout of 200 seconds for each of them. We will compare chronological backtrack method vs. a discrepancy-based method following the various variable ordering heuristics proposed and using the same kind of constraint propagations (FC). Since the method YIELDS differs from the original method LDS by limiting the exploration for inconsistent problems (see Section 2), note that both methods are equivalent here because the instances under consideration are all satisfiable.

The first part of experiments consists in testing the impact of instantiation heuristics on CB and LDS with binary and non-binary counting modes. We then compare CB and each variant of LDS with two variable ordering heuristics: Lexico, which follows the lexicographical order, and Wvar⊕Lexico,which chooses the variable X i associated with the greatest weight W var (i) and, in case of ties, follows the lexicographical order. The value ordering is MaxOpt⊕Lexico which selects value corresponding to a car which requires the greatest number of options (MaxOpt) and, to break the ties, uses the lexicographical order. Table 2 presents for each method the number of solved problems out of 70 (#Solved), the average CPU time (CPU) in seconds and the average number of expanded nodes (NEN) to solve these problems. For each method, this table shows that the use of Wvar⊕Lexico as variable ordering improves the number of solved problems. This improvement is very weak for CB and comes along with a high increase in the average CPU time (4 times in more) and in the average number of expanded nodes (2.8 times in more). However, for binary and non-binary LDS, this improvement is more important (increasing the number of solved problems from 43% for binary LDS up to 71% for non-binary LDS) and leads to a reduction of the average number of expanded nodes (decreasing about 75% with binary LDS and for 42% for non-binary LDS). The CPU time increases very slightly with Wvar⊕Lexico in binary LDS (about 5%) and it decreases more importantly with Wvar⊕Lexico in non-binary LDS (about 19%). Globally, the LDS method with non-binary counting associated with the variable ordering Wvar⊕Lexico outperforms all the other methods. In [START_REF] Van Hoeve | New filtering algorithms for combinations of among constraints[END_REF], a global constraint called regular is proposed and compared to the global sequencing constraint (GSC) available in Ilog Solver. For the same set of considered experiments (instances called carseq10 ... carseq78 in [START_REF] Van Hoeve | New filtering algorithms for combinations of among constraints[END_REF]), 37 instances are solved using GSC and 39 using GSC combined with regular (with a timeout of 3600 seconds). In this paper, the ordering heuristics used are the best between dom and the slack heuristic proposed in [START_REF] Régin | A filtering algorithm for global sequencing constraints[END_REF]. With the proposed heuristic based on Wvar⊕Lexico, with just FC propagation, the best tree search method (Non-binary LDS) is clearly very well performing since it solved 65 instances.

Random binary CSPs

To obtain random binary CSPs, we used the model B generator developed by Frost et al. [START_REF] Frost | Random uniform CSP generators[END_REF].

According to [START_REF] Xu | Random constraint satisfaction: Easy generation of hard (satisfiable) instances[END_REF], we started from densities that permit to avoid flawed instances. We consider instances involving 30 and 40 variables having a uniform domain size of 25 and 20. The problem density (i.e., the ratio of the number of constraints involved in the constraint graph over that of all possible constraints), denoted by p 1 , varies. The constraint tightness (i.e., the ratio of the number of disallowed tuples over that of all possible tuples), denoted by p 2 , varies so that we obtain instances around the peak of complexity. In the last part of experiments, three variants of YIELDS are compared, depending on the way for discrepancy counting: binary, non-binary, and also mixed [START_REF] Gacias | Parallel machine scheduling with precedence constraints and setup times[END_REF]. For mixed counting we consider non-binary counting at the top and binary counting at the bottom, denoted by YIELDS-NB-B, and the opposite, named YIELDS-B-NB. To mix the two kinds of counting, we use the depth for partitioning the search tree and change the counting modes. We test various partitioning depths of 1/5, 1/3, and 2/3 (measured from the top). In Figure 5 Note that these results are not steady for other values of the depth, which remains open the right tuning for partitionning the search tree.

Discussion

Previous figures and tables show that for solving car-sequencing and random CSPs, non-binary variants of discrepancy-based methods are more efficient than binary variants or than MAC.

Moreover, for random CSPs, YIELDS-NB is less sensitive, than the other approaches, to the variations of parameter p 2 , i.e., the constraint tightness. This tends to assume that YIELDS-NB is a robust method.

In complement to the above presented results, we have conducted experiments on the performance of the mixed counting mode to solve car-sequencing instances. We tested various partitioning depths but none improved the results obtained with the non-binary version of YIELDS.

The interest of the mixed counting is thus still questionable for a discrepancy-based method.

Other weighting mechanisms were also tried. For instance, we have considered the integration of weighting values in both MAC and YIELDS methods. We tested three value ordering heuristics, each one being different from the other according to the mode to increment the weight of a value. However, the associated experiments did not produce valuable results.

Discrepancy and learning for jobshop problems with time-lags

This section addresses a combinatorial optimization problem: the jobshop scheduling problem with time-lags. A time-lag constraint is initially defined as a time-distance between the end of an operation and the start of another. This extension of classical shop scheduling problems (generally, they are already NP-hard in the strong sense) is of practical importance, as time-lag constraints appear frequently in industrial processes such as chemical plants, pharmaceutical, and food industry [START_REF] Neumann | Project Scheduling with Time Windows and Scarce Resources[END_REF].

Few methods have been used to solve this type of problems. Wikum et al. [START_REF] Wikum | One-machine generalized precedence constrained scheduling problems[END_REF] study singlemachine problems with minimum and/or maximum distances between jobs. The authors state that some particular single-machine problems with time-lags are polynomially solvable, even if the general case is NP-hard. Brucker et al. [START_REF] Brucker | A branch and bound algorithm for a single machine scheduling with positive and negative time-lags[END_REF] show that many scheduling problems (such as multi-processor tasks or multi-purpose machines) can be modeled as single-machine problems with time-lags and propose a branch-and-bound method. A local search approach can be found in [START_REF] Hurink | Local search algorithms for a single-machine scheduling problem with positive and negative time-lags[END_REF]. A memetic algorithm is proposed in [START_REF] Caumond | A memetic algorithm for the job-shop with time-lags[END_REF] and obtained good results on jobshop instances, especially for those with null minimum and maximum time-lags (named as "no-wait problems").

Branch-and-bound was proposed for single-machine problems with general time-lags [START_REF] Brucker | A branch and bound algorithm for a single machine scheduling with positive and negative time-lags[END_REF]. The problem is also studied in [START_REF] Artigues | Generalized disjunctive constraint propagation for solving the job shop problem with time lags[END_REF] by integrating generalized resource constraint propagation and branch-and-bound.

In this part, as in [START_REF] Artigues | Generalized disjunctive constraint propagation for solving the job shop problem with time lags[END_REF][START_REF] Caumond | A memetic algorithm for the job-shop with time-lags[END_REF], we only consider maximum time-lags between successive operations of the same job. In this case, a trivial schedule can be obtained by a greedy constructive algorithm.

It consists in considering the jobs one after the other, and, for each job, all its operations are scheduled at their earliest start time. The first operation of the next job starts at the end of the partial schedule. However, this trivial schedule is of poor performance for makespan minimization. The proposition of methods for solving the jobshop scheduling problem with maximum time-lags is then relevant, even for just finding a non-trivial feasible solution.

Problem modeling and initial solution

In the jobshop problem, a set J of n jobs have to be scheduled on a set of m machines. Each job J i corresponds to a linear sequence of n i operations. Each operation must be processed on a unique non-preemptive machine and each machine can process only one operation at a time.

Then, two operations that need the same machine cannot be processed at the same time. In Solving the JSPTL consists in sequencing all of the operations on the machines such that the resource sharing constraints are satisfied and such that consecutive operations of each job respect the time-lag constraints. The objective is to find a schedule that minimizes the makespan (min C max ).

Assume that i = 1, . . . , n are job indexes and j = 1, . . . , n i operation indexes for job i.

. (i, j) stands for the j th operation of job i,

. m i,j corresponds to the machine allocated to operation (i, j),

. p i,j is the duration of operation (i, j),

. t i,j represents the start time of operation (i, j),

. T L min i,j,j+1 and T L max i,j,j+1 correspond to the values of the minimum and maximum time lags, respectively, between operations (i, j) and (i, j + 1).

Constraints of the problem are mathematically formulated as follows:

C max ≥ t i,j + p i,j ∀i = 1, . . . , n , j = 1, . . . , n i , (1)
t i,j+1 ≥ t i,j + p i,j + T L min i,j,j+1 ∀i = 1, . . . , n , j = 1, . . . , n i-1 , (2)
t i,j+1 ≤ t i,j + p i,j + T L max i,j,j+1 ∀i = 1, . . . , n , j = 1, . . . , n i-1 , (3)
t i,j ≥ t k,l + p k,l or t k,l ≥ t i,j + p i,j ∀(i, j), (k, l) m i,j = m k,l , (4)
t i,j ≥ 0 ∀i = 1, . . . , n , j = 1, . . . , n i . (5)
Constraints (1) establish the end times of the operations. Constraints ( 2) and ( 3) represent the temporal constraints between two consecutive operations of the same job including minimum and maximum time lags, respectively. Constraints (4) correspond to the resource sharing: two operations competing for the same machine cannot be processed at the same time and must then be sequenced.

In our modeling, the set of variables X correspond to job selection variables. The variable X i is then the selection of the ith job to be scheduled on the machines. For each i ∈ [1, . . . , n],

the domain D i of each X i variable is {J 1 , . . . , J n }. Thus, the values of these variables must be all different. Once a job J i is selected, the n i operations of this job have to be scheduled on the machines by instantiating their start times from t i,1 to t i,n i such that both resource sharing and time-lag constraints are satisfied.

To solve the JSPTL under study, we use the job insertion heuristic proposed by [START_REF] Artigues | Generalized disjunctive constraint propagation for solving the job shop problem with time lags[END_REF]. It consists in selecting a job J i and in setting the start time of its first operation, t i,1 , to its earliest start time on the associated machine. Then, we go to the second operation and fix its start time t i,2 : if its earliest start time (for the required machine) does not match with the time-lag constraints associated with the first operation, we go back to the first operation and shift it to its next possibility. We proceed this way until we found a position where both operations are scheduled on the machines and the time-lag constraints are satisfied. We reiterate until all the operations of each job are scheduled. In the worst case, the jobs are scheduled in a single queue.

Weight-based heuristics for improving climbing discrepancy search

To solve problems with time-lags, we consider a variant of Climbing Discrepancy Search (CDS), a tree search method based on discrepancy devoted to optimization. CDS [START_REF] Milano | On the relation between complete and incomplete search: An informal discussion[END_REF] starts from an initial solution proposed by a given heuristic and tries to improve it by increasing step by step the number of discrepancies. It then builds a neighborhood around this initial solution. The leaves with a number of discrepancy equal to 1 are first explored, then those having a discrepancy number equal to 2, and so on. As soon as a leaf with an improved value of the objective function is found, the reference solution is updated, the number of discrepancy is reset to 0, and the process for exploring the neighborhood is restarted. To limit the search tree expansion, we fix a stop condition as a timeout on the CPU time.

We propose to integrate learning mechanisms based on weights in the CDS method. For the JSPTL, we then associate a weight W i with each job J i . During the search, if some operations of a given job J i cannot be scheduled at their earliest start time on the associated machine, W i is increased. In our problem, the weights {W j } j=1..n (initially equal for all j) can be increased in three ways:

• Increment per operation (Op): The job weight is increased every time one of its operations cannot be inserted in some slack period and then must be postponed until the next slack period. The number of moves is cumulated to give the increase in the job weight.

• Increment per machine (Mach): The job weight is increased every time one of its operations is not inserted in the first slack period on one of its associated machine. We increment the weight at most once per machine (or operation). The maximum factor to get on a considered operation is equal to the number of machines (or operations).

• Unary increment per job (Job): The job weight is increased every time one or more operations of this job are not placed in their first slack periods on the associated machine.

The weight is increased at most once for the same job.

In a given iteration of the CDS method, several branches are developed and a same job may have several weight increases. Thus, in addition of the manner to increase weights, we must choose a way to count them after a given iteration of the CDS method. We propose to consider either the sum of all weights obtained by the job during the incumbent iteration (denoted in the following by Sum), or the maximum of all its weights (denoted by Max ). In the next iterations of CDS, the weights obtained are integrated in the instantiation heuristic to select the job to be scheduled.

Moreover, in our experiments we consider various discrepancy positions in the CDS method (see Section 2): we test to diverge alternatively, first at the top of the search tree, or first at its bottom. We try also to diverge only in a part of the tree, for example at the top limited by a given depth, and to visit the other part without discrepancies at all. We use the binary

J 1 m 2 , 3 0, 1 m 1 , 5 0, 0 m 3 , 4 J 2 m 1 , 2 0, 1 m 2 , 8 0, 1 m 3 , 8
J 3 m 3 , 9 0, 0 m 1 , 5 0, 0 m 2 , 5
of discrepancies. The Gantt chart of Figure 6 depicts the solution obtained by the presented heuristic where the job selection is J 1 , J 2 , and then J 3 . This solution has a makespan of 39. The first one selects J 1 J 3 J 2 and leads to a makespan of 47, the second one selects J 2 J 1 J 3 with a makespan of 41. Figure 8 displays the Gantt charts of these two solutions.

J 1 J 3 J 3 J 3 J 3 J 3 J 3 39 47 41 J 1 J 2 Iteration 0 J 1 J 2 J 2 Iteration 1 Iteration 3 J 2 J 1 Iteration 2 J 3 J 1 J 2 39 23 41 23 23 J 1 J 1 J 2 J 2 J 3
Operations in dotted lines were shifted to respect both resource and time-lag constraints.

Table 4 gives the new weights for these jobs and the end of iteration 1 for the three ways of 4: Weights of jobs after iteration 1 according to three counting modes

W 1 W 2 W 3
Op Mach Job Op Mach Job Op Mach Job

J 1 J 2 J 3 - - - - - - - - - J 1 J 3 J 2 - - - 6 3 1 - - - J 2 J 1 J 3 - - - - - - 2 2 1
counting. At iteration 0, there is no shift on operations and the job weights are not modified.

At iteration 1, two sequences are then considered: J 1 J 3 J 2 and J 2 J 1 J 3 (see Figure 7). For the first sequence, i.e., when attempting to place J 1 then J 3 then J 2 , only operations of job J 2 are shifted to satisfy time-lag constraints (Figure 8). Therefore, job J 2 is the only job to increment its weight (column W 2 in Table 4). The same thing happens for job J 3 when searching for a solution with the order J 2 J 1 J 3 (column W 3 of the table). At the end of this iteration, J 2 has the highest priority, whatever the way for weight integration is (lexicographical order can be used to break the tie for mode Job), then J 3 and finally J 1 , and there is no improvement of the initial solution with one discrepancy. Therefore, the proposed CDS method restarts with two discrepancies and selects jobs with the new defined order: J 2 J 3 J 1 (iteration 2). The first solution produced by this iteration has a makespan of 23 (see Figure 9). This leads to a lower makespan than the current best solution. The search is then interrupted and restarts with this solution as the new reference solution and search for 1-discrepancy solutions (iteration 3).

Computational results

Our experiments were conducted on instances presented in [START_REF] Caumond | A memetic algorithm for the job-shop with time-lags[END_REF][START_REF] Lacomme | [END_REF]. These instances have been obtained from classical jobshop benchmarks where only maximum time-lags have been added (Lawrence's instances {laX} X=1..20 , and Fisher & Thompson's instances, f t06 and f t10). The maximum time-lags generated are associated with a coefficient α equal to 0, 0.25, 0.5, 1, 2, 3, 5, and 10 (note that, in the available instances, there are not all values of α for each instance).

Maximum time-lags are calculated for each job J i with these coefficients α and the durations {p ij } j=1..n i of the operations of the job.

To generate the initial solution, we tested different orders to sort the jobs. Considered orders are decreasing or increasing orders for job duration (D) or for job time-lags (TL); decreasing order of some combinations (D⊕TL and D/TL); lexicographical order (Lexico). The tests about the heuristic to generate the initial solution show that decreasing D gives the best results. Indeed in Table 5, one can observe the number of instances on which every heuristic is the best. It is also worth remarking that decreasing D⊕TL gives the same result (in bold). This is explained by the strong correlation between D and the value of the generated time-lags in these instances. For this first test, experiments concern a set of 126 instances (f t06, la01..la20) with only the values of α proposed by [START_REF] Caumond | A memetic algorithm for the job-shop with time-lags[END_REF]. There is a timeout of 200 seconds for the various CDS methods. For the second part of experiments, we tested many combinations of parameters: counting weights using cases Op, Mach, Job, or 0 if we do not use weights, and integrating weights after an iteration using Max or Sum. If weights are not used, the variant is named 0. A discrepancy may be applied at the top first or at the bottom first. In this experimental study, the case top-first always leads to better solutions. Surprisingly, the CDS method with no weights (0) is very well performing. It gives the best results (in bold) in average over all sets of instances but also over all Lawrence's instances.

Fisher & Thompson's instances are better solved with weighted variants of the method. For these weighted CDS methods, the counting modes based on Mach and Job outperform in average the Op mode. Actually, the method based on Mach generally beats that based on Op (values in italic). Thus, the variants 0, Mach-Sum and Mach-Max are retained in the sequel to go further in the experiments.

Then we tested a variant of the weighted CDS method with depth-bounded discrepancies (denoted by CDDS in [START_REF] Ben Hmida | Discrepancy search for the flexible job shop problem[END_REF]) to limit discrepancies at the top of the search tree. In Table 7 we give the results obtained for two depth limits (1/2 and 1/3) and the weighted mechanism is either Mach-Sum or Mach-Max. The comparisons are provided in terms of number of times each method obtained the best result and in terms of number of times each method improves the best-known value for the makespan (in parenthesis). For these experiments, we consider a set of 149 instances (f t06, f t10, la01..la20 with various values for α: 0, 0.25, 0.5, 1, 2, 3, 5, and 10) and the timeout of the CDS method is still limited to 200 seconds.

Table 7 shows that the benefit of weighted mechanisms is not steady for all variants. Indeed, including weights damages the results of CDS (columns 2 and 3 vs. column 1) while it improves the results for climbing depth-bounded discrepancy search (columns 2 and 3 of CDSS-1/2 and for some instances with tight time-lags (α generally lower than 1), that are hard instances.

Focusing on the instances improved by the weighted mechanisms, it is interesting to remark that the way for weight integration (Max or Sum) has practically no impact (there is little difference only for 'la12 -0.25' and 'la17 -0.25' instances). Considering all the variants, the results are very tight; the global improvement from BK is of about 6.3%. Furthermore, as previously discussed, the results also show the interest of combining both weighted mechanisms and bounds on discrepancies, since CDDS based on the counting mode Mach participates in improving two of the instances ('la12 -0.5' and 'la12 -1'), which had not been improved by other methods.

Finally, it is worth noticeable that our discrepancy-based search methods (without weights, however) improves two no-wait instances for which the memetic algorithm proposed in [START_REF] Caumond | A memetic algorithm for the job-shop with time-lags[END_REF] is generally the best performing.

Conclusion and further works

This paper presents various weighting mechanisms to improve instantiation heuristics, backtrack, and discrepancy search. These mechanisms are associated with different parameters to solve constraint satisfaction and combinatorial optimization problems.

In the satisfaction context, an experimental study was carried out on numerous binary CSPs and car sequencing benchmarks. The results showed that the proposed heuristic based on variable weighting is efficient for the studied tree search methods (based on chronological backtracking or on discrepancies). Furthermore, this study showed that variable ordering heuristics using weights on variables are the best suited heuristics when combined with discrepancy search;

especially with non-binary counting mode. Finally, non-binary discrepancy search outperforms others methods (binary discrepancy search or chronological backtracking) on these experiments.

The second part of this work addresses the jobshop scheduling problem with time-lags. To solve it, a variant of Climbing Discrepancy Search (CDS) using weighting mechanisms is proposed. We studied various parameter settings for the proposed method, such as discrepancy positions, heuristics to generate the initial solution, and learning mechanisms based on weights associated with jobs. The proposed variants were tested on known benchmarks from the literature. Tests show that the proposed methods help to improve the makespan for some jobshop instances and that the combination of weights and bounds for discrepancies is promising.

A natural extension of this work is to consider other weighting mechanisms for both variable and value ordering to better understand the impact of weights for both satisfaction and optimization problems. Another extension should be to realize a more substantial computational experience. Hence, we would aim to increase the size and the number of considered instances for car-sequencing, random CSPs, or jobshop with time-lags. Other objectives are to study the impact of the variable weighting principle on other known heuristics and to study the impact counting modes for satisfaction or optimization problems. Some work is also to be done for increasing the efficiency of CDS with weights for jobshop with time-lags. In particular, the interaction between heuristic and weights will be studied. Finally, the introduction of extended resource constraint propagation rules taking account of time-lag constraints and the integration of upper bounds during the search could greatly improve the efficiency.

Figure 1 :

 1 Figure 1: LDS search tree with the Wvar heuristic

Algorithm 1 :

 1 Wvar_YIELDS_Probe Data: node, (X, D, C), W var , CurrentM axDiscr Result: Sol begin if Goal(node) then return Sol else suc ← Successors(node, (X, D, C), W var ) if Failure(suc) then UpdateWeights(node, W var ) return NIL else if CurrentM axDiscr = 0 then return Wvar YIELDS Probe(First(suc), (X, D, C), W var , 0) else Sol ← Wvar YIELDS Probe(Second(suc), (X, D, C), W var , CurrentM axDiscr -1) if Sol = NIL then return Sol else UpdateWeights(suc, W var ) return Wvar YIELDS Probe(First(suc), (X, D, C), W var , CurrentM axDiscr) end Based on the same principle, LDS, YIELDS with non-binary counting of discrepancies, and CB can be adapted for the Wvar heuristic.

Figure 4 :

 4 Figure 4: Random CSPs: Comparison of two weighting heuristics in non-binary YIELDS

  the jobshop problem with time-lags (JSPTL) under study, time-lag constraints represent the distance between two operations belonging to the same job. The minimum distance (supposed to be positive or null) corresponds to the minimum time-lag and the maximum distance to the maximum time-lag. Maximum time-lags represent a specific difficulty since they can create many impossibilities for the operations insertion on the machines. A trivial schedule consisting in sequencing the entire jobs one after the other leads to poor makespan, and finding a non-trivial feasible solution remains a difficult issue. Problems containing only minimum time-lags are less difficult. In fact, minimum time-lags can be considered as a part of the previous operation. The difference is that the resource is available over the time-lag.

Figure 6 :

 6 Figure 6: Gantt chart of the initial solution (0 discrepancy)

Figure 7 :Figure 7

 77 Figure 7: Iterations of the CDS method

Figure 8 :

 8 Figure 8: Gantt charts of 1-discrepancy solutions

Figure 9 :

 9 Figure 9: Gantt chart for the new reference solution of iteration 2

Table 1 :

 1 Variable weighting

	W var	after LDS(0) after LDS(1)

Table 2 :

 2 Performance of CB vs. LDS (binary and non-binary variants) for car-sequencing instances

		VarOrder Lexico	Wvar⊕Lexico
		#Solved	36	37
	CB	CPU (s)	3.08	12.54
		NEN	700164	1995906
		#Solved	41	59
	Binary LDS	CPU (s)	9.87	10.42
		NEN	662301	165075
		#Solved	38	65
	Non-binary LDS	CPU (s)	11.81	9.61
		NEN	541359	314350

  The size of samples is 100 problem instances for each tuple (n, d, p 1 , p 2 ) where n is the number of variables and d the maximal domain size.The first part of experiments is devoted to testing the impact of two variable instantiation heuristics (dom/Wvar and dom/wdeg) on both CB and YIELDS methods using the same level of constraint propagation (arc-consistency). The arc-consistency is obtained by the powerful algorithm proposed by Zhang[START_REF] Zhang | Making AC-3 an optimal algorithm[END_REF]. In the following, CB with arc-consistency is named MAC, and YIELDS with arc-consistency is just denoted as YIELDS. For each method (MAC, YIELDS with binary and non-binary counting modes), we compute the standard deviation as follows: 100 * (dom/wdegdom/Wvar)/dom/wdeg. The value ordering heuristic is always minconflicts undergoing a succeed-first principle. Figure 2 compares the results obtained by MAC using the two variable ordering heuristics dom/Wvar and dom/wdeg. The left part of the figure entitled by '30-25-0.16' stands for CSPs of 30 variables, 25 values, and a density p 1 of 0.16. The right part of the figure, entitled by '40-20-0.8' stands for CSPs with 40 variables, domain sizes of 20, and a density p 1 of 0.8. The X-axis corresponds to several values of p 2 . The top of the figure gives the CPU time in milliseconds (CPU) for each method and the bottom of the figure gives the number of expanded nodes (NEN).This figure shows that MAC with the dom/Wvar variable ordering heuristic gives better results comparatively with dom/wdeg. For instances belonging to set 40-20-0.8, the CPU time is reduced by about 13.5% in average (from 9.1% to 23.1%) and the number of expanded nodes is reduced by about 11.3% (from 9.1% to 16.7%). For instances from the series 30-25-0.16, the CPU time is reduced by about 10.6% (from 9.1% to 14.3%) and the number of expanded nodes is reduced by about 9.7% (from 9.1% to 11.2%). In the next figures, the method MAC with dom/Wvar is retained for comparison. Figure 3 displays the results obtained by the method YIELDS with binary counting (denoted by YIELDS-B) for both variable ordering heuristics: dom/Wvar and dom/wdeg. Random CSPs: Comparison of two weighting heuristics in binary YIELDS The contribution of dom/Wvar towards YIELDS-B is less evident. Indeed, for the instances from 40-20-0.8, the heuristic dom/Wvar causes reduction of 27.1% for the CPU time and of 57.9% for the number of expanded nodes. However, for the instances from 30-25-0.16, NEN is still reduced (about 27.9%) but CPU is now increased (about 55.6%). Moreover, YIELDS-B with either dom/Wvar or dom/wdeg never improves MAC with dom/Wvar both on CPU and NEN for instances 40-20-0.8. It is just profitable in NEN for instances from 30-25-0.16.Figure 4 reports the results obtained by the method YIELDS with non-binary counting (denoted by YIELDS-NB) for both variable ordering heuristics: dom/Wvar, and dom/wdeg, and compares these methods to MAC with dom/Wvar. YIELDS-NB with dom/Wvar clearly outperforms YIELDS-NB with dom/wdeg. In average, for instances from 40-20-0.8, the CPU time is improved by about 46.4% and the NEN is improved by about 13.5%. For the instances from 30-25-0.16, the CPU time is improved by about 34.1% and the NEN by about 21.1%. Moreover, YIELDS-NB with dom/Wvar or dom/wdeg always improves MAC with dom/Wvar in both CPU time and NEN. For the proposed weighted heuristic dom/Wvar, we evaluate the average standard deviation between MAC and YIELDS-NB: 100 * (MAC -YIELDS-NB)/MAC. For CPU, the improvement of YIELDS-NB is around 80.2% and 78.9% for instances 40-20-0.8 and 30-25-0.16, respectively; for NEN this improvement is of 50.9% and 77.1%.

								30Ͳ25Ͳ0.16						40Ͳ20Ͳ0.08
			1800															10000
			1600 1400												YIELDSͲBͲdom/Wvar YIELDSͲBͲdom/wdeg MacͲdom/Wvar	7000 9000 8000	YIELDSͲBͲdom/Wvar YIELDSͲBͲdom/wdeg MACͲdom/Wvar
			1200															6000
	CPU(ms)	800 1000 1800 1800					30Ͳ25Ͳ0.16 30Ͳ25Ͳ0.16						3000 4000 5000 4000 CPU(ms) 4000	40Ͳ20Ͳ0.08 40Ͳ20Ͳ0.08
			600 1600 1600											YIELDSͲNBͲdom/Wvar YIELDSͲNBͲdom/Wvar	2000 3500 3500	YIELDSͲNBͲdom/Wvar YIELDSͲNBͲdom/Wvar
			2000 2000 1200 1200 200 400 1400 1400					30Ͳ25Ͳ0.16 30Ͳ25Ͳ0.16		YIELDSͲNBͲdom/wdeg YIELDSͲNBͲdom/wdeg MacͲdom/Wvar MacͲdom/Wvar	5000 5000 2500 2500 0 1000 3000 3000	40Ͳ20Ͳ0.08 40Ͳ20Ͳ0.08	YIELDSͲNBͲdom/wdeg YIELDSͲNBͲdom/wdeg MacͲdom/Wvar MacͲdom/Wvar
	CPU(ms) CPU(ms)		1600 1800 1600 1800 0 800 1000 800 1000	.47	.475	.477	.479	.48		.485	p2	.49	.492	.493	MacͲdom/Wvar MacͲdom/wdeg MacͲdom/Wvar MacͲdom/wdeg .494 .495 .5	CPU(ms) CPU(ms)	4000 4500 1500 1500 4000 4500 2000 2000	p2	MacͲdom/Wvar MacͲdom/wdeg MacͲdom/Wvar MacͲdom/wdeg
			1400 1400 600 600															3500 3500
	NEN	0 200 400 600 800 1000 1200 10000000 .47 0 200 400 600 800 1000 1200 .47 16000000 16000000 200 400 200 400 4000000 5000000 6000000 7000000 8000000 9000000 10000000 0 2000000 4000000 6000000 8000000 10000000 12000000 14000000 0 .47 9000000 CPU(ms) CPU(ms) NEN NEN 0 .47 0 1000000 2000000 3000000 4000000 5000000 6000000 7000000 8000000 9000000 .47 .47 .475 .475 .475 .475 .477 .477 .477 .477 .479 .479 .479 .479 .475 .477 .479 .475 .477 .479 Figure 3: 0 .48 .485 .49 .492 .493 .494 .495 .5 p2 30Ͳ25Ͳ0.16 500 0 1000 1500 2000 2500 3000 CPU(ms) 300000000 .48 .485 .49 .492 .493 .494 .495 .5 2500 3000 CPU(ms) 1,6E+09 30Ͳ25Ͳ0.16 1,6E+09 1000 1000 30Ͳ25Ͳ0.16 YIELDSͲBͲdom/Wvar 500 500 p2 30Ͳ25Ͳ0.16 MacͲdom/Wvar MacͲdom/wdeg 0 500 1000 1500 2000 100000000 150000000 200000000 250000000 300000000 NEN 0 200000000 400000000 600000000 800000000 1E+09 1,2E+09 1,4E+09 NEN .48 .485 .49 .492 .493 .494 .495 .5 p2 YIELDSͲBͲdom/wdeg MacͲdom/Wvar 250000000 .48 .485 .49 .492 .493 .494 .495 .5 p2 30Ͳ25Ͳ0.16 YIELDS NB d /W 0 0 50000000 100000000 150000000 250000000 NEN .48 .485 .49 .492 .493 .494 .495 .5 p2 .48 .485 .49 .492 .493 .494 .495 .5 30Ͳ25Ͳ0.16 YIELDSͲNBͲdom/Wvar YIELDSͲNBͲdom/wdeg 200000000 MacͲdom/Wvar	p2 40Ͳ20Ͳ0.08 40Ͳ20Ͳ0.08 40Ͳ20Ͳ0.08 p2 40Ͳ20Ͳ0.08 p2 p2 40Ͳ20Ͳ0.08 p2 40Ͳ20Ͳ0.08	YIELDSͲBͲdom/Wvar MacͲdom/Wvar MacͲdom/wdeg YIELDSͲBͲdom/wdeg MACͲdom/Wvar YIELDSͲNBͲdom/Wvar MacͲdom/Wvar YIELDSͲNBͲdom/wdeg
			3000000
			2000000							p2							50000000	p2
			1000000														0
				0
					.47	.475	.477	.479	.48	.485	.49	.492	.493	.494	.495	.5
											p2						p2
					Figure 2: Random CSPs: Comparison of two weighting heuristics in MAC

  , we compare the results obtained by YIELDS-B, YIELDS-NB, and a mixed counting mode with depth equals 1/5, denoted by YIELDS-NB-B-1/5.

						30Ͳ25Ͳ0.16 30Ͳ25Ͳ0.16					40Ͳ20Ͳ0.08 40Ͳ20Ͳ0.08
		1600 1600											9000 9000
		1400 1400								YIELDSͲBͲdom/Wvar YIELDSͲNBͲdom/Wvar YIELDSͲBͲdom/Wvar YIELDSͲNBͲdom/Wvar	8000 8000	YIELDSͲBͲdom/Wvar YIELDSͲNBͲdom/Wvar YIELDSͲBͲdom/Wvar YIELDSͲNBͲdom/Wvar
		1200 1200								YIELDSͲNBͲBͲ1/5Ͳdom/Wvar YIELDSͲNBͲBͲ1/5Ͳdom/Wvar	7000 7000	YIELDSͲNBͲNͲ1/5Ͳdom/Wvar YIELDSͲNBͲNͲ1/5Ͳdom/Wvar
													6000 6000
		1000 1000
	CPU(ms) CPU(ms)	800 800											CPU(ms) CPU(ms)	4000 5000 4000 5000
		600 600											3000 3000
													2000 2000
		400 400
													1000 1000
		200 200
													0 0
		0 0
		.47 .47	.475 .475	.477 .477	.479 .479	.48 .48	.485 .485	.49 .49	.492 .492	.493 .493	.494 .494	.495 .495	.5 .5
							p2 p2						p2 p2
						30Ͳ25Ͳ0.16 30Ͳ25Ͳ0.16					40Ͳ20Ͳ0.08 40Ͳ20Ͳ0.08
		14000000 14000000											500000000 500000000
										YIELDSͲBͲdom/Wvar	450000000	YIELDSͲBͲdom/Wvar
		12000000								YIELDSͲNBͲdom/Wvar	400000000	YIELDSͲNBͲdom/Wvar
										YIELDSͲNBͲBͲ1/5Ͳdom/Wvar	YIELDSͲNBͲNͲ1/5Ͳdom/Wvar
		10000000											350000000
													300000000
	NEN	8000000											NEN	250000000
		6000000											200000000
													150000000
		4000000											100000000
													50000000
		2000000
													0
		0
		.47	.475	.477	.479	.48	.485	.49	.492	.493	.494	.495	.5
							p2						p2
	and around 78.1% for instances 30-25-0.16. Concerning NEN, this improvement is about 79.5%
	and 86.4% for instances 40-20-0.8 and 30-25-0.16, respectively. Furthermore, YIELDS-NB-B-
	1/5 again improves YIELDS-NB. The CPU time is improved by about 63.5% and 45.1% and NEN
	is improved by about 69.9% and 57.3% for instances 40-20-0.8 and 30-25-0.16, respectively.

Figure 5: Random CSPs: YIELDS with mixed counting This figure shows that YIELDS-NB drastically improves YIELDS-B. In terms of average standard deviation, the improvement of YIELDS-NB is around 90.1% in CPU for instances 40-20-0.8

Table 3 :

 3 Example of jobshop problem with time-lags

	J i	O i1	time-lags (min, max) O i2	time-lags (min, max) O i3

Table 5 :

 5 Comparison of heuristics to generate an initial solution (number of best solutions)

	Order	D	TL D⊕TL D/TL Lexico
	Decreasing 55 51	55	29	20
	Increasing	5	12	5	22

Table 6 :

 6 Table 6 then compares several parameter settings for the CDS method, considering that top-first strategy is always selected to do discrepancies. It gives the number of times each combination of parameters obtained the best result for each given set of instances. We consider in these experiments the same set of 126 instances and the timeout of the CDS method is still limited to 200 seconds. Comparison of proposed CDS variants (number of best solutions)

	Variant	ft06 la01-05 la06-10 la11-15 la16-20 Total
	0	1	21	19	19	16	76
	Op-Sum	5	6	3	4	6	24
	Op-Max	2	4	1	5	6	18
	Mach-Sum	3	6	5	5	8	27
	Mach-Max	5	8	0	7	7	27
	Job-Sum	3	8	0	6	7	24
	Job-Max	3	10	1	6	7	27

Table 7 :

 7 Comparison of variants with depth-bounded discrepancies (number of best solutions and number of benefits)

		CDS			CDDS-1/2			CDDS-1/3
	0	Mach-Sum	Mach-Max	0	Mach-Sum	Mach-Max	0	Mach-Sum	Mach-Max

Table 8

 8 illustrates that discrepancy search (CDS and CDDS methods) improves the results

discrepancy counting (it was experimentally proved better than the non-binary mode for the problem under study): the heuristic choice corresponds to 0 discrepancy, all the other choices correspond to one discrepancy. Algorithm 2 summarizes the proposed improved CDS method principle. This algorithm is the same than CDS algorithm except in Line 6 where various parameter settings (in bold characters) offer several choices. Div pos denotes the discrepancy position chosen to diverge first: either first at the top or first at the bottom. W Increment denotes the case chosen to increment the discrepancies (Op, Mach, Job, or 0 when no weights are associated with the jobs). W integration denotes the mode for weight integration after a given iteration (Max or Sum).

Algorithm 2: Improved_CDS_Probe

Data: X, D, C % Variables, Domains of values, and Constraints Result: Sol begin % k is the discrepancy number ;

Example

We consider a jobshop with three jobs J 1 , J 2 , and J 3 , and three machines m 1 , m 2 , and m 3 .

Every job has three operations. Table 3 gives the associated machine and duration for each operation of each job and the time-lag constraints between each pair of consecutive operations.

For the solving method CDS with weighted values, we consider, in this example, the lexicographical order for the job selection and, for the sake of simplicity, we use a non-binary counting 19 [START_REF] Artigues | Generalized disjunctive constraint propagation for solving the job shop problem with time lags[END_REF] 16 (0) Total 90 ( 13) 57 ( 11) 63 ( 10) 52 ( 12) 67 ( 13) 93 ( 12) 49 ( 12) 90 ( 13) 90 ( 12)

CDDS-1/3 vs. their respective column 1). Table 7 also illustrates that the CDS method with weighted mechanisms is more efficient when the depth in the tree for doing discrepancies is bounded (columns 2 and 3 of CDDS-1/2 and CDDS-1/3 vs. columns 2 and 3 of CDS). Conversely, CDS without weights does not take benefit from this bound on discrepancies (column 1 of all variants). In terms of deviation on the makespan (not presented in the table), the results are quite similar since it is about 1.16 for CDS without weights and no limit on discrepancies, about 1.19 for CDS without weights and when discrepancies are bounded, and about 1.17 for CDS with weights and whatever the limit on discrepancies is.

Considering that CDDS with weighted mechanisms obtains the overall greatest number of best solutions and almost the greatest number of improvements (93 [START_REF] Grimes | Learning from failure in constraint satisfaction search[END_REF] for CDSS-1/2 and Mach-Max ), we can conclude that using a weight-based heuristics is a promising approach to solve the JSPTL.

In the last part of experiments, we compare for all the 149 instances the proposed methods with the best-known results provided either by the memetic algorithm of [START_REF] Caumond | A memetic algorithm for the job-shop with time-lags[END_REF] or by ILOG-Scheduler. For the 17 instances referred in Table 8 (instance name associated with its maximum time-lag), our methods found some improvements of the best-known results. In column 'BK', ILOG-Scheduler provides the best results for all the instances except for the two last no-wait instances ('la18 -0' and 'la19 -0') where the memetic algorithm is the best approach. On these instances, the CDDS methods with a depth limit of 1/2 or 1/3 obtain the same results; thus, we only report one on these results. In bold, we note the best obtained value on the makespan for a

given instance over all the methods; the makespan is in italic if it corresponds to an improvement of the previous best-known results.


Ahmed Akl
email: aakl@laas.fr

Thierry Gayraud
email: gayraud@laas.fr

Pascal Berthou
email: berthou@laas.fr

Investigating Several Wireless Technologies to Build a Heteregeneous Network for the In-Flight Entertainment System Inside an Aircraft Cabin

Keywords: IFE system, WLAN, WUSB, PLC networks I

A primary difficulty when investigating communication requirements in an aircraft cabin is the diverse needs of passengers when compared to the strict constraints inside the cabin. It is recognized that there is an increasing need of passengers to use their electronic devices as well as the need for entertaining during the flight. This paper aims at integrating heterogeneous available communication technologies, showing their pros and cons -within this contextwhile considering the imposed communication restrictions inside the aircraft's cabin.

INTRODUCTION

In recent years, market surveys have revealed a surprising and growing trend in the importance of In-Flight Entertainment (IFE) with regard to choice of airline. With modern long range aircraft the need for "stop-over" has been reduced, so the duration of flights has also been increased. Air flights, especially long distance, may expose passengers (PAX) to discomfort and even stress. IFE can provide stress reduction entertainment services to the passenger. The IFE system is an approach that can utilize the wireless technology for the purpose of exchanging data -in both directions-between PAX and the entertainment system. It can be also used to improve the passenger's service satisfaction level.

As stated by Niebla [START_REF] Niebla | Coverage and capacity planning for aircraft in-cabin wireless heterogeneous networks[END_REF] users are becoming more and more familiar to personal equipments, such as mobile phones, laptops, and PDAs. This shows the importance of providing aircrafts with facilities that support these equipments.

In addition, usage of the wireless technology will help in decreasing the connecting wires; this is a valuable criterion in aircrafts designing. However, using off-shelf technologies inside the cabin is usually not applicable when using them in the usual manner; the environment inside the cabin has very strict constrains since safety is a major requirement. Consequently, using just one technology can't be the optimum solution. In fact, using a combination of different technologies can provide a better service while overcoming the existing constrains. How to allow PAX to use their Personal Electronic Devices (PED) (i.e., mobile phones, laptop, etc.) was usually done through specialized devices [START_REF] Niebla | Coverage and capacity planning for aircraft in-cabin wireless heterogeneous networks[END_REF] [START_REF] Jahn | Evolution of aeronautical communications for personal and multimedia services[END_REF]. Nevertheless, there is no current research to use a combination of off-shelf technologies inside the cabin.

In the next section we will introduce an overview for an IFE system showing its components and requirements.

Section III introduces the communication challenges that face the IFE systems. Section IV shows the proposed available technologies that can be used to overcome the challenges in such environment. Section V introduces our approach for integrating them together.

II. BACKGROUND AND RELEVANT WORK

The recognized economics of wireless networks and communications systems have made them an attractive target for environments where individual wires are cumbersome. An airplane cabin is such an environment. Dwayne [START_REF] Folden | An Aircraft Cabin Wireless System for Games and Video Entertainment[END_REF] said that due to the need of rapidly reconfiguring the cabin's seating, it is further assumed that wireless networking, rather than cable or fiber optics, must be used to interconnect passenger's entertainment equipment with other elements of the system.

The use of wireless communication technologies on board of an aircraft provides an opportunity to remove wiring and save weight on the aircraft. The weight savings can be directly measured in terms of fuel savings and improved operating economics over the life time of an aircraft. However, there is a need to ensure that there is no interference with the aircraft's communication and navigation systems.

A. The need for IFE systems

Hao [START_REF] Liu | In-Flight Entertainment System: State of the Art and Research Directions[END_REF] mentioned that the enclosed environment of the aircraft can cause discomfort or even problems to PAX. IFE systems can greatly reduce these negative effects. This can be done by using e-books, video/audio broadcasting, games, internet, and On Demand services. The fact that the PAX come from highly heterogeneous pools (such as age, gender, ethnicity, etc…) causes an impact on the adaptive interface systems.

As mentioned by Fariba [START_REF] Alamdari | Airline in-flight entertainment: the passengers' perspective[END_REF], the IFE systems usually include screen-based, audio and communication systems. The screen-based products include video systems enabling PAX to watch movies, news and sports. These systems had progressed into video-on-demand, allowing PAX to have control when they watch movie. Air map display is another service that allows PAX to locate their flight's route. Exterior-view cameras also enable PAX to have the pilot's forward view on take-off and landing on their personal TV screens. Audio systems include different types of music channels and special programs recorded for the airlines. Communication systems include intra-communications with devices such as telephones, facsimile and in-seat power supplies, and inter-communications between the screenbased system and its subsystems (i.e., remote control).

B. The IFE system's components

In fact, the entertainment starts from the passenger's seat design where most of the IFE system components are embedded. Wiring cables connect together all of the electronic devices in the seat as well as connecting them to the whole system in the cabin. They run through the cabin's walls, floor, and seats. Unfortunately, conveying signals and power to the seats with a connector for each seat would cause reliability and maintenance problems, and hinder timely cabin reconfiguration.

Nowadays, IFE systems are interactive systems, so a Passenger Control Unit (PCU) is usually needed to control the surrounding devices. The PCU should be compact and easily held. Moreover, the pocket holding the PCU has to be placed in a way that makes it easily reached and not to affect the passenger's comfort.

A Seat Electronic Box (SEB) can be used to connect the system's different components together. It is used to connect the passenger's devices and the IFE system instead of having a separate channel for each signal. For example, to transmit communication and video signals, two different networks should be available if the SEB is not used. When using the SEB, the communication and video devices are connected directly to it to convey signals to the rest of the IFE system through one single network. Then, it simplifies and facilitates maintenance procedure since malfunctioning devices can be easily replaced without affecting the IFE connections.

Halid [START_REF] Hrasnica | Broadband Powerline Communications Networks[END_REF] stated that PLCs can provide a way of communication through power lines networks. Power lines and communication networks have different physical characteristics, so a PLC modem must be used as an interface between the two networks. They must be designed to provide accepted network operation under typical power lines transmission conditions. However, power lines are not designed as a good transmission media. It suffers from attenuation, fading, and noise. Nevertheless, the great advances in digital signal processing, error detection and correction, modulation, media access control techniques encourage the use of PLC in communication field.

III. COMMUNICATION CHALLENGES

Although aircraft security may be seen as another burden due to its very strict requirements, but it is mandatory to be included during the design of communication and data services. A major concern for using wireless devices in aircraft cabin is their interference with the aircraft's communication and navigation system, especially unintended interference from PAX's Personal Electronic Devices (PED). Holzbock [START_REF] Holzbock | Advances of aeronautical communications in the EU framework[END_REF] said that the installed navigation and communication systems on the aircraft are designed to be sensitive to electromagnetic signals, so they can be protected against PAX's emitters by means of frequency separation. In addition, Jahn [START_REF] Jahn | Evolution of aeronautical communications for personal and multimedia services[END_REF] mentioned that there are two types of PEDs' interference, intentional and spurious. The former is the emissions used to transmit data over the PED's allocated frequency band. The latter is the emissions due to the RF noise level.

Moreover, the existing systems suffer from bandwidth limitations; the trend toward bandwidth-consuming Internet services currently cannot be satisfied [START_REF] Jahn | Evolution of aeronautical communications for personal and multimedia services[END_REF]. PAX number and categories can be considered as a factor that affects network scalability. For example, the network bandwidth should be increased if the number of the first class PAX was increased to support the increasing need for video stream.

It is stated by Holzbock [7] that existing indoor channel models mainly investigate office or home environments, thus these models may not be appropriate for modeling an aircraft cabin channel. Attenuation of walls and multi path effects in a 'normal' indoor environment are effects which are not expected to be comparable to the effect of the higher obstacle density in a metallic 'tunnel'. The elongated structure of a cabin causes smaller losses, than that expected in other type of room shapes. However, the power addition of local signal paths can lead to fading of the signal in particular points. In addition, small movements of the receiver can have a substantial effect on reception. The same opinion was emphasized by Diaz [START_REF] Diaz | Wideband Channel Characterization for Wireless Communications inside a short haul aircraft[END_REF]. To overcome this problem, Youssef [START_REF] Youssef | Wireless network simulation in aircraft cabins[END_REF] used the commercial software package Wireless Insite to model the electromagnetic propagation of different wireless access points inside different types of aircrafts. Another challenge is that the cabin of an aircraft and the aeronautical environment in general define a very specific scenario that presents several constraints which will affect the coverage and capacity planning. This is due to the fact that the space is very limited in an aircraft cabin, and its design allows installing equipment only in specific locations, where the configuration of the panels is easy to disassemble for maintenance [START_REF] Niebla | Coverage and capacity planning for aircraft in-cabin wireless heterogeneous networks[END_REF]. Therefore, the replacement technique associated with the IFE system components, may affect the welling of the companies to use them. Replacing time consuming parts can lead to a long aircraft downtime or flight delays. Also, a device that fails during the flight, and is difficult to be replaced, will cause the passenger to be unsatisfied. Consequently, it is advisable to design components that are easily replaced with the minimum required technical skill.

IV. PROPOSED COMMUNICATION TECHNOLOGIES

As mentioned by Holzbock [START_REF] Holzbock | Advances of aeronautical communications in the EU framework[END_REF], wireless Cabin aims at developing a communication infrastructure consisting of heterogeneous wireless access networks to provide aircraft PAX and crew members with access to IFE system. PAX are able to access different services through state-of-the-art wireless access technologies such as W-LAN IEEE802.11, and Bluetooth.

A. Ethernet

Ethernet is currently the standard for wired communication in different fields. Haydn [START_REF] Thompson | Wireless and Internet communications technologies for monitoring and control[END_REF] showed that it is characterized by interesting features such as good communication performance, scalability, high availability, and resistance to external noise. However, Ethernet cabling is considered a burden for aircraft design

B. Wireless LAN

WLAN is a well known technology used in different commercial, industrial, and home devices, and can easily coexist with other technologies to form a heterogeneous network [START_REF] Niebla | Coverage and capacity planning for aircraft in-cabin wireless heterogeneous networks[END_REF]. Jim [START_REF] Lansford | Wi-Fi (802.11b) and Bluetooth: Enabling Coexistence[END_REF] stated that WLAN and Bluetooth technologies are too complementary not a competing technologies. They can cooperate together to provide users with different connecting services.

C. Wireless USB

USB technology allows different peripherals to be connected to the same PC more easily and efficiently than other technologies such as serial and parallel ports. However, cables are still needed to connect the devices. This raised the issue of Wireless USB (WUSB) where the devices can have the same connectivity through a wireless technology. Neal [START_REF] Leavitt | For Wireless USB, the Future Starts Now[END_REF] stated that although it is difficult to achieve a wireless performance similar to wired USB, but the rapid improvements in radio communication can make WUSB a competent rival. It is based on the Ultra Wide Band (UWB) technology. In Europe, it supports a frequency range from 3.1 to 4.8 GHz. Moreover, Udar [START_REF] Udar | Characterization of Ultra Wide Band Communications in Data Center Environments[END_REF] mentioned that UWB communication is suitable for short range communications which can be extended by the use of mesh networks. Although WUSB was designed to satisfy client needs, but it can also be used in a data centre environment. He discussed how WUSB characteristics can match such environment. This application can be of a great help in IFE systems which strive to massive data communication to support multimedia services and minimizing the connection cables. Moreover, Jong [START_REF] Sohn | Design issues towards a high performance wireless USB device[END_REF] discussed the design issues related to WUSB. He stated that WUSB can support up to 480Mbps, but in real world it doesn't give the promised values; and he showed the effect of design parameters on the device's performance.

D. Power Line Communication

A PLC network can be used to convey data signals over cables dedicated to carry electrical power; where PLC modems are used to convert data from the digital signal level to the high power level; and vice versa. Using an existing wiring infrastructure can dramatically reduce costs and effort for setting up a communication network. Moreover, it can decrease the time needed for reconfiguring the cabin's layout since less cables are going to be relocated.

However, such technology suffers from different problems. A power line cable works as an antenna that can produce Electromagnetic Emissions (EME). Thus, the PLC device must be Electromagnetic Compatible (EMC) to the surrounding environment. This means that it must not produce intolerable EME, and not to be susceptible to them. To overcome this problem, the transmission power shouldn't be high in order not to disturb other communicating devices [START_REF] Hrasnica | Broadband Powerline Communications Networks[END_REF]. However, Working on a limited power signal makes the system sensitive for external noise. In spite of this, the PLC devices can work without concerns of external interference due to two reasons. Firstly, the PLC is divided into segments; this minimizes signal attenuation. Secondly, all the cabin's devices are designed according to strict rules that prevent EME high enough to interfere with the surrounding devices.

V. A HETEROGENEOUS ARCHITECTURE

IFE system is a field starving for unusual ideas. PAX can be satisfied by receiving services dedicated to a single user, but it will be more amusing if they can be offered services for multiple users, where PAX of similar interests can share their time. Using a single communication technology inside the cabin can't yield satisfactory results, but a combination of different technologies can have a great impact on the provided services.

The term heterogeneous in the networking domain usually implies the mix between wireless and wired networks. However, we mean by heterogeneity, the existence of different networking technologies cooperating together to achieve certain services. The network can be divided into User Technology and System Technology. A User Technology is the technology apparent and directly used by the user (i.e., Bluetooth, WiFi, etc…) to connect his devices to the system. A System Technology is the technology used by the system and is hidden from the user (i.e., PLC). In our proposed heterogeneous architecture, we suggest the usage of a PLC network to convey data between a data server and the PAX seats where he use his PEDs. In addition, wireless APs are connected to the PLC backbone as well; while WUSB is used to provide a way to connect some USB devices to the network (see Figure 1).

A. PLC

In this section, we will introduce some experimentation results to show the applicability of using PLCs for a cabin's IFE system. As shown in Figure 1, the PLC system consists of a Power Line Head Box (PLHB) and a Power Line Box (PLB). The PLHB connects the two terminals of the power line to connect the data server with the seats. Each PLHB service a group of seats which are equipped with PLB per seat. The PLB is responsible for distributing the signal received by the PLHB to the seat's SEB. Each PLHB can support up to 20 PLBs at a rate of 3480 bit/sec. Both PLHB and PLB devices can be configured through their internal web interface to define their IP address and other configuration parameters.

The MGEN (version 4.2) [START_REF]MGEN site[END_REF] traffic generator was used to emulate the traffic produced by the data server, and a laptop was used as a substitute to the SEBs. The target of the test was to collect different statistics to study the behavior of the PLC system by injecting periodic traffic flows at constant intervals. However, it is normal to have packet dropping during transmission; this is illustrated in Figure 3 showing the obtained loss fraction. It is less than 0.05 which can be considered as a good value. Such configuration can provide the IFE with a way to provide video services by using the existing power cabling.

B. WLAN

We held different NS2 [16] simulations to propose a good distribution for the wireless Access Points (APs) inside the cabin. We used the same cabin configuration used by Alexandaros [START_REF] Kaouris | Propagation Measurements inside a B737 Aircraft for In-Cabin Wireless Networks[END_REF]. The cabin consists of 26 rows with 6 seats each (3 on each side of the aisle); this gives a total of 156 seats. The cabin is 21m long and 3.54m wide. The rows' separation distance is 81cm.

A wireless node -representing a passenger's device -is located at the position of each seat, and APs are used to connect them with the data server. Using large number of wireless devices in a very narrow metallic tunnel like the cabin has a dramatic effect on the network's performance. For this reason, we are studying the effect of using frequency separation between APs. However, we need to determine the minimum number of APs required to cover the whole cabin, and their distribution inside the cabin, so we experimented with three scenarios. In scenario 'A', all nodes (each has a transmission range covering the whole cabin) are using the same communication channel. Scenario 'B' uses nodes with short transmission range, which allows connection only to the nearest Access Point (AP), while using the same channel. Scenario 'C' shows nodes with short transmission range and using channel separation. The channel separation in the third scenario is based on the fact that 802.11 only allows the usage of three non interfering channels (i.e., channels 1, 6, and 11). The impact of the three scenarios over average throughput, average delay, and number of transmitted packets is studied. Each scenario was repeated 5 times while using different numbers of Aps located at the aisle. We started by using one AP and the number is incremented until we reached the maximum number of APs which was determined according to the cabin's dimensions. The AP's transmission power was adjusted to minimize the transmission range, so the signal can travel a distance just enough to reach the seat beside the window in order to minimize the effect of its reflection. This allowed us to use a maximum number of 5 APs (Figure 5).

For all scenarios, the nodes (156 node + APs) were configured to have a large queue that can hold up to 1000 packets in order to prevent packet dropping. The transmission power was adjusted to 10mW as the minimum value defined in the 802.11 standard. In scenarios that use different channels, Channels 1, 6, and 11 were adjusted to their frequencies 2.412e9 Hz, 2.437e9 Hz, and 2.462e9 Hz respectively. The Rx threshold was determined according to the required transmission range. It was calculated by the tool "Threshold" provided as a separate program with the NS2 simulator. TABLE I. shows the values used with each number of APs. For each simulation, the APs were distributed evenly throughout the aisle to provide a full coverage for the cabin. When comparing the three scenarios we can find that using just different number of APs doesn't have a great impact on the networks performance, but when accompanied with channel separation the networks performance is dramatically enhanced. Figure 6, Figure 7, and Figure 8 combine the results of scenarios A, B, and C. It is noticeable that there is no great difference between scenario A and B; this is due to the existence of large number of nodes in a small area. In addition, there are many nodes in the shared zone between every two APs. In this zone, nodes are able to detect two APs, but they select just one of them. In other words, on the physical level signals are interfering, while on the logical level only one AP is seen. However, as the number of APs increase, the difference between scenario A and B starts to increase slightly; this is because the number of nodes in the shared zone becomes less, so the interference decreases. On the contrary, when using channel separation (i.e., scenario C) performance was dramatically enhanced after using 3 APs. It is worthy to note that the number of nodes assigned to each AP affects its performance; the fewer nodes we use, the higher performance we get. When using 1, 2, 3, 4, and 5 APs, each AP will have 156, 78, 52, 39, and 32 nodes respectively. However, the difference in the number of assigned nodes with 3, 4, and 5 APs is small. This justifies the reason for saturation after using more than 3 APs; where APs almost handles the same amount of APs

C. WUSB

Using WUSB to connect passenger's devices seems to be an appealing solution since it doesn't require any additional adapters or connectors, and avoids interference with other wireless technologies (i.e., WLAN, Bluetooth, etc…) by using different bandwidth. 1) Connecting different USB devices Connecting multiple USB devices (i.e., mouse, and keyboard) was done in two different ways; firstly by using two Device dongles for each USB device, secondly by using a USB hub. The results of the first approach were not satisfactory because the two dongles were using the same channel causing interference between them. However, the Host dongle has the ability to choose between seven different channels. In other words, it is possible to use seven Hosts at the same transmission range without any interference between them. The second approach gave better performance. Moreover, a hub is much more economical than using a WUSB dongle dedicated for each device.

3) Transmission range with different power levels

The test started by putting the Host dongle and the Device dongle on the same line of sight; then the device dongle is moved away until it is disconnected. The same procedure was repeated while using two Device dongles. The two dongles are placed at the same horizontal level with a separation of few centimeters, and are moved together. The whole experiment was repeated while changing the dongles transmission power level (i.e., low, normal and strong).

TABLE III. TRANSMISSION RANGE

As shown in TABLE III. , the existence of two dongles at the same and working at the same channel has a dramatic effect on transmission range, so when considering that the distances between seats inside the cabin is considerably short when compared with the minimum transmission range, then it is highly recommended to use different channels for neighboring dongles.

VI. CONCLUSION AND FUTURE WORK

Heterogeneous network architecture is a promising solution for such application. Using PLC networks can be a competitive solution since it decreases the amount of cabling inside the cabin, and can be used to connect the APs (to support mobility) directly to the network system. Moreover, it overcomes the interference constrain, and can provide enough bandwidth to support heavy traffic required for multimedia services. When combined with WUSB, it becomes easier for PAX to connect their PEDs.

Through experimentation results and simulations, this work proves that it is possible to build a heterogeneous network which contains all the mentioned technology; each to solve a certain part of the problem. Multimedia content distribution supported by PLC and Ethernet architecture added to personal communication supported by WUSB can provide the IFE system with a satisfactory solution needed for such systems. This can be done without interfering with each other.

It is planned to investigate the feasibility of using other technologies such as UWB and smart antennas; where low energy transmissions with high bandwidth while covering certain regions can be used to increase performance. In addition, scalability issues of WUSB need more investigation.

Figure 1 .

 1 Figure 1. Heterogeneous network architecture

Figure 2 .

 2 Figure 2. Flow rate of all flows Figure 2 shows the sum of flows' rates. The stepping of the flow rate is constant indicating that the PLC connection is able to carry the 20 flows. In addition, Figure 4 represents the packet count of the first flow. It is clear that the packet count stayed constant from the start to the end of the simulation without being affected by the injection of the subsequent flows. This emphasis the same results derived from Figure 2

Figure 3 .

 3 Figure 3. Packet count of the first flow

Figure 4 .

 4 Figure 4. Loss Fraction

Figure 5 .

 5 Figure 5. APs distribution

Figure 6 .

 6 Figure 6. Packets sent by the transmitter

Figure 7 .

 7 Figure 7. Average Throughput

Figure 8 .

 8 Figure 8. Average delay

Figure 9 .

 9 Figure 9. WUSB test-bed

TABLE I

 I

			.	RX THRESHOLD VALUES
	Number of APs	Transmission	Rx threshold
			range(meters)
		1		10.5		8.97474e-9
		2		5.25		3.58989e-8
		3		3.5		8.07726e-8
		4		2.625		1.43596e-7
		5		2.1		2.24368e-7
			Tx's sent packets
		70000
		60000
	Number of Packets	10000 20000 30000 40000 50000				Scenario A Scenario B Scenario C
		0
		1	2	3	4	5
			Access Points

USB Ethernet cable Host dongle Device dongle USB cable (optional) USB hub (optional) USB Ethernet cable Host dongle Device dongle USB cable (optional) USB hub (optional)

  It is important to know if WUSB is capable of transferring large files, and to what extent it is comparable to wired USB, so 4064 files of size 892MB were transferred to a flash USB storage device using WUSB and wired USB. The results shown in TABLE II. indicate that WUSB are slower by almost 60% than wired USB.

	2) File transfer
			Average Delay
		25000
		20000
	Microseconds	10000 15000				Scenario A Scenario B Scenario C
		5000
		0
		1	2	3	4	5
			Access Points

TABLE II

 II

		.	WUSB VS WIRED USB
		Elapsed time	Delay ratio
	WUSB	915secs		((344/915)*100)-100
	Wired USB	344secs		= 62.4%