Dimitris Mourtzis

Michalis Doukas

A knowledge-based decision-making framework for the design of manufacturing networks for custom-made products

Keywords: Manufacturing Networks, Knowledge, Decision making

Efficient design of manufacturing networks is paramount for a sustainable growth. The establishment of mass customization and the transition to personalization complicates design activities and leads to vast amounts of unexploited data. This research work aims to exploit existing knowledge for enhancing decision-making during the initial manufacturing networks design, which carry out custom orders of industrial equipment. A method developed into software is proposed, comprising a Genetic Algorithm with knowledge-enriched operators and an intelligent initialization algorithm that exploits existing planning knowledge. The validation of the method is performed using data from a highprecision mold-making manufacturer and its network of first-tier suppliers.

Introduction

The establishment of mass customization and the gradual transition towards personalization affects manufacturing network design [START_REF] Mourtzis | Design and Operation of Manufacturing Networks for Mass Customisation[END_REF]. To achieve the desired variety, quick adaptation and re-configuration of production networks is necessary [START_REF] Mourtzis | A multi-criteria evaluation of centralized and decentralized production networks in a highly customer-driven environment[END_REF]. Also, vast amounts of planning-related data are generated daily, which however, remain unexploited. Reuse of past knowledge can improve decision-making, as design, planning, and operation activities of past and new projects, share numerous commonalities [START_REF] Baxter | An engineering design knowledge reuse methodology using process modelling[END_REF]. This research work presents a method for the initial design of manufacturing networks subject to unpredictable customer requirements for custom-made products. The suggested approach attempts to identify near optimum manufacturing network configurations for a specific custom product, while minimizing the total flowtime. It also allows the timely reconfiguration of the system to adhere to actual manufacturing capacity and availability. The method is validated with data from the mold-making industry.

State of the Art

Knowledge reuse in manufacturing has yet to reveal its full potential [START_REF] Chryssolouris | Manufacturing Systems: Theory and Practice[END_REF] after almost three decades of research [START_REF] Chryssolouris | Knowledge-based systems in manufacturing[END_REF]. Numerous approaches are available for knowledge reuse in product design [START_REF] Cochrane | Knowledge reuse in manufacturability analysis[END_REF], process planning [START_REF] Züst | Knowledge-Based Process Planning System for Prismatic Workpieces in a CAD/CAM-Environment[END_REF] and part family representation [START_REF] Mäntylä | Representation of Process Planning Knowledge for Part Families[END_REF].

Regarding the problem of design of manufacturing networks, the identification of optimum multi-stage, multi-product manufacturing network or system configurations, under hard pre-and post-condition constraints is strongly NP-Hard [START_REF] Garey | Computers and Intractability -A Guide to the Theory of NP-Completeness[END_REF]. Enumerative methods are non-applicable for such problems; instead optimization methods are being applied, aiming at multi-or single-objective optimization. A GA was used in [START_REF] Chryssolouris | Dynamic scheduling of manufacturing job shops using genetic algorithms[END_REF] for addressing to the job-shop scheduling problem. The method included random input turbulences, multiple criteria and multiple job routes. A scheduling approach was developed in [START_REF] Elmaraghy | A Genetic Algorithm Based Approach for Scheduling of Dual-Resource Constrained Manufacturing Systems[END_REF] using a GA, to determine the efficient assignment of machines and workers in order to optimize performance criteria such as the mean flow time. The problem of scheduling of a Flexible Manufacturing System using a GA with knowledge based genetic operators is included in [START_REF] Prakash | FMS scheduling with knowledge based genetic algorithm approach[END_REF]. The way that these operators exploit past knowledge was unclear. The authors in [START_REF] Yan | Knowledge-Based Genetic Algorithms[END_REF] attempt to discover knowledge patterns that are generated in each generation of a GA using Rough Set Theory. The combined utilization of knowledge-based methods directly incorporated in the metaheuristic optimization algorithm is missing from the literature to the best of the authors' knowledge.

The presented research work combines knowledge-based techniques with an optimisation engine for supporting the initial design of manufacturing networks for custommade industrial equipment. Existing knowledge regarding past design and planning projects is embedded in evolutionary operators in the form of rules. In addition, the formation of the initial GA population is pre-optimised, since similarity measurements against known planning cases are used. Based on successfully executed past planning projects, the search for optimum configurations for new problems becomes guided.

Knowledge-based Manufacturing Network Design

The proposed method focuses on identifying near-optimum feasible selections of manufacturing nodes and suppliers, while minimising manufacturing flowtime for an engineer-to-order product. The structure of the manufacturing network is shown in Fig. 1. terised by an availability index that models manufacturing capacity to meet market demand. Static capacity models are widely used by industry as cost-effective means for communicating capacity across the supply chain [START_REF] Witte | Using static capacity modeling techniques in semiconductor manufacturing[END_REF][START_REF] Ozturk | Conceptualization, design and implementation of a static capacity model[END_REF]. The availability index values of OEM nodes and for suppliers are defined using historical observations.

Formulation of the design problem

Let the processing time for the task t to be performed by machine k be ptk and a task selection p = {p1, p2,…, pn}, where n tasks (j = 1, 2,…, n) will be processed by m machines (k = 1,2,…, m). Similarly, we define the setup times for machine k to perform task t as stk, and the waiting time of task t in the queue of machine k as wtk. The sum of wtk, ptk and stk for all product components, represents the flowtime of the product. The Total Flowtime FTtot(p) of a design p can be computed by summing all flow times (1):

𝐹𝑇 𝑡𝑜𝑡 = ∑ 𝐹𝑇(𝜋 𝑡 ) = ∑ 𝐶(𝜋 𝑡 , 𝑚) 𝜋 𝑡=1 𝜋 𝑡=1 (1)

Knowledge enriched Genetic Algorithm

The problem is solved by a Genetic Algorithm (GA) [START_REF] Holland | Adaptation in Natural and Artificial Systems[END_REF], with knowledge enriched operators. In contrast to a regular GA, the proposed enriched GA includes an intelligent initialization process and rule-based selection of genetic operators (selection, crossover and mutation). The steps of the knowledge enriched GA are visualized in Fig. 2.

Each manufacturing process can be performed by both a machine tool family and by specialized suppliers. However, based on technological differences and availability, different flow times are associated with different machines or suppliers carrying out the same task. Thus, each chromosome is encoded to represent alternative selections of nodes to carry out the required tasks. The encoding uses integer values in a matrix structure. This encoding structure is beneficial since it reduces decoding complexity.

Initialization Procedure.

Instead of generating the initial population of alternative designs in a totally random fashion, each newly investigated planning case is compared to previously executed cases through a pairwise comparison of their most important attributes, i.e. number of components, special works, machining features, volumetric data, etc. Thus, based on similar past design cases, an appropriate adaptation of the task sequence and their mapping to processing nodes is done to best fit the new case requirements. This leads to a pre-optimised initial set of individuals to be fed to the GA. The similarity between numerical attributes is computed using the Euclidean distance [START_REF] Mourtzis | A multi-criteria evaluation of centralized and decentralized production networks in a highly customer-driven environment[END_REF].

𝐷 𝑛 = ∑ √|1 -|1 - 𝑇 𝑝𝑖 𝑇 𝑛𝑖 | * 𝑤 𝑖 | 𝑛 𝑖=1 (2)
where: n = no. of features, Tni, Tpi = new and past case features, wi = feature weight.

Fig. 2. The workflow of the knowledge enriched Genetic Algorithm

Selection Operators.

Selection is used in GAs to identify individuals that will carry their genes to the next generation. Here, the following widely used operators Roulette Wheel Selection (RWS), Stochastic Universal Sampling (SUS) and Tournament Selection (TS) are used [START_REF] Mitchell | An Introduction to Genetic Algorithms[END_REF]. To exploit previous knowledge coming from network and human planner, and to imbue it in the algorithm, a set of IF THEN rules has been developed in cooperation with the industrial partner of the case study. An analysis involving semi-structured questionnaires that were filled in by employees led to defining these rules. Moreover, literature findings about the performance of different operators in specific situations are encapsulated [START_REF] Mitchell | An Introduction to Genetic Algorithms[END_REF]. rule example for adapting the selection method is the following:

IF current_CPU_time < termination_CPU_time/5 THEN Selection_method = RWS ELSE IF current_CPU_time > termination_CPU_time/2 THEN Selection_method = SUS

ELSE Selection_method = TS

RLW is known to drive to convergence and SUS forces an even faster convergence by the algorithm. In case the predetermined runtime is near exhaustion, then SUS is assigned for deriving a solution. Additional rules are similarly implemented.

Crossover Operators.

Crossover, handles mating between chromosomes, by selecting two (or more) parents in order to produce off-springs. The crossover operators used are: Single, Multi-point and Uniform. A rule example follows:

IF hardening_quality = very_good THEN Crossover_Method = Single_Point_Crossover(n)
Through a characterisation of hardening types (normal, good, very good) by experts, based on thickness quality (in μm), specific partners must be selected that can offer the required precision. Due to the fact that these partners are located in distant countries from the mold maker facilities, hardening may require disproportionately large lead times (up to 3 weeks). Thus, a single crossover point is set right before the gene assignment that represents the partner that carries out the hardening. This ensures a higher degree of exploration of alternative paths and possibly great reductions in flowtime.

Mutation Operators.

Mutation is necessary for maintaining the genetic diversity in the population. Fine tuning of mutation operators can alter the behavior of the search from explorative (visit new areas of the search space by creating new individuals) to exploitative (local optimization by fine-tuning existing individuals). The mutation operators are: Uniform and Gaussian Mutation. A rule for selecting each one of these methods is the following:

IF Best_of_Pop(n) < Best_of_Pop(n-1) FOR 5 consecutive gens THEN Mutation_Operator = Gaussian_Mutation

In case the population stagnates to local optima and no improvement is observed in subsequent generations, then, a Gaussian mutation with reduced variance is selected, to ensure a higher probability of mutation compared to a purely stochastic sampler.

Industrial pilot case from the mold making industry

Mold making is technology, knowledge and labor intensive [START_REF] Klocke | Perspectives for the German Die and Mold Manufacturing Industry[END_REF]. Each new mold is a unique product, which yet shares a number of commonalities with previous cases on process plan and resource level. Thus, reusing knowledge from finished mold-making cases can reduce overhead times required for initial network planning, decrease rampup, improve response time to volatile market requirements and lead to cost savings. The case study for the validation of the method was an already finished mold with documented process plans from a company that manufactures high precision injection molds. The dataset included alternative machines and also operations and processing, setup and waiting times for similar machines to perform identical processes (Fig. 3).

Fig. 3. The components of the mold and the integer encoding of the chromosome

The resource model of the pilot case includes the characteristics of the manufacturing nodes, and the required processing times of components in technologically similar resources, as well as the flowtimes required by suppliers for supplying the requested material or for performing a specialized process (e.g. hardening). Moreover, the availability of the resources and suppliers has been modelled based on historical data, as follows: 75% for part suppliers, 50% for outsourcing suppliers, and 35% for milling operations (roughing, finishing, air and water circuits cutting) performed in the manufacturing facilities of the OEM, 70% for wire cutting and die sinking, and 45% for manual tasks, such as fitting, polishing and assembly.

The product model includes: geometric characteristics of the components, number of cavities, tolerance specifications, cooling mechanisms, ejection methods and other process plan related information. The manufacturing processes required include: roughing, finishing, hardening, creation of air and water circuits, drilling, wire cutting, grinding, fitting, creation of electrodes for die sinking, polishing, measuring and assembly.

Experimentation: Results and Discussion

A set of experiments were carried out to investigate the performance of the developed GA. The total number of feasible alternative configurations for this problem is 156x10 15 , as a combinatorial analysis indicates. The optimal set of tuneable parameters of the GA was identified through a Statistical Design of Experiments (SDoE) and was the following: Population Size = 50, No. of Generations = 50, Generation Gap = 0.9, Termination Time = 20 sec and Mutation Probability = 0.009. Moreover, a correction factor is applied on the obtained flowtimes in order to take into consideration machine breakdowns, shortage of materials and other unpredictable factors The presented research work investigated the initial design of a manufacturing network for custom-made products. The problem was tackled by a knowledge enriched Genetic Algorithm (GA) and its performance was tested in a real case study coming from the high precision mold making sector. The results depicted an improvement against both a regular GA and actual historical data. The encapsulation of knowledge into the genetic operators and the intelligent initialization process enhanced the robustness of the GA. The quality of the obtained solutions surpasses actual historical performance of the network, which was configured based on human experience and was therefore sub-optimal. Moreover, the small execution time of the algorithm facilitate the need for near real-time reconfiguration of the network for compensation to unforeseen disturbances.

The proposed method and tool can be exploited by a planning manager in order to support the design and planning of efficient manufacturing networks and systems. The results obtained by the tool can be overridden by the manager in cases when the proposed solution is not satisfactory and the algorithm may be executed repeatedly until an accepted solution is found. The low computation requirements of the algorithm constitute it suitable for deployment on mobile devices and enables fast decisions on the go. Future work will focus on extending the rule-base in order to cover additional historical observations and expert knowledge. Also, the method will be developed into an app for mobile devices. The GA will be executed into a company-owned private Cloud server and services will be exposed for distributing information to mobile devices.

Fig. 1 .

 1 Fig. 1. The manufacturing network nodes

  . The correction factor was adjusted through the deviation of actual times obtained by the mold maker and experimental values for different mold cases. The results of the execution of the GA are shown in Fig.4. The algorithm converges after 28 generations to an optimum flowtime of 1,211 hours requiring a total runtime of 19.56 seconds. In comparison, a regular with optimised parameters based on a SDoE) yielded in the same number of generations a globally best solution of 1,450 hours, i.e. a 17.96% worse solution. Most importantly, this obtained value is significantly lower (38.26%) when compared to the actual flowtime for the specific order, which, as reported by the production engineer of the mold maker was 1,784 hours.

Fig. 4 .

 4 Fig. 4. Evolution of the fitness function (left) and improvement of total flowtime (FT) obtained by the enriched GA after 50 generations and comparison to historical data and a simple GA

Acknowledgements

This research work is partially supported by the EU funded research project "Applications for Advanced Manufacturing Engineering -Apps4aME" (GA No. 314156).


Michel Gourgand
email: gourgand@isima.fr

Nathalie Grangeon
email: grangeon@isima.fr

Nathalie Klement
email: klement@isima.fr

An Analogy between Bin Packing Problem and Permutation Problem: A New Encoding Scheme

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The bin packing problem has been introduced by [START_REF] Johnson | Near-optimal bin packing algorithms[END_REF]. It considers a set of N items, each item with a given size w i , and several bins with a same capacity C. The aim of this problem is to pack all of the items in a minimum number of bins. The sum of the size of the items packed in a bin has to be smaller than the capacity of the bin. Each item has to be packed in one bin.

This problem can be met in industrial application or computer network design and memory allocation [START_REF] Chandra | Bin packing with geometric constraints in computer network design[END_REF]. [START_REF] Bortfeldt | Container loading problems: A state-of-the-art review[END_REF] makes a state-of-the-art review about the container loading problem: the bin packing problem can be used to pack a set of cargo into a minimum number of containers. It can also be used to solve assembly line balancing problems [START_REF] Wee | Assembly line balancing as generalized bin packing[END_REF] or multiprocessor scheduling problems [START_REF] Coffman | An application of bin-packing to multiprocessor scheduling[END_REF].

In [START_REF] Gourgand | Activities planning and resource assignment on multi-place hospital system: Exact and approach methods adapted from the bin packing problem[END_REF] we use the bin packing problem to model the problem of activities planning and resources assignment, called the HCT problem. The problem considers a system composed of resources and of a set of activities to assign. Each activity needs a resource to be treated and a time slot, a period when it will be done. Each activity has a known process time. Each activity starts in one period and finishes in the same period. Resources have a planning defining their available time: the resource opentime. Each resource cannot treat all the activities, there is a list of incompatibilities between activities and resources.

The aim is to assign each activity to one resource and one period. Activities have to be done as soon as possible, so the assigned periods have to be the smallest possible. The aim of the HCT problem is not to make a precise schedule of the activities but to assign a period to each activity.

The HCT problem has to respect some constraints: resources have to be able to process their assigned activities according to the incompatibilities; activities have to be assigned to a resource during the opentime of this resource; each activity has to be assigned to one resource and one period. Figure 1 gives an example of an assignment in such an application. A couple (resource, period) can be seen as a bin. Activities are assigned to resources during periods. All the resources have the same opentime.

Table 1 summarizes the analogies between the bin packing problem and this application. A new constraint in the HCT application is the incompatibility constraint between resources and activities. The HCT problem can be seen as an extension of the bin packing problem with incompatibility constraints. In Section 2, a brief state of the art about approximate algorithms used to solve the bin packing problem is made. In this paper, we propose an encoding scheme, which is used in the hybridization between a metaheuristic and a list algorithm. The used method is described in Section 3, as its theoretical justification. The experimental results on literature instances are presented in Section 4. This paper is ended by a conclusion and some further works.

State of the art

Given the size of the real problems that can be solved thanks to the bin packing problem, exact methods quickly reach their limit about computational time. Moreover, [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-completeness[END_REF] shows that it is an NP-Complete decision problem. Approximate algorithms seem to be a good way to solve this problem.

The most popular list algorithms have been developed by [START_REF] Johnson | Near-optimal bin packing algorithms[END_REF]. Items are considered one by one according to a list. Next Fit (N F ) is the most intuitive method for the bin packing problem. The maximum number of items is packed into the current bin. If the available space in the current bin is smaller than the size of the considered item, this bin is closed and a new bin is opened and becomes the new current bin. First Fit (F F ) is different from N F in that none of the bins is closed. Each item is packed into the first bin which can contain it. Once an item cannot fit in any bin, a new bin is opened. Best Fit (BF ) consists in packing each item into the best bin which is the one with the smallest available space after packing the considered item into it.

The use of metaheuristics to solve the bin packing problem starts in the 1990s. In most published works, a classical encoding scheme S is used where S(i) is the index of the bin where item i is placed. [START_REF] Alvim | A hybrid improvement heuristic for the one-dimensional bin packing problem[END_REF] proposes a hybrid metaheuristic based on tabu search. [START_REF] Falkenauer | A hybrid grouping genetic algorithm for bin packing[END_REF] proposes a hybrid grouping genetic algorithm which uses the heuristic F F D [START_REF] Johnson | Near-optimal bin packing algorithms[END_REF] and the dominance criterion from [START_REF] Martello | Lower bounds and reduction procedures for the bin packing problem[END_REF]. To a better use of grouping genetic algorithm, it uses the classical encoding, augmented with a group part which defines the used bins. [START_REF] Loh | Solving the one-dimensional bin packing problem with a weight annealing heuristic[END_REF] applies a new approach method: the weight annealing. It uses the classical encoding scheme. [START_REF] Levine | Ant colony optimization and local search for bin packing and cutting stock problems[END_REF] uses a hybrid ant colony optimization, inspired by Falkenauer's works. It does not individualize the items, they are designated by their size and not their index: S = (w i ) i∈N with w i the size of item i. In these papers, the hybrid part consists in matching a known metaheuristic (like genetic algorithm, tabu search method, ant colony optimization) to an additional improvement method such a local search.

Another encoding scheme has been exploited. [START_REF] Reeves | Hybrid genetic algorithms for bin-packing and related problems[END_REF] uses a permutation coding to hybridize the genetic algorithm. [START_REF] Stawowy | Evolutionary based heuristic for bin packing problem[END_REF] uses a permutation with separators representation: it is a list of n items and l separators of bins, integers from range {1, ..., n} represent the item, integers {n + 1, ..., n + l} represent the separators. A simplified version of the genetic algorithm is developed: a simple evolutionary based heuristic.

Most of the works on the bin packing problem uses population based metaheuristics.

Proposed hybrid method

The method proposed in this paper uses a hybridization between a metaheuristic and a list algorithm (Next Fit, First Fit, Best Fit). This method is performing in two search spaces: Ω where a solution represents a list of items and S where a solution represents the assignment of each item to a bin. The aim of this purpose is to reduce the size of the set of solutions where the metaheuristic is performing.

Encoding of the set of solutions

The used encoding is inspired by the one used in the permutation problems. A solution (X i ) i∈N ∈ Ω is a list of items as in a permutation problem with X i an item index. A list algorithm L, such as N F , F F or BF , is applied to the list of items X to determine the assignment of the items to the bins: (Y i ) i∈N ∈ S as the classical scheme, with Y i the bin index assigned to item i. Then a cost function H is applied to the assignment Y . The general scheme of the encoding is the following:

X ∈ Ω -→ Heuristic L L(X) = Y ∈ S -→ Criteria H H(Y )
Figure 2 summarizes the considered sets of solutions.

Ω Ω ′ x x x C S x

Fig. 2. Sets of solutions

-Ω is the set of all the lists of items. card(Ω)= N ! -Ω ′ is the set of all the possible assignment of items to bins, without checking the capacity constraint. card(Ω ′ )= N N -C is the set of the admissible solutions: a solution is admissible if the capacity constraint is respected. C ⊆ Ω ′ . -S is the set of all the solutions built by the application of a list algorithm on a list of items. S ⊆ Ω ′ and S ⊆ C.

Proof that S contains the set of optimal solutions: Let be Y * any optimal solution. Y * = (Y * 1 , ..., Y * N ) with Y * i the bin index assigned to item i. A list of items assigned in each bin is deduced. By concatenation of these lists, an ordered list of all the items is determined: X * ∈ Ω. By applying the heuristic F F or N F to X * , Y * is found, so Y * ∈ S. As a consequence the set of the optimal solutions written C * is included in S.

The following example considers the assignment of eight items. Two different solutions in Ω give the same element in S. In total, 2 × 4! × 2 = 96 elements in Ω give the same element in S. Let be S B the set of solutions ∈ Ω ′ built by the heuristic BF , S F the set built by F F and S N the set built by N F . We have the following assumption:

C * ⊆ S B ⊆ S F ⊆ S N ⊆ C ⊆ Ω ′
. By exploiting this encoding scheme, the search space is reduced and it is assured that the optimal solution can be reached. This proposition presents some advantages:

-Admissibility of the solutions is by the list algorithms.

-Many metaheuristics already exist to solve the permutation problems, with their neighborhood systems for single solution based metaheuristics and their crossover operator and/or mutation for population based metaheuristics. -The metaheuristic is performed on a smaller set S than the original one Ω ′ .

-The set S all the optimal solutions. -S conforms with the property of accessibility.

-This method is a combination of simple existing methods easy to implement.

General framework

The general framework can be used with any metaheuristic. Algorithm 1 shows the principle of hybridization between a local search and a list algorithm where V : Ω -→ Ω denotes the neighborhood system and H : S -→ N the cost function.

Algorithm 1: Principle algorithm of the hybridization 1 Let be X ∈ Ω the initial solution 2 Y = L(X): a list algorithm is applied to the list X 3 while necessary do 4 Choose uniformly and randomly X ′ ∈ V (X)

5 Y ′ = L(X ′ ) 6 if H(Y ′ ) ≤ H(Y ) then 7 X = X ′ 8 Y = Y ′
Neighborhood system V (X): Several classical neighborhood systems for permutation problems can be used; P i,j : the item at position i permutes with the one which is at position j. |P i,j | = N.(N -1)

2

; I i,j : the item at position i is inserted at position j. |I i,j | = N.(N -1). In both cases, V satisfies the accessibility and reversibility properties.

Cost function H(Y ): The most intuitive cost function is the number of used bins. But many solutions have the same value of cost function. To avoid it, [START_REF] Falkenauer | A genetic algorithm for bin packing and line balancing[END_REF] proposes a new cost function H which characterizes the average bin utilization, defined by Equation [START_REF] Johnson | Near-optimal bin packing algorithms[END_REF].

H(Y ) = - j∈N (F j (Y )/C) k M (Y ) (1)
Where F j (Y ) = N i=1 w i .δ j,Yi , ∀j ∈ {1, N } is the sum of the sizes of the items packed in bin j (we use the Dirac function δ, δ a,x = 1 if a = x, 0 otherwise), M (Y ) is the number of bins used by the solution Y , k > 1 is a constant which defines how much a solution with equally filled bins is preferred over one in which some bins are rather full and other rather empty. A good value is k = 2 [START_REF] Falkenauer | A hybrid grouping genetic algorithm for bin packing[END_REF].

Experimentation

Hybridization has been tested with both metaheuristics: simulated annealing or kangaroo algorithm (iterated local search).

Originally, the inhomogeneous simulated annealing was used by [START_REF] Metropolis | Equation of state calculations by fast computing machines[END_REF] to simulate the physical annealing in metallurgy. Unfavorable transitions are accepted with a probability e -H(Y ′ )-H(Y )

T

. Simulated annealing converges in probability to the set of optimal solutions if neighborhood system V satisfies the accessibility and reversibility properties [START_REF] Aarts | Simulated Annealing: Theory and Applications[END_REF]. The initial temperature T 0 is chosen such as all the transitions are authorized at the beginning, i.e. e -H(Y ′ )-H(Y )

T 0 ≃ 1, ∀(Y, Y ′ )
according to the algorithm proposed by [START_REF] Aarts | Simulated Annealing: Theory and Applications[END_REF]. The decreasing factor α is computed by α = IterM ax ( Ta T0 ). T a is the latest temperature close to 0. Kangaroo algorithm is an iterated local search. This algorithm consists in a stochastic descent, but if there is no improvement of the current solution after a number of iterations A ≥ |V |.ln(2) [START_REF] Fleury | Méthodes stochastiques et déterministes pour les problèmes NPdifficiles[END_REF], a jump is made. To make this jump, a solution is chosen in a neighborhood system W different from V . Kangaroo algorithm converges in probability to the set of optimal solutions if neighborhood system W satisfies the accessibility property. W consists in applying several times neighborhood system V , it satisfies the accessibility property.

We compared all the possible combinations: choice of the metaheuristic (kangaroo algorithm or simulated annealing), choice of the list algorithm (N F , F F or BF ) and choice of the neighborhood system (P i,j or I i,j ).

All of the referenced papers in the state of the art used the same instances, except [START_REF] Reeves | Hybrid genetic algorithms for bin-packing and related problems[END_REF]. In the instances, the bin capacity is equal to 150 and sizes of items between 20 and 100. Four sizes of problems are used: 120 items, 250, 500 and 1000. For each size, twenty different instances have been created. "u120" to "u1000" define the size of the instance. The results are about the sum of the differences between the optimal solution and the solution found by the considered method for all the instances of the same size. For example, for the twenty instances of size "u120", [START_REF] Falkenauer | A hybrid grouping genetic algorithm for bin packing[END_REF] finds the optimal solutions + 2 bins in total.

Table 2 compares our two best methods SABFP (Simulated Annealing + Best Fit + P i,j ) and KABFP (Kangaroo Algorithm + Best Fit + P i,j ) to the bibliographic ones. SABFP and KABFP use the Best Fit heuristic and the neighborhood system P i,j . At the opposite, our hybridization does not work very well with the list algorithm Next Fit or with the neighborhood system I i,j (which disturbs too much the current solution).

This method gives good results. Our strength is the easy implementation of our proposition. It can be easily used on a lot of applications (resource constrained scheduling, assembly line balancing, multiprocessor scheduling).

u120 +2 0 0 0 0 0 u250 +3 +2 0 0 +1 +2 u500 0 0 0 0 +2 +2 u1000 0 0 0 0 +3 +4

Conclusion

In this paper, we propose a hybridization between a metaheuristic and a list algorithm to solve the bin packing problem. Some methods already exist to solve it and perform very well. The main advantage of our proposition is its intelligibility because it combines two simple well-known methods. This method allows us to work on two different search spaces. This eases the used method. Several reasons justify this encoding scheme: it is not useful to check the admissibility of the solutions, many methods already exist to solve permutation problems, the set used for the metaheuristic is reduced and contains all the optimal solutions. This resolution method used on the bin packing problem is currently applied on real applications such a problem of activities planning and resources assignment. We can also solve more sophisticated models thanks to this encoding scheme. Indeed, more constraints can be added to the list algorithms: incompatibilities between items, between items and bins, precedence.

Hybridization between a metaheuristic and a list algorithm can be used with any metaheuristic. In further work, hybridization will be used with population based metaheuristic. The use of particle swarm optimization is the next step of our approach.

Table 1 .

 1 Analogies between the bin packing problem and the HCT problem.

			Time
												Resource
												Opentime
			1 6	3	4 2	7	11 5 8 10	9 13	12	15 16	14	Bin	number x x Activity's Caption:
	Resource	Radio Scan MRI Radio Scan MRI Radio Scan MRI Radio Scan MRI
	Period	Monday AM Monday PM Tuesday AM Tuesday PM
			Fig. 1. Example of the HCT application
		Bin packing problem	Problem of activities planning and resources assignment
					Item					Activity
	Data					Bin				Couple (resource, period)
				Size of an item			Process time of an activity
	Objective To assign items in bins			To assign activities to periods and resources
	Constraints		Capacity of the bins -			Resources opentime Incompatibility constraint
	Criterion	To minimize the number of used bins	To minimize the number of used couples (resource, period)

Table 2 .

 2 Results of the different methods to solve the bin packing problem

	Prob	[9]	[12]	[8]	[11] SABFP KABFP


Scaling the impact of active topic choice in the Naming Game Flowers Project-team, Inria Bordeaux Sud-Ouest William Schueller, Pierre-Yves Oudeyer

How does language emerge, evolve and gets transmitted between individuals? What mechanisms underly the formation and evolution of linguistic conventions, and what are their dynamics? Computational linguistic studies have shown that local interactions within groups of individuals (e.g. humans or robots) can lead to self-organization of lexica associating semantic categories to words [START_REF] Steels | Crucial factors in the origins of word-meaning[END_REF]. However, it still doesn't scale well to complex meaning spaces and a large number of possible word-meaning associations (or lexical conventions), suggesting high competition among those conventions.

In statistical machine learning and in developmental sciences, it has been argued that an active control of the complexity of learning situations can have a significant impact on the global dynamics of the learning process [START_REF] Gottlieb | Information-seeking, curiosity, and attention: computational and neural mechanisms[END_REF][START_REF] Lopes | Active Learning for Autonomous Intelligent Agents: Exploration, Curiosity, and Interaction[END_REF][START_REF] Kaplan | Computational models in the debate over language learnability[END_REF]. This approach has been mostly studied for single robotic agents learning sensorimotor affordances [START_REF] Oudeyer | Intrinsic motivation systems for autonomous mental development[END_REF][START_REF] Moulin-Frier | Exploration strategies in developmental robotics: a unified probabilistic framework[END_REF]. However active learning might represent an evolutionary advantage for language formation at the population level as well [START_REF] Oudeyer | How evolution may work through curiosity-driven developmental process[END_REF][START_REF] Steels | The Autotelic Principle[END_REF].

Naming Games are a computational framework, elaborated to simulate the self-organization of lexical conventions in the form of a multi-agent model [START_REF] Steels | Language games for autonomous robots[END_REF]. Through repeated local interactions between random couples of agents (designated speaker and hearer ), shared conventions emerge. Interactions consist of uttering a word -or an abstract signal -referring to a topic, and evaluating the success or failure of communication.

However, in existing works processes involved in these interactions are typically random choices, especially the choice of a communication topic.

The introduction of active learning algorithms in these models produces significant improvement of the convergence process towards a shared vocabulary, with the speaker [7, 9, 1] or the hearer [START_REF] Schueller | Active control of complexity growth in naming games: Hearer's choice[END_REF] actively controlling vocabulary growth.

We study here how the convergence time and the maximum level of complexity scale with population size, for three different strategies (one with random topic choice and two with active topic choice) detailed in table 1. As for the version of the Naming Game used in our work, the scenario of the interaction is described in [START_REF] Schueller | Active control of complexity growth in naming games: Hearer's choice[END_REF]. Vocabulary is updated as described in the Minimal Naming Game, detailed in [START_REF] Wellens | Adaptive Strategies in the Emergence of Lexical Systems[END_REF]. In our simulations, we choose to set N = M = W , where N is the population size, M the number of meanings, and W the number of possible words. The computed theoretical success ratio of communication is used to represent the degree of convergence toward a shared lexicon for the whole population. A value of 1 means that the population reached full convergence. Complexity level of an individual lexicon is measured as the total number of distinct associations between meanings and words in the lexicon, or in other words: memory usage.

We show here (see figures 2,3) that convergence time and maximum complexity are reduced with active topic choice, a behavior that is amplified as larger populations are considered. The minimal counts strategy yields a strictly minimum complexity (equal to the complexity of a completed lexicon), while converging as fast as the success threshold strategy. Further work will deal with other variants of the Naming Game (with different vocabulary update, population replacement, and different ratio for N , M and W ). For the moment only the hearer's choice scenario is studied, because of its high robustness to changes in parameter values for the different strategies [START_REF] Schueller | Active control of complexity growth in naming games: Hearer's choice[END_REF].

Figure 1 :

 1 Figure 1: Strategies: Choice of meaning m. Both active strategies use a parameter (α and n), which is each time chosen optimal in our simulations.

Figure 2 :Figure

 2 Figure 2: Strategy comparisons, in terms of convergence time (theoretical success ratio) and complexity level (memory usage). In this case, the hearer is the one choosing the topic. M=W=N=40, averaged over 8 trials


Woodrow L Shew

Yoann Gasteuil

Mathieu Gibert

Pascal Metz

Jean-François Pinton

An instrumented tracer for Lagrangian measurements in Rayleigh-Bénard convection

Keywords: numbers: 47, 80, -v (Instrumentation for fluid flows); 44, 27, +g (Convective heat transfer)

We have developed novel instrumentation for making Lagrangian measurements of temperature in diverse fluid flows. A small neutrally buoyant capsule is equipped with on-board electronics which measure temperature and transmit the data via a wireless radio frequency link to a desktop computer. The device has 80 dB dynamic range, resolving milli-Kelvin changes in temperature with up to 100 ms sampling time. The capabilities of these "smart particles" are demonstrated in turbulent thermal convection in water. We measure temperature variations as the particle is advected by the convective motion, and analyse its statistics. Additional use of cameras allow us to track the particle position and to report here the first direct measurement of Lagrangian heat flux transfer in Rayleigh-Bénard convection. The device shows promise for opening new research in a broad variety of fluid systems.

I. INTRODUCTION

Scalar mixing in turbulent flows plays a crucial role in uncountable natural, medical, and industrial systems: spread of pollutants by wind and water; oceanic and atmospheric thermal convection; the life cycles of plankton; mixing in combustion engines and chemical reactors. A natural approach to understanding these examples is to measure the trajectories of the pollutant molecules, warm fluid elements, planktonic organisms, and chemical species, respectively, as well as the properties of the flow along these trajectories. This Lagrangian approach to turbulent mixing has been advanced significantly with numerical and theoretical models [1], but experimental works are rare due to the difficulties in (1) distinguishing the identity of a fluid particle along its trajectory, and (2) making measurements along these paths . A few recent experimental studies have successfully performed resolved measurements of the trajectories of small solid tracer particles in turbulence [2,3,4,5]. Atmospheric research groups [START_REF] Gifford | it Month[END_REF] and oceanographers routinely employ meter-sized Lagrangian floats to study large scale flows [7]. Lagrangian probes have a distinct advantage over Eulerian probes which record at fixed positions in the flow: the measurements provide information about local physical processes as experienced by the fluid particle.

With the aim of measuring Lagrangian scalar quantities in well-controlled laboratory flows, we have developed a miniature, wireless, neutrally-buoyant instrument, dubbed a smart particle. We present temperature measurements obtained with this device in turbulent thermal convection. Similar instruments have been used in medical applications [8], but to our knowledge we report the first such measurement device in the context of fluid dynamics. Simultaneous measurements of temperature and position have been made before in convection experiments, most recently by tracking optically the motion of microspheres containing thermochromic liquid crystal (TLC) [9]. The shape evolution of thermal plumes very close to the thermal and hydrodynamic boundary layers was quantified, but this method is not capable of tracking individual particles over large distances. Our smart particle measurements complement those of TLC particles by vastly improving temperature and time resolution as well as allowing observation of very long particle trajectories, though the smart particles are too large to investigate the flow in the boundary layers.

II. DEVICE DETAILS

The details of the instrument are describe in the following five subsections. First we present a block diagram and general description of the whole system. Then, the radio frequency (RF) data transfer is described in detail. Next, we focus on the power management system. We then discuss the measurement and processing of temperature data and end with details about the position measurement technique.

A. Overview

The smart particle consists of a D = 21 mm diameter capsule containing temperature instrumentation, an RF emitter, a battery, and an on-off switch -illustrated in Figs. 1(a,b).

A resistance controlled oscillator is used to create a square wave whose frequency depends on the temperature of several thermistors. This square wave is used directly to modulate the amplitude of the radio wave generated by the RF emitter. The entire mobile circuit is powered with a coin cell battery and may be put in a low power standby mode using an externally applied magnetic field.

The stationary parts of the system include an antenna, an RF receiver, 2 RF amplifiers, a high speed data acquisition system, and a desktop computer running Labview (Fig. 1a).

The broad-band radio frequency amplifiers increase the voltage amplitude of the signal by a factor of 26 dB. The receiver is carefully tuned to demodulate the signal produced by the emitter. The receiver outputs a square wave identical to that generated by the resistance controlled oscillator. The frequency of this square wave, and hence temperature, is recovered on-the-fly using a Labview algorithm. In addition, the particle trajectory is recorded with a digital video camera, resulting in synchronous measurements of the position and temperature of the particle as it is carried about by the fluid.

B. RF data link

The radio frequency emitter is a MAX7044 (from Maxim Integrated Products), which employs on-off keying (OOK) amplitude modulation. The RF carrier frequency is 315 MHz.

The MAX7044 expects a digital modulating signal with a baud rate from 0 to 100 kHz. We implement an 8 mm diameter, 8-turn coil emitter antenna with about 200 nH inductance and 4 Ω resistance. We use a split-capacitor impedance matching network to maximize the efficiency since the MAX7044 is optimized for a 125 Ω antenna. The emitter draws an average of 5 mA and requires 2.1-3.6 V from the battery in normal operation. The emitter consumes 10 to 100 times more power than any of the other on-board components.

On the receiving end we use the MAX1473 superheterodyne receiver, which demodulates OOK data and is designed to work with the MAX7044. The receiving antenna is a 315 MHz 1/4 wave whip (Linx Technologies, Inc., ANT-315-CW-HD). Between the antenna and the receiver are two low noise amplifiers each with a gain of 13 dB at 315 MHz (MAX2640).

C. Power management

The size of the instrumentation capsule is minimized so that it capable of probing as small a spatial scale as possible. The component of the system which limits the size of the capsule most is the battery. It is a CR1616 lithium coin cell (Panasonic), which is 16 mm in diameter and 1.6 mm thick. This battery can supply the necessary power for about 3 hours. The circuit is also equipped with a magnetic field triggered switch so that the instrumentation may be turned off when we are not ready to acquire data. The switch is composed of a TLE4913 low power hall switch (Infineon Technologies) and a NL17SZ74 single D flip-flop (ON Seminconductor). The hall switch outputs a high logic level when in the presence of a sufficiently large magnetic field. Feeding this output into the CP pin of the flip-flop while D is connected to Q we have a "push-button" switch, which is operable with a hand-held permanent magnet from a distance of several centimeters. When the switch is in the "off" position, the circuit consumes less than 100 µA. The hall switch and the flip-flop respectively require 2.4-5.5 V and 1.65-5.5 V from the battery.

D. Temperature detection

The system measures the spatially averaged temperature around the smart particle body. This is accomplished using four thermistors to set the frequency of a LMC555 timer/oscillator (National Semiconductor) operating in astable mode. The thermistors protrude from the capsule wall by about 0.5 mm and are spaced evenly around its middle.

The LMC555 outputs a square wave at logic levels with a period 1/f = (R 1 + R 2 + 2R 3 + 2R 4 )C/1.44, where R i are the resistances of the four thermistors, and C is 47 pF. We employ 0.8 mm, 230 kΩ thermistors (Epcos B57540G0234) with a response time of about 0.06 s in water, which is faster than the fastest temperature time scales of the flow we study. In the range of temperature 26 -34 • C, the frequency of the square wave is in the range 22 -26 kHz; the sensitivity is 513 Hz/ • C. The relationship between temperature and frequency is linear within 2 percent. The LMC555 requires about 100 µA at a supply voltage between 1.5 and 12 V.

The RF receiver recovers the square wave signal, which is then recorded with a high-speed, 14 bit, analog-to-digital converter (ADC) (National Instruments 5621 in a PXI system).

Running on a desktop PC, Labview is used to control the data acquisition. The frequency of the demodulated square wave is computed on-the-fly using a standard Labview library.

Each measurement of frequency is computed from 100 ms of the square wave, i.e. about 3000 periods, sampled by the ADC at 10 MHz. The resulting measurement resolution is about ±2 Hz, which is ±4 mK when converted to temperature. The sampling rate is about 10 Hz. With maximum flow velocities in the range 1-2 cm/s and a particle size of 21 mm, we are oversampling the dynamics by a factor of order 10.

E. Position measurement

In order to measure the smart particle position, we use a standard webcam, interfaced with a desktop computer. A uniform well-illuminated image background is achieved with a back-lit sheet of frosted glass. We use Matlab scripts to control the camera and process the video data. First, each video frame is converted into a 2D binary array, using an adaptive threshold. Then, the particle position is extracted using an image recognition algorithm.

The effective sample frequency is around 5 Hz. The resolution of the camera is 640 × 480 pixels, so that the particle position is determined with 0.1 mm precision.

III. MEASUREMENTS IN RAYLEIGH-B ÉNARD CONVECTION A. Convection apparatus

Our experimental setup, shown in figure 1c, is a traditional rectangular Rayleigh-Bénard cell with height H = 40 cm and section 40 cm × 10 cm. The fluid is water and the walls of the vessel are 25 mm thick PMMA. The upper plate of the cell is temperature regulated by a chilled water bath. The bottom plate is heated by 5 resistors, regularly spaced. Complete experimental details can be found in [10].

In the results reported here, the power input is P = 230 W, and the upper plate is regulated to T up = 19 • C, corresponding to a temperature difference between the top and bottom plates of ∆T = 20.3 • C. As a result, the Rayleigh number is

Ra = gβ∆T H 3 νκ = 3.07 × 10 10 , (1)
where g is acceleration due to gravity, β = 2.95 × 10 -4 K -1 is the thermal expansion coefficient of water and ν = 8.17 × 10 -7 m 2 s -1 , κ = 1.48 × 10 -7 m 2 s -1 its viscosity and thermal diffusivity (values are given for a mean temperature equal to 29.1 • C). The Nusselt number, measured as the total heat flux normalized by κ∆T /L, is Nu = 167.9 ± 0.2. Under these conditions, the convective regime is fully turbulent [10,13] and the mean flow is a steady, system-sized, single convection roll with a rotation period of about 100 s. The characteristic thickness of the thermal boundary layer is ℓ T ∼ 1 2 HNu -1 ∼ 1.2 mm and that of the hydrodynamic boundary layer is ℓ U ∼ ℓ T (ν/κ) 1/3 ∼ 2 mm. Thus, the particle is too large to penetrate the boundary layers.

B. Temperature measurement

The particle and fluid density are carefully matched. This is achieved by initially adjusting the particle mass to within 1 percent of ρ f πD 3 /6, where ρ f is the density of water. Then, to obtain neutral buoyancy within 0.05 percent, ρ f is finely adjusted by the addition of small amounts (about 1000 ppm) of pure glycerol, which has a density 20 percent greater than water. The particle is inevitably slightly lighter than the cool fluid near the upper plate and slightly heavier than the warm fluid near the bottom plate. Nonetheless, the particle explores all regions of the vessel without a clear bias as can be seen in figure 2b.

We show in figure 3a, a time series of the temperature θ(t) recorded by the particle, during the trajectory shown in figures 2b,c. Apparent in the time series is a nearly periodic, large amplitude fluctuation, which reflects the particle's entrainment in the mean flow. This periodicity, as well as the smaller amplitude turbulent fluctuations are made more clear in the power spectrum shown in figure 3b. The spectrum also reveals a range of time scales, corresponding to frequencies 0.016 < f < 0.230 Hz, which is consistent with a self-similar θ2 ∼ f -α scaling, with an exponent α close to -2. This feature is in sharp contrast with the Eulerian temperature spectrum obtained when the particle is constrained to remain at fixed location in space. In that case, we have verified that the spectrum shows an f -7/5 scaling range. This value is in agreement with other experimental Eulerian studies of convection (e.g. [11]), provided the frequency spectrum be interpreted as a spectrum in space, which is plausible considering the persistent mean flow (i.e. Taylor's hypothesis). Bolgiano-Obhukov scaling also leads to a k -7/5 wavenumber spectrum for temperature variations in real space.

By contrast, the spectral behavior found here for the moving particle is reminiscent of velocity data for Lagrangian tracers in turbulent flows. Indeed when fluid turbulence is fully developed, a well-established feature of Lagrangian dynamics and Kolmogorov's theory is that the Lagrangian velocity spectrum should have an f -2 inertial range [3,12] -as we have verified also verified here from our independent measurement of the particle position.

The upper cut-off frequency apparent in figure 3b around (∼ 0.3 Hz) corresponds to the characteristic time of motion of the particle across a distance equal to its diameter D: the mean speed of the large scale roll being ≈ 1.6 cms -1 . This is also in agreement with Lagrangian measurements made using density matched tracers: the velocity spectrum was found to follow the expected Lagrangian behavior up to a frequency set be the particle's size and the flow characteristic velocity scale [3]. These interpretations are consistent with qualitative observations using Schlieren visualization, which reveal that temperature plumes of size D or larger fully entrain the smart particle, while smaller plumes do so only partially.

Finally, as shown in figure 3c, the histogram of temperature is non-Gaussian. The non-Gaussian character of the PDF is in agreement with Eulerian measurements using fixed temperature probes [13]. Other recent experimental studies have also shown that the distribution of intense temperature plumes in the form of mushrooms has non Gaussian tails [9].

We note that the asymmetry of the PDF is probably due to imperfect density matching between the fluid and the particle, so that it tends to stay slightly longer near the bottom plate.

C. Heat flux measurement

With the assumption that the particle may indeed act as a Lagrangian tracer in the convective flow, it is natural and interesting to discuss the heat carried by the flow in terms of the temperature measured by the particle. To this end, we define an instantaneous Lagrangian Nusselt number as:

Nu L (t) = 1 + L κ∆T θ ′ (t) • v z (t) , (2)
where θ ′ (t) = θ(t) -θ is the particle temperature variation from its time averaged temperature θ, and v z (t) its vertical velocity. Integrating this quantity over all the fluid particles in any horizontal plane recovers the traditional Nusselt number.

The time series of Nu L is shown in figure 4a. Comparing this time series with the trajectory in figure 2(c), we see that the heat transfer intermittently spikes to very large values often as the particle moves away from the end plates and mixes with fluid at intermediate heights in the vessel. The power spectrum in figure 4b shows that the periodicity of the large scale convection roll is diminished and strong fluctuations occur over a broader range of (slow) scales. The spectrum shows a fast, f -4 decrease in the same frequency range that the temperature showed f -2 . As discussed in the previous section, this scaling is consistent with our understanding of velocity spectra (ṽ

2 ∼ f -2 ) resulting in Ñu L 2 ∼ θ2 ṽ2 ∼ f -4 .
The PDF of Nu L , figure 4c is skewed toward positive values, as expected because coherent convective motion are associated with either hot fluid rising or cold fluid sinking, so that in each case θ ′ • v z > 0. The much less probable events with θ ′ • v z < 0 correspond, for instance, to the rise of the particle when it is colder than its environment. This is unlikely but not impossible as the particle may be trapped in the swirls of a turbulent plume (e.g.

the flow in the "cap" of the mushroom shaped plume is opposite the flow in the "stem").

The most probable value of the PDF is zero, indicating the particle spends a large amount of time at the mean fluid temperature in the bulk of the cell. The mean value, Nu L , is more surprising: at 335.4 it is roughly twice the global, Eulerian, Nusselt value computed from power input and velocity differences. Such an increased mean may be due to the fact that the particle does not sample the flow uniformly, but may instead get more advection from intense thermal plumes. The dramatically non-Gaussian form of the PDF as well as scale-by-scale statistics of the local flux requires further study. This analysis will be reported elsewhere.

IV. CONCLUSIONS

We report on new instrumentation for making fluid mechanics measurements in the reference frame of particles passively advected by flow motion. These smart particles show promise for a fresh perspective in turbulence research as well as two phase flows. The rapid development of MEMS and microfluidic components, which may be incorporated in a smart particle, opens a diverse range of potential applications including granular flows and reacting flows in chemical and biological systems.

We demonstrate the capabilities of smart particles in the simple case of Lagrangian temperature measurements in thermal convection. We report several original findings. First, we observe f -2 power law scaling behavior for the temperature spectrum, which suggests the temperature acts as a passive scalar advected by fully developed, Kolmogorov-like, turbulence. This result supports the hypothesis that outside the boundary layers, where buoyancy sets the fluid into motion, the temperature is passively mixed in the turbulent bulk. (e.g. [14,15,16]). Strong temporal intermittency in Lagrangian heat transport is revealed in the extremely heavy-tailed probability distribution functions, while the fact that the mean Lagrangian heat transport is much higher than the Eulerian average suggests strong spatial inhomogeneity as well. Further and deeper investigations of these features will be presented soon elsewhere.

FIG. 1 :FIG. 3 :

 13 FIG. 1: (a) Block diagram of measurement system. (b) Photo of the smart particle before closing the capsule.

Acknowledgements

The authors have had fruitful discussions with Francesca Chillá and Bernard Castaing. This work has been supported by C.N.R.S. and Emergence Contract No. 2005-12 from the French Rhône-Alpes Region.


J Senzier

P S Luo

H Courtois

Combined scanning force microscopy and scanning tunneling spectroscopy of an electronic nano-circuit at very low temperature

Keywords: numbers: 07.79.-v, 74.78.Na, 07.20.Mc

We demonstrate the combination of scanning force microscopy and scanning tunneling spectroscopy in a local probe microscope operating at very low temperature (60 mK). This local probe uses a quartz tuning fork ensuring high tunnel junction stability. We performed the spatially-resolved spectroscopic study of a superconducting nano-circuit patterned on an insulating substrate. Significant deviations from the theoretical prediction are observed.

Scanning Tunneling Microscopy (STM) is a powerful tool for imaging surfaces down to the atomic scale. It also allows to measure the electronic Local Density Of States (LDOS) with an accuracy of 2k B T given by the thermal smearing. This so-called Scanning Tunneling Spectroscopy (STS) technique has been used in many fields of condensed matter physics. Cryogenic environment is a key to reach the best spectroscopic energy resolution and access the fundamental electronic properties of quantum mechanics-driven nanostructures. Nevertheless, the application of STS in the field of mesoscopic devices and nano-circuits is still in its infancy. The main reason is that a STM needs a fully metallic surface to be operated safely, which is not the case of nano-circuits patterned on insulating substrates.

On the other hand, the Atomic Force Microscopy (AFM) technique [1] is capable of imaging any kind of surface with an excellent resolution, although no information can be gained on the electronic LDOS. A combination of both modes of microscopy in a versatile instrument, namely a cryogenic AFM-STM with the STS capability, is therefore of particular interest. As the same tip is used for both microscopy, a metallic nano-circuit can be located with the force microscopy before being probed in the tunneling mode. The local spectroscopy of the nano-structure is then possible like in an usual STS experiment.

The STS is a very demanding technique in terms of junction stability. The use of a metallized cantilever as the force sensor is therefore prohibited, since its natural flexibility would prevent a sufficient tunnel junction stability. An alternative consists in the use of a quartz tuning fork (used in watches), which was proposed in the framework of Scanning Near-field Acoustic Microscopy [2] and since then applied in many kinds of local probes [3,4,5,6]. A tuning fork-based AFM probe brings the advantage of its natural stiffness at low frequency, which is a prerequisite for the STS. Moreover, the oscillation of a tuning fork can be detected with electrical means, avoiding any optical setup. Finally, a tuning fork dissipates a very small amount of power. This makes the tuning fork-based AFM the choice candidate for AFM-STM experiments at very low temperature.

In this letter, we report on the characteristics and performances of a combined AFM-STM operating at very low temperature down to 60 mK in a dilution refrigerator. We demonstrate its application to the study of the local electronic properties of a superconducting submicron wire patterned on a sapphire substrate. Significant deviations from the BCS prediction are observed, which are related to the very small thickness of the wire.

Our AFM-STM is an evolution of a home-made very low temperature STM [7,8]. The microscope is thermalized on the top plate of an upside-down dilution refrigerator with a base temperature of 60 mK. Every electrical connection entering the microscope's hermetic calorimeter is now filtered with radio-frequency filters made of 20 cm-long high capacitance micro-coaxial wires [9].

We are using commercial quartz tuning forks resonating at 32768 Hz. To mount a probe, we first cut the tuning fork packaging just above the fork prongs end. Keeping the tuning fork box avoids possible damage to the tuning fork itself and provides a good electrical shield for the electrical measurements. Then we glue an electrochemically-etched tungsten tip with a small amount of conductive epoxy at the end of the top prong, see Fig. 1 inset. The metallic contact between the tip and one tuning fork electrode enables us to use the latter as the tunnel current collector while the other electrode is used for the AFM signal measurement. We chose to mount the tip perpendicular to the tuning fork prongs, so that tip-sample interaction forces are probed, not shear forces.

After fabrication, the tuning fork probe is fixed on the microscope scanner tube. It is excited mechanically by adding a small a.c. component to the high voltage applied to the tube's inner electrode. Although the tube response is attenuated by about two decades in amplitude in the relevant frequency range (30-32 kHz), this method avoids the use of an additional piezo-electric element and enables us to measure simultanously the tunnel current and the AFM signal. Compared to a bare tuning fork, the resonance frequency shift and the quality factor of a tuning-fork probe depend strongly on the amount of glue and on the geometry of the tip gluing. Figure 1 displays a typical frequency response of an AFM-STM probe at cryogenic temperature. The resonance frequency is shifted down by about 700Hz while the quality factor of about 50000 remains quite good.

As the tip approaches the sample surface, the tuning fork oscillation is influenced by the tip-sample interaction forces. In the small amplitude limit, the resonance frequency is shifted proportionally to the force gradient [1,10]. Figure 2a shows a typical dependence of the frequency shift ∆f as a function of the tip-sample distance. The zero distance reference has been defined with an estimated accuracy of 0.3 nm as the position where a tunnel resistance of 1GΩ is reached (at a 0.5 Volt bias). The oscillation amplitude of 0.8 nm is close to the small amplitude limit, so that the resonance frequency shows a clear negative shift regime and exceeds -1 Hz at a distance of about 3 nm. For the sake of operation reliability, we chose to operate in the positive shift region which features a steep evolution of the frequency shift as a function of distance of the order of 2 Hz per nanometer.

As for AFM imaging, we use a Phase Locked Loop electronics that maintains the excitation frequency precisely at the resonance, while an adjustable gain amplifier also maintains the oscillation amplitude constant. In this Frequency Modulation mode (FM-AFM), the measured frequency shift feeds the distance regulation electronics that operate with a setpoint of 0.15 to 0.5 Hz. As for test images, Fig. 2b shows an image of a reference sample made of a silanized silica surface with adsorbed colloidal Au nano-particles of 5 nm diameter. Dots appear with a height of 5 nm and a full width at half maximum of about 35 nm. This apparent size increase shows that our lateral resolution is limited by a tip radius of about 15 nm. In the vertical direction, we achieve routinely atomic resolution. As an example, the Fig. 2c image of a sapphire R-plane substrate annealed for 1h in air at 1100 • C displays regular atomic steps (step height of 0.34 nm). The measured corrugation on a given atomic plane is 0.1 nm, which demonstrates the excellent vertical resolution of the set-up.

We have achieved very low temperature AFM-STS experiments on submicron Nb wires patterned on such a sapphire substrate. An epitaxial Nb layer of 15 nm was deposited in UHV at 500 • C and covered by a thin Si (5 nm) capping layer [11]. We used e-beam lithography and Reactive Ion Etching (RIE) to pattern a Nb meander line. Our process provides a clean Nb surface, although a few small local defects may remain. Figure 3a shows a 3D representation from an AFM image of a sample at T = 100 mK. A Nb wire with a width of about 300 nm and a height of 8 nm is imaged, in agreement with expectations. The observed r.m.s. corrugation on the wire's surface is about 0.8 nm. After taking several images, we moved the probe over the wire and switched the microscope to the STM mode. At this moment, the tuning fork is no longer excited and the input of the distance regulation is fed with the tunnel current signal.

We performed local spectroscopy measurements by acquiring direct I-V characteristics that were subsequently numerically differentiated in order to access the LDOS. A series of spectroscopies was acquired along the arrow displayed on Fig. 3b and with a 5 nm displacement between every spectroscopic measurement. In this case, displacement and spectroscopic measurements were made with a constant tip-sample distance corresponding to a 50 M Ω tunnel barrier. The tunnel resistance could be decreased down to 10 M Ω while still keeping a good junction stability. The noise level of the I-V characteristics is due to both the vibration of the tip-sample distance and the measurement noise. The exponential dependence of the tunnel current I with the distance z gives the formula:

dI I = - √ 2mW dz, (1)
m being the electron mass and W the metal work function of about 4 eV. Neglecting the effect of the measurement noise, the measured current noise level of below 0.5% gives then an upper limit for the peak-peak tip vibration of 0.5 pm. This demonstrates the high stability of the tuning fork-based AFM-STM probe.

The Figure 3b spectra display a clear superconducting gap with a width of 2∆=2.32 meV which is slightly below the gap of bulk Nb (3.0 meV) but consistent with the measured critical temperature of 7.4 K. The expected superconducting coherence length is 9.8 nm. The third spectrum shows slightly smaller coherence peaks than the others. This behavior is presumably related to a local defect that weakens locally the superconductivity. The other spectra are very close to each other and show a smearing that cannot be accounted for by the measured sample temperature (100 mK).

As an energy resolution test, we performed AFM-STM spectroscopy experiments on thick Nb films. We obtained spectra that could be fitted by the Bardeen-Cooper-Schrieffer (BCS) theory and an effective temperature close to 200 mK, in agreement with our recent STS experiments [8]. We therefore conclude that our measurements are not affected by thermal smearing or noise and give an accurate measure of the LDOS of the Nb surface. The LDOS thus features smeared peaks and a significant sub-gap density, in clear deviation from the BCS theory. This behavior appears to be linked to the small thickness of the film as the same behavior was observed on unprocessed films of similar thickness. An inverse proximity effect due to the presence of a metallic and nonsuperconducting Nb oxide layer at the sample surface or at the sapphire-Nb interface is a possible explanation for the observed behaviour which calls for further investigation.

In conclusion, we have developed a very low temperature local probe combining Force Microscopy and Scanning Tunneling Spectroscopy. The high rigidity of the tuning fork used as a force sensor enables us to obtain highly stable measurement conditions as demonstrated by a first spectroscopy experiment on a submicron superconducting wire. This combined AFM-STM technique opens wide perspectives in the study of quantum nano-circuits. This set-up can be used for Scanning Tunneling Potentiometry of a current-biased device. By using a superconductive tip on a metallic sample, out-ofequilibrium effects can be investigated through measurements of the local energy distribution function [12].

FIG. 1 :

 1 FIG.1:(Color online) Plot of the phase (dotted line) and amplitude (full line) of the AFM-STM probe response close to its resonance. The measurement is performed at 4 K with a mechanical excitation through the scanner tube. Inset: Photograph of the probe made of a tungsten tip glued with silver epoxy on one electrode of the quartz tuning fork. The cylindrical tuning fork packaging (length 8 mm) was cut just above the fork prongs prior to gluing.

FIG. 2 :

 2 FIG. 2: (Color online) (a) Frequency shift ∆f as a function of the tip-sample distance on a Nb-Au film at 150 mK. (b) 0.7 × 0.7µm 2 very low temperature AFM image of a silica surface with adsorbed Au nano-particles of 5 nm diameter: ∆f = 0.4Hz and T = 100 mK, z-scale is 6 nm. (c) 1600 × 300 nm 2 AFM image of atomic steps on an annealed R-plane sapphire wafer: ∆f = 0.2Hz and T = 90 mK, z-scale is 3 nm.

FIG. 3 :

 3 FIG. 3: (Color online) (a) 140 × 950 nm 2 AFM image of a 300 nm-wide Nb wire patterned on a sapphire substrate at 100 mK. Frequency shift is 0.15Hz, tip oscillation amplitude is 1 nm, scanning speed is 175 nm/s. (b) Differential conductance spectra acquired at 100 mK in units of the high bias conductance equal to 50 MΩ. The spectroscopies from bottom to top were acquired along a 25nm-long displacement of the tip on the Nb wire. The arrow superposed on the AFM image gives the position, length and direction of the spectroscopic scan.

We thank the CRTBT technical staff, and especially A. Gerardin, for their various contributions to the design and construction of the microscope set-up. We acknowledge preliminary work by A. Gupta and L. Crétinon and useful discussions with V. Bouchiat, C. Delacour, N. Dempsey, B. Grévin, K. Hasselbach and P. Joyez. Samples were prepared at the Nanofab facility at CNRS Grenoble. This work was funded by the EU NMP2-CT-2003-505587 'SFINx' STREP and by ACN 'AFM-STM-NME' project.