Carla Juvin
email: carla.juvin@laas.fr

Laurent Houssin
email: laurent.houssin@laas.fr

Pierre Lopez
email: pierre.lopez@laas.fr

Logic-based Benders decomposition for the preemptive Flexible Job-Shop Scheduling Problem

Keywords: Flexible job-shop scheduling, preemption, Benders decomposition, mixed-integer programming, constraint programming

In this paper, we focus on exact methods to solve the preemptive Flexible Job-Shop Scheduling Problem with makespan and total completion time minimisation objective functions. Mathematical and constraint programming models enable the resolution of this problem for small instances. However, as an NP-hard problem, the cost of solving grows rapidly when considering larger instances. In this regard, we propose a logic-based Benders decomposition that relies on an efficient branch-and-bound procedure to solve the subproblem representing a pure (non-flexible) preemptive job-shop scheduling problem. Computational experiments are carried out and show the very good performance of our proposals.

Introduction

The job-shop scheduling problem (JSSP) is a well studied and NP-hard problem [START_REF] Garey | The complexity of flowshop and jobshop scheduling[END_REF]. In the JSSP, a set of jobs are to be processed on a set of machines. Each job is composed of a sequence of operations that must be processed on machines with given processing time in a given job-dependent order, and each machine can process only one operation at a time. An extensive literature has been devoted to the JSSP, including the consideration of various additional constraints and different objective functions, even if makespan minimisation is mostly studied [START_REF] Jain | Deterministic job-shop scheduling: Past, present and future[END_REF]. Nevertheless, very few works consider the job-shop problem with preemption. Le Pape and Baptiste [START_REF] Pape | Resource constraints for preemptive job-shop scheduling[END_REF] were the first to solve the preemptive job-shop scheduling problem (pJSSP) using constraint programming. Then, genetic algorithm and fuzzy logic are used in Yun [START_REF] Yun | Genetic algorithm with fuzzy logic controller for preemptive and nonpreemptive job-shop scheduling problems[END_REF]. To our knowledge, Ebadi and Moslehi are among the latest authors to have solved the problem to optimality. In particular, they proposed a MILP model [START_REF] Ebadi | Mathematical models for preemptive shop scheduling problems[END_REF] and an efficient branch-and-bound procedure [START_REF] Ebadi | An optimal method for the preemptive job shop scheduling problem[END_REF].

The flexible job-shop problem (FJSSP) is a generalisation of the JSSP in the sense that, for each operation, there exists a set of eligible machines. This makes the problem more difficult to solve, as it consists of both a machine allocation and a sequencing problem. In the FJSSP literature, the most often studied optimisation criterion is the makespan minimisation; see for example the survey of Chaudhry and Khan [START_REF] Chaudhry | A research survey: review of flexible job shop scheduling techniques[END_REF]. Due to the complexity of the problem, many heuristics and metaheuristics have been developed, e.g., Tabu search [START_REF] Shen | Solving the flexible job shop scheduling problem with sequence-dependent setup times[END_REF][START_REF] Hurink | Tabu search for the job-shop scheduling problem with multi-purpose machines[END_REF], genetic algorithms [START_REF] Pezzella | A genetic algorithm for the flexible job-shop scheduling problem[END_REF][START_REF] Xianzhou | An improved genetic algorithm for dual-resource constrained flexible job shop scheduling[END_REF] or simulated annealing [START_REF] Najid | A modified simulated annealing method for flexible job shop scheduling problem[END_REF][START_REF] Yazdani | Two metaheuristic algorithms for the dual-resource constrained flexible job-shop scheduling problem[END_REF]. With the improvement of the performance of solvers, exact methods have also been designed, including a majority of mathematical models [START_REF] Özgüven | Mathematical models for job-shop scheduling problems with routing and process plan flexibility[END_REF][START_REF] Ziaee | A mixed integer linear programming model for flexible job shop scheduling problem[END_REF]. Meng et al. [START_REF] Meng | Mixed-integer linear programming and constraint programming formulations for solving distributed flexible job shop scheduling problem[END_REF] compared four mixed-integer linear programming models and one constraint programming model. They showed that the constraint programming model outperforms all other studied exact methods. Numerous variants of the FJSSP exist and have been also studied in the literature, e.g., including sequencedependent setup times [START_REF] Shen | Solving the flexible job shop scheduling problem with sequence-dependent setup times[END_REF] or workers [START_REF] Kress | Mathematical models for a flexible job shop scheduling problem with machine operator constraints[END_REF].

Studies on the preemptive flexible job-shop scheduling problem (pFJSSP) are scarce: three metaheuristics are presented in Zhang and Yang [START_REF] Zhang | Flexible job-shop scheduling with flexible workdays, preemption, overlapping in operations and satisfaction criteria: An industrial application[END_REF], while Jansen et al. [START_REF] Jansen | Approximation algorithms for flexible job shop problems[END_REF] proposed several approximation algorithms for the FJSSP including one for the particular case of the pFJSSP. To the best of our knowledge, no exact method is reported in the literature to solve this problem. The purpose of the present article is to develop and compare several exact methods for the pFJSSP with makespan minimisation, namely: Mixed-Integer Linear Programming (MILP), Constraint programming (CP), and Logic-Based Benders decomposition (LBBD). We also extend these three methods to a second optimisation criterion: the total completion time minimisation.

LBBD was introduced by Hooker et al. [START_REF] Hooker | Verifying logic circuits by Benders decomposition[END_REF] in the context of logic circuit verification and Hooker [START_REF] Hooker | Logic based methods for optimization: Combining optimization and constraint satisfaction[END_REF] formalised the concept. This approach has been applied to a large variety of scheduling problems, especially those including assignment decisions to make: Hooker and Ottosson [START_REF] Hooker | Logic-based Benders decomposition[END_REF] tackle a parallel-machine problem with release and delivery dates with the objective to minimise processing costs, Hooker [START_REF] Hooker | Planning and scheduling by logic-based Benders decomposition[END_REF] addresses the cumulative scheduling problem, while Tan and Terekhov [START_REF] Tan | Logic-based Benders decomposition for two-stage flexible flow shop scheduling with unrelated parallel machines[END_REF] solve the flexible flow shop problem with an LBBD algorithm. Naderi and Roshanaei [START_REF] Naderi | Critical-path-search logic-based Benders decomposition approaches for flexible job shop scheduling[END_REF] also proposed an LBBD scheme to solve the FJSSP without preemption.

The remainder of the paper is organised as follows. In the next section, the preemptive flexible job-shop scheduling problem is formally defined; MILP and CP models for the pFJSSP with makespan minimisation are also presented. In Section 3, we propose an LBBD scheme based on the use of an efficient branch-and-bound procedure for solving a pure scheduling subproblem. Computational experiments are carried out in Section 4 for two objective functions: the minimisation of the makespan and the minimisation of the total completion time. We draw a conclusion in Section 5.

Problem definition and modelling

An instance of the pFJSSP is defined as a set of jobs J and a set of machines M. A job is not subject to an initial release date. Each job i ∈ J consists of a sequence of n i operations. The j th operation O i,j ∈ O i of a job i must be performed by one of the machine from the set of eligible machines M i,j ⊆ M. Let p i,j,m denote the processing time of operation O i,j that is processed on machine m ∈ M i,j . Each machine can process at most one operation at a time and preemption is allowed: the processing of operations can be interrupted and resumed later without penalty. Although an operation can be interrupted (preemption), it is assumed that it must be fully processed by one and the same machine (no migration).

Notations and definitions.

J

Set of jobs M Set of machines

n i Number of operations in job i (i ∈ J ) O i Set of operations in job i (i ∈ J ) O i,j j th operation of job i (i ∈ J , j ∈ {1, . . . , n i }) M i,j Set of eligible machines for operation O i,j (i ∈ J , O i,j ∈ O i ) I m
Set of operations that can be processed by machine m (m ∈ M)

p i,j,m Processing time of operation O i,j on machine m (i ∈ J , O i,j ∈ O i , m ∈ M i,j ) p min i,j Shortest processing time of operation O i,j , p min i,j = min m∈M i,j p i,j,m (i ∈ J , O i,j ∈ O i ) r min i,j Shortest release date of operation O i,j , r min i,j = j ′ <j p min i,j ′ (i ∈ J , O i,j ∈ O i ) q min i,j Shortest delivery time of operation O i,j , q min i,j = j ′ >j p min i,j ′ (i ∈ J , O i,j ∈ O i )
Example 1. Consider a pFJSSP with 4 jobs and 4 machines. The processing times p i,j,m of operations {O i,j ∈ O i , j = 1, . . . , n i } i∈J , on each eligible machine m ∈ M i,j are given in Table 1. A solution of this instance of the pFJSSP is to consider the following assignments:

operations O 1,1 , O 2,1 and O 2,3 on machine M 1, operations O 2,2 , O 3,2 , O 4,1 on machine M 2, operations O 1,2 , O 4,3 on machine M 3, and operations O 1,3 , O 3,1 , O 3,3 , O 4,2 on machine M 4.
These assignments are associated with the processing times noted in bold in Table 1. Figure 1 depicts such a solution. On machine M 2, operation O 3,2 is interrupted at t = 5 by operation O 2,2 and resumed on the same machine at t = 6. The makespan is 10.

M1 M2 M3 M4 O 1,1 O 1,2 O 1,3 O 2,1 O 2,2 O 2,3 O 3,1 O 3,2 O 3,2 O 3,3 O 4,1 O 4,2 O

Mathematical model

Let us introduce a mixed-integer program to solve the pFJSSP. It is based on a time-indexed formulation proposed by Bowman [START_REF] Bowman | The schedule-sequencing problem[END_REF] to solve the preemptive job-shop problem. We adapt it to integrate the notion of resource flexibility.

Let H = {1, 2, 3, . . . , h} be the time horizon. The decision variables are defined as follows:

x i,j,m = 1 if operation O i,j is processed on machine m; 0 otherwise.

y i,j,t = 1 if operation O i,j
is in process at time t; 0 otherwise. Hence for the mathematical model, it yields:

min C max (1)
s.t. m∈M i,j x i,j,m = 1 ∀i ∈ J , O i,j ∈ O i (2)
h t=1 y i,j,t ≥ m∈M i,j x i,j,m × p i,j,m ∀i ∈ J , O i,j ∈ O i (3) h t ′ =t y i,j,t ′ ≤ max m∈M i,j p i,j,m × (1 -y i,j+1,t ) ∀i ∈ J , O i,j ∈ O i \ {O i,n i }, t ∈ H (4) i∈J n i j=1 x i,j,m × y i,j,t ≤ 1 ∀m ∈ M, t ∈ H (5)
C max ≥ (t + 1) × i∈J y i,n i ,t ∀t ∈ H (6)
x i,j,m ∈ {0, 1} ∀i ∈ J , O i,j ∈ O i , m ∈ M i,j (7)
y i,j,t ∈ {0, 1} ∀i ∈ J , O i,j ∈ O i , t ∈ H (8)
The objective (1) is the makespan minimisation. Constraints (2) ensure that each operation is processed by exactly one of the eligible machines. The duration of each operation is satisfied thanks to constraints [START_REF] Pape | Resource constraints for preemptive job-shop scheduling[END_REF]. Constraints (4) express the precedence constraints between operations of the same job. Let i ∈ J be a job, O i,j and O i,j+1 be two successive operations and t be a given period. If operation O i,j+1 is processed at time t (i.e., y i,j+1,t = 1), then operation O i,j must be completed before t (i.e., no longer be processed from t, ∀t ′ ≥ t, y i,j,t ′ = 0). Constraints (5) represent the disjunctive constraints on each machine. Finally, constraints (6) allow us to calculate the makespan.

Note that constraints (5) are nonlinear, but can be easily linearised since variables x i,j,m and y i,j,t are binary, the previous mathematical model thus becoming a MILP model by adding the variables: z i,j,m,t = 1 if operation O i,j is processed on machine m at time t; 0 otherwise and replacing constraints (5) by the following constraint set:

z i,j,m,t ≥ x i,j,m + y i,j,t -1 ∀i ∈ J , O i,j ∈ O i , m ∈ M i,j , t ∈ H (9) z i,j,m,t ≤ x i,j,m ∀i ∈ J , O i,j ∈ O i , m ∈ M i,j , t ∈ H (10) z i,j,m,t ≤ y i,j,t ∀i ∈ J , O i,j ∈ O i , m ∈ M i,j , t ∈ H ( 11
) i∈J n i j=1 z i,j,m,t ≤ 1 ∀m ∈ M, t ∈ H (12)

Constraint programming

To introduce the CP model, we use the IBM CP Optimizer solver, which allows the use of specific decision variables and constraints. In particular, we use interval variables, whose main feature is to be optional. This concept is relevant to our problem since each operation is performed on a machine within a set of eligible machines.

There are two possible ways to model preemptive operations of duration p with interval variables [START_REF] Polo-Mejía | Mixed-integer/linear and constraint programming approaches for activity scheduling in a nuclear research facility[END_REF]: 1) by a set of optional interval variables with unfixed duration and imposing that the sum of their durations is equal to p;

2) by a chain of p unit-duration intervals.

These two possibilities are respectively illustrated in Figure 2 for an operation of duration 3.

1)

. . .

2)

. . . In the context of preemptive multi-skill resource-constrained project scheduling, Polo-Mejía et al. [START_REF] Polo-Mejía | Mixed-integer/linear and constraint programming approaches for activity scheduling in a nuclear research facility[END_REF] show that the second approach is more efficient. We have also conducted experiments leading to this conclusion for our specific pFJSSP. For this purpose, each preemptive operation is divided into unit-duration parts in our constraint programming model. We introduce the following decision variables:

• task i,j : interval variable between the start and the end of the processing of operation O i,j ;

• mode i,j,m : interval variable between the start and the end of the processing of operation O i,j on machine m (since the operations have multiple eligible machines and must be executed by exactly one of them, this is an optional variable);

• part i,j,k,m : interval variable of unit duration of the processing of the k th part of operation O i,j on machine m (optional variable).

min

C max (13) s.t. C max ≥ task i,n i .end ∀i ∈ J (14) EndBef oreStart(task i,j , task i,j+1 ) ∀i ∈ J , O i,j ∈ O i \ {O i,n i } (15) EndBef oreStart(part i,j,k,m , part i,j,k+1,m ) ∀i ∈ J , O i,j ∈ O i , m ∈ M i,j , 1 ≤ k ≤ p i,j,m -1 (16)
Span(mode i,j,m , part i,j,k,m : ∀1 ≤ k ≤ p i,j,m ) ∀i ∈ J , O i,j ∈ O i , m ∈ M i,j (17)
Alternative(task i,j , mode i,j,m : ∀m ∈ M i,j ) ∀i ∈ J , O i,j ∈ O i (18) P resenceOf (mode i,j,m ) ⇒ P resenceOf

(part i,j,k,m ) ∀i ∈ J , O i,j ∈ O i , m ∈ M i,j , 1 ≤ k ≤ p i,j,m (19)
N oOverlap(part i,j,k,m :

∀O i,j ∈ I m , 1 ≤ k ≤ p i,j,m ) ∀m ∈ M (20)
The objective function [START_REF] Yazdani | Two metaheuristic algorithms for the dual-resource constrained flexible job-shop scheduling problem[END_REF] is to minimise the makespan. Constraints ( 14) define the makespan. The global constraint EndBeforeStart is used to model the precedence constraints, as in the two following constraint sets. Constraints [START_REF] Ziaee | A mixed integer linear programming model for flexible job shop scheduling problem[END_REF] ensure that the operations of the same job will be processed with respect to the job sequence. Constraints [START_REF] Meng | Mixed-integer linear programming and constraint programming formulations for solving distributed flexible job shop scheduling problem[END_REF] aim at ordering the parts of the operation and so avoid symmetries, and ensure that each part is treated one after the other. With the Span global constraint, constraints [START_REF] Kress | Mathematical models for a flexible job shop scheduling problem with machine operator constraints[END_REF] are used to ensure that operation interval spans over all its processing parts (i.e., each operation starts with its first part and ends with its last part). Constraints [START_REF] Zhang | Flexible job-shop scheduling with flexible workdays, preemption, overlapping in operations and satisfaction criteria: An industrial application[END_REF] use the Alternative global constraint that ensures each operation to be processed by exactly one of the eligible machines. From the presence status (PresenceOf function) of mode interval variable, constraints [START_REF] Jansen | Approximation algorithms for flexible job shop problems[END_REF] define the duration of each operation. With the NoOverlap global constraint, constraints [START_REF] Hooker | Verifying logic circuits by Benders decomposition[END_REF] forbid the overlapping of operations processed on the same machine.

Logic-based Benders decomposition

Hybrid methods for optimisation, especially those combining MILP and CP, have been widely used since the late 90's. LBBD falls into this category. The LBBD approach decomposes a given problem into a master problem, usually a MILP, and one or several subproblems. It iterates between the master problem and the subproblems until an optimal solution is found by means of constraint generation techniques. At each iteration h, a subset of variables, say x, are fixed by the master problem, the resolution of the resulting subproblem provides the objective value z h implied by the current solution xh . This bound is then used to generate cuts that are added to the master problem, and so on. A state-of-the-art about LBBD can be found in [START_REF] Hooker | Integrated methods for optimization[END_REF].

Decomposition scheme

The pFJSSP can be decomposed into an assignment master problem and a scheduling subproblem. In the master problem, each operation is assigned to exactly one of its eligible machines. Solving the master problem enables to find a lower bound LB for the global problem. Once this assignment xh is fixed, the subproblem consists in a preemptive JSSP (i.e., without flexibility), of which a solution is an upper bound U B of the global problem and so a feasible solution of our problem. Solving this subproblem also allows the deduction of optimality cuts. Then, these cuts are added to the master problem, which is solved again. This general processing is illustrated in Figure 3.

In the following, a MILP model is proposed for the master problem. The scheduling subproblems are solved using two different methods: constraint programming for the first version and a dedicated branch-and-bound algorithm for the second version. These methods are named LBBD CP O and LBBD B&B , respectively. Then the question of the generation of optimality cuts is addressed. Finally, we present an extension of the methods for the consideration of the total completion time minimisation problem.

Master problem

The master problem is a relaxation of the pFJSSP as it only consists in the assignment of operations to machines (i.e., the constraints only involve the assignment variables x i,j,m ). Let m ∈ M be a machine, I ′ m ⊆ I m be a subset of operations that can be processed by m, r ′ m = min O i,j ∈I ′ m r min i,j be the shortest release starting date of operations from I ′ m (minimum head) and

q ′ m = min O i,j ∈I ′ m q min i,j
be the shortest delivery time after I ′ m (minimum tail). The master problem is as follows:

min C max (21)
s.t. m∈M i,j x i,j,m = 1 ∀i ∈ J , O i,j ∈ O i (22)
C max ≥ n i j=1 m∈M i,j x i,j,m × p i,j,m ∀i ∈ J (23)
C max ≥ r ′ m + O i,j ∈I ′ m x i,j,m × p i,j,m + q ′ m ∀m ∈ M, I ′ m ⊆ I m (24)
x i,j,m ∈ {0, 1} ∀i ∈ J , O i,j ∈ O i , m ∈ M i,j (25)
Constraints ( 22) are identical to constraints (2) (processing of each operation by one of the eligible machines). Constraints ( 23) and ( 24) express the relaxation of the subproblem as they help to estimate the objective value C max according to the assignment variables x i,j,m . Having a tighter lower bound increases the chances of obtaining high-quality subproblem. Constraints [START_REF] Hooker | Planning and scheduling by logic-based Benders decomposition[END_REF] restrict the makespan to be at least equal to the sum of the processing times of operations of the same job. Constraints [START_REF] Tan | Logic-based Benders decomposition for two-stage flexible flow shop scheduling with unrelated parallel machines[END_REF] come from an idea first proposed by Carlier [START_REF] Carlier | The one-machine sequencing problem[END_REF] to compute a lower bound for the JSSP: Given a machine m and a subset of operations I ′ m , the makespan is at least equal to the sum of the processing times of operations from this subset assigned to m, plus the minimum head and tail.

In practice, for this last set of constraints [START_REF] Tan | Logic-based Benders decomposition for two-stage flexible flow shop scheduling with unrelated parallel machines[END_REF], it is not useful to consider all the possible subsets of I m . Indeed, based on Theorem 1 below, it is enough to study the sets I a created as follows: for each machine m and for each pair of operations a = (O i,j , O i ′ ,j ′ ) ∈ I m × I m , let r a = min(r min i,j , r min i ′ ,j ′ ) be the minimum head and q a = min(q min i,j , q min i ′ ,j ′ ) be the minimum tail, and

I a = {O i,j ∈ I m | r min i,j > r a , q min i,j
> q a } be the set of operations that can be processed by m and of which the shortest release date and the shortest delivery time are larger than the minimum head and tail, respectively. Theorem 1. Let I ′ m and I ′′ m be two subsets, such that

I ′′ m ⊂ I ′ m and ∃ O i,j ∈ I ′′ m with r min i,j = r ′ m and ∃ O i ′ ,j ′ ∈ I ′′ m with q min i ′ ,j ′ = q ′ m . Constraint C max ≥ r ′ m + O i,j ∈I ′ m x i,j,m × p i,j,m + q ′ m dominates constraint C max ≥ r ′′ m + O i,j ∈I ′′ m x i,j,m × p i,j,m + q ′′ m .
Proof. To prove that a constraint C1 dominates another one constraint C2, it must be shown that C1 implies C2.

By assumption r ′ m = r ′′ m , q ′′ m = q ′ m and, for any assignment,

O i,j ∈I ′ m x i,j,m × p i,j,m ≥ O i,j ∈I ′′ m x i,j,m × p i,j,m . Hence, r ′ m + O i,j ∈I ′ m x i,j,m × p i,j,m + q ′ m ≥ r ′′ m + O i,j ∈I ′′ m x i,j,m × p i,j,m + q ′′ m . It follows that: C max ≥ r ′ m + O i,j ∈I ′ m x i,j,m × p i,j,m + q ′ m =⇒ C max ≥ r ′′ m + O i,j ∈I ′′ m x i,j,m × p i,j,m + q ′′ m .
Example 2. Consider again Example 1 and let suppose that:

x 1,1,1 = x 1,2,3 = x 1,3,4 = x 2,1,1 = x 2,2,2 = x 2,3,1 = x 3,1,4 = x 3,2,2 = x 3,3,4 = x 4,1,2 = x 4,2,4 = x 4,3,3 = 1.
Regarding constraints [START_REF] Hooker | Planning and scheduling by logic-based Benders decomposition[END_REF], it yields:

• duration of job 1: p 1,1,1 + p 1,2,3 + p 1,3,4 = 2 + 4 + 2 = 8 =⇒ C 1 ≥ 8;
• duration of job 2:

p 2,1,1 + p 2,2,2 + p 2,3,1 = 3 + 1 + 3 = 7 =⇒ C 2 ≥ 7;
• duration of job 3:

p 3,1,4 + p 3,2,2 + p 3,3,4 = 3 + 4 + 2 = 9 =⇒ C 3 ≥ 9;
• duration of job 4:

p 4,1,2 + p 4,2,4 + p 4,3,3 = 2 + 2 + 4 = 8 =⇒ C 4 ≥ 8.
Therefore, the makespan of the incumbent solution is at least 9, that is, C max ≥ 9. About constraints [START_REF] Tan | Logic-based Benders decomposition for two-stage flexible flow shop scheduling with unrelated parallel machines[END_REF], we detail the calculations for only one pair a = (O 1,1 , O 2,1 ) on machine M 1.

(1) Identify the head r a and tail q a : r a = min(r min 1,1 , r min 2,1 ) = min(0, 0) = 0 q a = min(q min 1,1 , q min 2,1 ) = min(p min 1,2 + p min 1,3 , p min 2,2 + p min 2,3 ) = min(4 + 2, 1 + 2) = 3

(2) Form subset I a :

I a = {O 1,1 , O 2,1 , O 3,1 , O 4,2 }
(3) Deduce a lower bound for the makespan:

C max ≥ 0 + p 1,1,1 × x 1,1,1 + p 2,1,1 × x 2,1,1 + p 3,1,1 × x 3,1,1 + p 4,2,1 × x 4,2,1 + 3 ≥ 0 + 2 × 1 + 3 × 1 + 3 × 0 + 4 × 0 + 3 = 8
Doing the calculations extensively on all machines and for all eligible pairs, we obtain C max ≥ 10 (for

I a ′ = {O 1,2 , O 4,3 } on machine M 3).
At each iteration h, we get a solution of the master problem, i.e., a set of operation-machine assignments. The following additional notations will be useful for the sequel: let xh i,j,m be the value of variable x i,j,m at iteration h. Let P h m = {O i,j ∈ O i , i ∈ J | xh i,j,m = 1} be the set of operations assigned to machine m at iteration h.

Subproblem

The subproblem is a pJSSP. To solve it, two different ways are proposed. We first present a CP model, then we describe a branch-and-bound algorithm that has its origin in a proposal made in Ebadi and Moslehi [START_REF] Ebadi | An optimal method for the preemptive job shop scheduling problem[END_REF].

Constraint programming: LBBD CP O

In the LBBD CP O method, the subproblem is solved using a constraint programming model. This model is similar to the one proposed in Section 2.2. However, in this case, it aims at solving a non-flexible pJSSP since the assignments are already fixed. The variables involved in this model are the following:

• task i,j : interval variable between the start and the end of the processing of operation O i,j ;

• part i,j,k : interval variable of unit duration of the processing of the k th part of operation O i,j .

Since the set of eligible machines is reduced to a single machine, unlike the model presented in Section 2.2, the mode i,j,m variables does not appear and part i,j,k are non-optional variables. The subproblem is described as follows:

min z h (26)
s.t. z h ≥ task i,n i .end ∀i ∈ J (27) EndBef oreStart(task i,j , task i,j+1 ) ∀i ∈ J , O i,j ∈ O i \ {O i,n i } (28) EndBef oreStart(part i,j,k , part i,j,k+1 ) ∀i ∈ J , O i,j ∈ O i , 1 ≤ k ≤ p h i,j -1 ( 29
)
Span(task i,j , part i,j,k : ∀1 ≤ k ≤ p h i,j ) ∀i ∈ J , O i,j ∈ O i (30)
N oOverlap(part i,j,k :

∀O i,j ∈ P h m , 1 ≤ k ≤ p h i,j ) ∀m ∈ M (31)
where p h i,j = m∈M i,j p i,j,m × xh i,j,m .

Branch-and-bound algorithm: LBBD B&B

The resolution algorithm used for the LBBD B&B method is inspired by Ebadi and Moslehi [START_REF] Ebadi | An optimal method for the preemptive job shop scheduling problem[END_REF]. In this study, the authors solve the pJSSP using a branch-andbound algorithm developed on the basis of a disjunctive graph representation. By exploiting the properties of the problem, they introduce effective dominance rules and lower bounds that make the method efficient. In particular, they have shown that the set of schedules of which preemption is only allowed by a newly available operation is dominant for the problem. The proposed algorithm is briefly presented in the following.

Each operation O i,j of duration p i,j is divided into p i,j operations {O i,j,1 , . . . , O i,j,p i,j } of unit duration named unit operations. At each level of the branch-andbound, the set V a of available unit operations (i.e., whose preceding operations have already been scheduled) is formed. The machine m * processing the unit operation with the earliest availability date (the availability date is determined by the longest path between node Start and the unit operation in the partial disjunctive graph) ES is selected. The set of unit operations available in ES on m * is denoted by V ′ a . A lower bound X for the date of the next available unit operation on m * is calculated. For each unit operation O i,j,k in V ′ a , a new node is created where O i,j,k and the (X -1) unit operations following are scheduled from ES. The disjunctive graph is updated (a disjunctive arc between the last unit operation O i,j,p i,j of operation O i,j and the set of other unit operations in V ′ a is added); hence, a lower bound LB of the partial scheduling is obtained to evaluate this new node. If LB is greater than the objective value of the best solution obtained so far, the node is pruned. Otherwise, the algorithm continue at the next level. Ebadi and Moslehi [START_REF] Ebadi | An optimal method for the preemptive job shop scheduling problem[END_REF] make the assumption that each job visits each machine at most once (in shop scheduling this is known as no recirculation). However, this is not true in our case when solving a subproblem of the pFJSSP. Indeed, during the assignment phase, nothing prevents two operations of the same job from being performed by the same machine (cf. Example 1). This is why we have to adapt the solving algorithm to our specific problem.

Benders cuts

If z h is the minimum makespan found by the subproblem, then a trivial Benders cut requires the makespan to be at least z h , whenever all assignments remain the same. In other words, any solution that achieves a better makespan assigns at least one of the operations to another machine. Thus, the following cut is created and added to the master problem:

C max ≥ z h 1 - m∈M O i,j ∈P h m (1 -xh i,j,m ) (32)
Inequality ( 32) is valid in the sense that it does not remove any feasible solution. However, this cut involves all the assignments and leads to the exclusion of only one solution of the master problem, since the cut becomes useless when even one of the operation assignments is changed. The goal is therefore to strengthen the cut by identifying a subset of assignments responsible for the value of the makespan.

For this purpose, we adapt our algorithm (see Algorithm 1). Once the master problem is solved (Step 1), instead of going directly to the subproblem (Step 3), the idea proposed by Carlier [START_REF] Carlier | The one-machine sequencing problem[END_REF] is again used, as in the set of constraints [START_REF] Tan | Logic-based Benders decomposition for two-stage flexible flow shop scheduling with unrelated parallel machines[END_REF], as a relaxation of the subproblem (Step 2). However, at this stage of the search, the assignments are fixed; this allows us to calculate a better approximation of the value of the objective function. Indeed, the duration of each operation O i,j is known:

p h i,j = m∈M i,j p i,j,m × xh i,j,m
, thus it is possible to redefine the shortest release date (resp. shortest delivery time) of an operation O i,j at iteration h as r min,h i,j = j ′ <j p h i,j (resp. q min,h i,j = j ′ >j p h i,j ). Let m ∈ M be a machine, a = (O i,j , O i ′ ,j ′ ) ∈ P h m × P h m be a pair of operations processed by machine m. Let us define r a = min(r h i,j , r h i ′ ,j ′ ) as the minimum head, q a = min(q h i,j , q h i ′ ,j ′ ) as the minimum tail, and P a = {O i,j ∈ P h m | m ∈ M i,j , r h i,j > r a , q h i,j > q a } as the set of operations that are processed by m and of which the shortest release date and the delivery time are smaller than the minimum head and the minimum tail, respectively. LB a = r a + O i,j ∈Pa p i,j,m + q a is a lower bound on the optimum value for the z h objective value in the pJSSP subproblem. Therefore, if LB a is superior to the incumbent best solution found, it is useless to solve the subproblem since it is impossible to improve the best known solution. Instead of solving the subproblem, it is required to add the following cut:

C max ≥ LB a 1 - m∈M O i,j ∈Sa∩P h m (1 -xh i,j,m ) (33)
where S a is the set of operations belonging to P a , but also the operations of jobs with at least one operation belonging to this set (because they have an influence on the calculation of r a or q a ).

Example 3. Consider Example 1 again and assume the same assignments as in Example 2, that is:

xh 1,1,1 = xh 1,2,3 = xh 1,3,4 = xh 2,1,1 = xh 2,2,2 = xh 2,3,1 = xh 3,1,4 = xh 3,2,2 = xh 3,3,4 = xh 4,1,2 = xh 4,2,4 = xh 4,3,3 = 1.
We focus on machine M 1 and we take into account the pair a = (O 1,1 , O 2,1 ):

LB a = r a + O i,j ∈Pa p i,j,1 + q a = min(r h 1,1 , r h 2,1 ) +p 1,1,1 + p 2,1,1 + min(q h 1,1 , q h 2,1 ) = min(r h 1,1 , r h 2,1 ) +p 1,1,1 + p 2,1,1 + min(p h 1,2 + p h 1,3 , p h 2,2 + p h 2,3 ) = min(0, 0) +2 + 3 + min(4 + 2, 1 + 3) = 9
This leads to the following cut:

C max ≥ 9 × 1 - m∈M O i,j ∈(O 1 ∪O 2 )∩P h m (1 -xh i,j,m )
In Example 3, although the considered subset of operations assigned to machine M 1 is identical to the one studied in Example 2, the bound obtained is tighter because the values r a and q a are calculated differently. Since the assignments are fixed, only the current assignment selection P h is taken into consideration to calculate the shortest release date r h i,j and shortest delivery time q h i,j of an operation O i,j (i.e., there is no need to consider all the possible assignments of previous and following operations).

Algorithm 1: Logic-based Benders decomposition algorithm

Initialisation Master constraints ←{constraint sets ( 22), ( 23), ( 24)} ; incumbent solution ← solution found using a heuristic ; h ← 0 ;

Step 1 Master problem Solve the assignment master problem until a new feasible solution P h is found ;

Step 2 Subproblem relaxation

foreach m ∈ M do foreach pair a = (O i,j , O i ′ ,j ′ ) ∈ P h m × P h m do r a ← min(r h i,j , r h i ′ ,j ′ ) ; q a ← min(q h i,j , q h i ′ ,j ′ ) ; P a ← {O i,j ∈ P h m | r h i,j > r a , q h i,j > q a } ; LB a ← r a + O i,j ∈Pa p i,j,m + q a m ; if LB a > incumbent solution.

value then

Generate cut [START_REF] Adams | The shifting bottleneck procedure for job shop scheduling[END_REF] and add it to master constraints ; Go back to Step 1 ;

Step 3 Subproblem current solution ← Solve the pJSSP subproblem with P h assignments ; if current solution.value < incumbent solution.value then incumbent solution ← current solution ;

Generate cut [START_REF] Lawrence | Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques[END_REF] and add it to master constraints ; Go back to Step 1

Total completion time

Considering the total completion time (i.e., the sum of the completion times of all the jobs) as the objective function to minimise, the decomposition scheme presented in Section 3.1 remains identical. However, adjustments have to be done to solve both the master problem and the subproblems.

Master problem

The master problem needs to be adapted to the new objective function. First of all, the criterion ( 21) is replaced by: min C total [START_REF] Carlier | An algorithm for solving the job-shop problem[END_REF] where C total is the total completion time.

Then we used two relaxations for the master problem. The first one is based on the idea that the completion time C i of a job i is at least equal to the sum of the processing times of operations belonging to job i, C i ≥ m∈M n i j=1 x i,j,m × p i,j,m , ∀i ∈ J . Constraints [START_REF] Hooker | Planning and scheduling by logic-based Benders decomposition[END_REF] are thus replaced by the following:

C total ≥ i∈J n i j=1 m∈M i,j x i,j,m × p i,j,m (35)
The second relaxation of the subproblem is based on the consideration of a singlemachine problem for each machine. On the one hand, by definition, the completion time of a job is not less than the completion time of one of its operations plus the tail of this operation: C i ≥ C i,j + q min i,j , ∀i ∈ J , O i,j ∈ O i . Hence, we deduce:

C i ≥ 1 n i × n i j=1 (C i,j + q min i,j ), ∀i ∈ J and C total ≥ i∈J 1 n i × n i j=1 (C i,j + q min i,j
). Let C m be a lower bound on the total completion time of operations on machine m. According to the previous statement, we can say that:

C total ≥ 1 max i∈J n i × m∈M C m + i∈J n i j=1 q min i,j (36)
On the other hand, the Shortest Processing Time first (SPT) rule is known to be optimal for the single-machine problem when the objective is to minimise the total completion time. Thus, for each machine m, let π m be a permutation of

I m such that p πm(1) ≤ p πm(2) ≤ • • • ≤ p πm(|Im|) . Hence, C ′ m = |Im| k=0 C πm(k)
where

C πm(k) ≥ k l=0 p πm(l) × x πm(l) × x πm(k) ( 37
)
is a lower bound on the total completion time of operations on machine m. Terms C πm(k) occur only for those operations that are assigned to machine m, that is why we introduce the assignment variables x πm(k) . We linearise by writing :

C πm(k) ≥ k l=0 (p πm(l) × x πm(l ) -B πm(k) × (1 -x πm(k) ) (38)
and C πm(k) ≥ 0, the big-M term B πm(k) is given by:

B πm(k) = k-1 l=0 p πm(l) (39)
Finally, we sum over all machines and constraints ( 24) are replaced by constraints ( 38), [START_REF] Fattahi | Mathematical modeling and heuristic approaches to flexible job shop scheduling problems[END_REF], and the following:

C total ≥ 1 max i∈J n i m∈M |Im| k=0 C πm(k) + i∈J n i j=1 q min i,j (40)

Subproblem

The subproblem must also fit the objective function. In particular, in the subproblem of the LBBD CP O version, it is enough to replace constraints ( 27) of the CP model by:

z h ≥ i∈J task i,n i .end (41)
Regarding the LBBD B&B version, some adaptations must be made in the branchand-bound algorithm. Specifically, the objective function value is given by the total length of the longest paths from node Start to the last unit operation of each job, in the disjunctive graph. At each node, a lower bound is calculated in a similar way in the partial disjunctive graph.

Numerical experiments

For computational tests, all experiments are performed on three cluster nodes with Intel Xeon E5-2695 v4 CPU at 2.1 GHz. All algorithms presented are implemented in C++, using CPLEX 12.10 for the MILP models and CP Optimizer (CPO) 12.10 for the CP models. CPU time and RAM were respectively limited to 1 hour and 16 GB.

A naive heuristic allows us to obtain an upper bound for the objective value. This solution is used at the beginning of the search in the decomposition methods. For the purpose of comparison between methods, and for the sake of fairness, we also use this solution as a warm start for the CP method. Therefore, the instances are solved using the CP model presented in Section 2 with warm start solution (method warm CP O) and without (CP O), and by the two versions of the decomposition proposed in Section 3 (LBBD CP O and LBBD B&B ).

To evaluate and compare the diverse methods, we consider various performance measures:

• the average optimality gap, computed as follows:

gap method = U B method -LB method U B method (42)
• the proportion of optima found;

• the relative percentage deviation compared to the best solution found. It aims to evaluate the quality of the upper bounds found by each method. It is therefore computed as follows:

RD method = U B method -U B * U B * (43)
where U B * is the best bound found among all tested methods;

• the proportion of instances for which the best solution (among the tested methods) is found.

Moreover, two objective functions are considered: the minimisation of the makespan and the minimisation of the total completion time.

Instances

Numerous benchmark instances for the FJSSP without preemption are available in the literature. These instances serve as a reference to evaluate our propositions in the preemptive case.

Brandimarte [START_REF] Brandimarte | Routing and scheduling in a flexible job shop by tabu search[END_REF] introduced instances, referred to here as "BrandimarteMk ", of which data are randomly generated using a uniform distribution within a given limit. Hurink et al. [START_REF] Hurink | Tabu search for the job-shop scheduling problem with multi-purpose machines[END_REF] provided an adaptation of some of the classical JSSP instances [START_REF] Fisher | Probabilistic learning combinations of local job-shop scheduling rules[END_REF][START_REF] Lawrence | Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques[END_REF][START_REF] Adams | The shifting bottleneck procedure for job shop scheduling[END_REF][START_REF] Carlier | An algorithm for solving the job-shop problem[END_REF][START_REF] Applegate | A computational study of the job-shop scheduling problem[END_REF] and generate three data sets, denoted by "HurinkEdata", "HurinkRdata" and "HurinkVdata", with increasing flexibility, by expanding the pool of eligible machines for some of the operations. Dauzère-Pérès and Paulli [START_REF] Dauzère-Pérès | An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search[END_REF] designed a data set "DPpaulli ", in which the number of operations per job is greater than the number of machines, and whose parameters are randomly generated using a uniform distribution within given limits. Barnes and Chambers [START_REF] Barnes | Flexible job shop scheduling by tabu search[END_REF] created a set of instances "ChambersBarnes" based on three instances of the classical JSSP problem [START_REF] Fisher | Probabilistic learning combinations of local job-shop scheduling rules[END_REF][START_REF] Lawrence | Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques[END_REF] transformed into FJSSP instances by duplicating some machines. Kacem et al. [START_REF] Kacem | Pareto-optimality approach for flexible jobshop scheduling problems: Hybridization of evolutionary algorithms and fuzzy logic[END_REF] created the instances "Kacem" with total flexibility (i.e., each machine is able to process each operation). Furthermore, for this benchmark, it is worth mentioning that it is also distinguished by the very small number of instances it contains (4). Lastly, Fattahi et al. [START_REF] Fattahi | Mathematical modeling and heuristic approaches to flexible job shop scheduling problems[END_REF] proposed randomly generated small-and medium-size problems ("Fattahi ").

Characteristics of these benchmarks are summarised in Table 2. For each benchmark, we report the number of instances (276 in total) that compose it, the size of these instances (in terms of number of jobs and number of machines), as well as the flexibility degree of the instance, defined as the average number of eligible machines per operation. Detailed information on these instances is presented in Behnke and Geiger [START_REF] Behnke | Test instances for the flexible job shop scheduling problem with work centers[END_REF]. show a graphical visualisation of the performance indicators for the minimisation of the makespan. In these figures, the results are grouped by type of benchmark. Figure 4 presents the average optimality gap for each method. We observe that the proposed decomposition methods outperform CP methods for all benchmarks. Globally, if we consider together the 276 instances, CP O method reaches in average an optimality gap of 23% (22% for warm CP O) in comparison with 10% for the LBBD CP O method and 6% for the LBBD B&B . Note that none method succeeds in solving even a single instance for benchmarks from Dauzère-Pérès and Paulli [START_REF] Dauzère-Pérès | An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search[END_REF] and Barnes and Chambers [START_REF] Barnes | Flexible job shop scheduling by tabu search[END_REF].

Figure 6 provides the proportion of best solutions found among all methods. In contrast to the optimality gap, if we consider the number of best solutions found as an indicator of performance, method LBBD CP O (with 65 best solutions found over all instances) does not clearly dominate CP O (with 56 best solutions) and gets even worse results than warm CP O (with 90 best solutions). However, method LBBD B&B still outperforms all these methods (with 194 best solutions) and finds at least half of the best solutions for each benchmark.

We illustrate the relative percentage deviation compared to the best solution found in Figure 7. It shows that LBBD B&B always gets high-quality solutions and never exceeds an average of 2% deviation for each benchmark. For the other methods, the quality of the solutions obtained is quite variable depending on the benchmark studied.

Based on these results we deduce that the proposed decomposition LBBD B&B outperforms the CP model for makespan minimisation. For all studied benchmarks, LBBD B&B method obtains a greater number of optimal solutions (Figure 5), a greater number of best solutions (Figure 6), a smaller average gap (Figure 4), and a smaller relative deviation to the best solution found (Figure 7).

Although the LBBD B&B method achieves better performances, we notice a great variability of the results depending on the benchmarks. Therefore, we propose to focus on the possible factors. In particular, Figure 8 permits us to study the optimality gap according to the average number of operations per machine. Each point of this graph represents an instance of the FJSSP solved by one of the four studied methods, with as abscissa the average number of operations per machine of the instance and as ordinate the obtained optimality gap for it with the involved method.

The observation of Figure 8 confirms what can be seen in Figure 4, namely that the decomposition-based methods achieve a better optimality gap than pure constraint programming methods. Moreover, using the linear regression performed for each method, we notice that problems become more difficult to solve as the number of operations per machine increases. However, the efficiency of the decomposition methods is less sensitive to that factor than the CP methods. Indeed, while the slope of the linear regression relating the optimality gap obtained by the CP-based meth- Finally, all the results presented above show the superiority of the LBBD B&B method over the LBBD CP O method. In Table 3, we report, for these two methods, the proportion of time spent in solving the subproblems (SP(%)), the proportion of time spent in solving the master problems (MP(%)), the average number of subproblems solved (SP number), and the average time spent to solve a subproblem (time per SP) for each studied benchmark. As expected, the time spent to solve the subproblems is much smaller for methods using the branch-and-bound algorithm, which explains its better performance. We also notice that for the most complicated instances (DPpaulli and ChambersBarnes), very few subproblems are considered (only 1 in most cases), which means that, whatever the method used, the imposed time limit of 1 hour is not enough to optimally solve these subproblems. By crossing this information with Figure 6, we note that even for these complicated instances method LBBD B&B obtains better quality solutions. We deduce that, in addition to proving the optimality of a solution more efficiently, the branch-and-bound algorithm allows finding better solutions in a given time than the CP method for the

Total completion time

As presented in Section 3.5, we adapt all methods to the problem of minimising the total completion time. For this objective function, we illustrate all the considered performance measures in Figures 9101112.

Contrary to the makespan minimisation problem, no method clearly outperforms the others when minimising the total completion time. In general, the observed performances, for instance in Figures 9 and10, are worse for this objective function, as it makes the problem more difficult. In more detail, we can observe in Figure 9 that very few instances are solved to optimality, only 6% of them, considering together the four methods under study. Among them, the methods that prove the optimality for the largest number of instances are warm CP O and CP O, which obtain exactly the same results (with 15 instances over 276) followed by LBBD B&B (14 instances), and finally LBBD CP O (9 instances). In addition, the optimality gap is very wide, for many instances and all methods, as shown in Figure 10. We also note that the average gap per benchmark is similar for each method, which results in very close overall average gaps: 39% for the warm CP O method, 38% for CP O, 37% for LBBD CP O , and 36% for LBBD B&B .

Figures 11 and12 focus on relative performances of the methods concerning the quality of the returned solutions. Again, none of the methods stand out, however, we notice a different behaviour for the CP methods compared to the LBBD methods. For both indicators (number of best solutions and relative deviation) and for most benchmarks, either the CP methods dominate, or the LBBD methods perform better.

Conclusions

In this paper, we present several exact methods to solve the preemptive flexible job-shop scheduling problem with two different objective functions, the makespan minimisation and the total completion time minimisation. We model the problem with both mixed-integer linear programming and constraint programming. Our main contribution consists in proposing a logic-based Benders decomposition algorithm by splitting the problem into an assignment master problem and a non-flexible scheduling subproblem. Concerning the makespan minimisation, the decomposition makes possible the use of the most powerful procedure in the literature to solve the preemptive job-shop subproblem, namely a branch-and-bound algorithm. With this method, the proposed decomposition outperforms the constraint programming model both in terms of optimality gap and in terms of the quality of the solutions found. We extend these solution methods to the total completion time minimisation problem. Due to the greater complexity of this problem, none of the proposed methods can achieve satisfactory results.

Future works could explore a way to take advantage of the proposed decomposition for the total completion time objective. Heuristics are also needed for the

Figure 1 :

 1 Figure 1: Gantt chart of a solution for Example 1 (4-job×4-machine pFJSSP, makespan 10)

Figure 2 :

 2 Figure 2: Two possible models with interval variables for preemptive operations of duration 3

Figure 3 :

 3 Figure 3: A decomposition scheme for the pFJSSP

Figure 4 :Figure 5

 45 Figure 4: Makespan minimisation -Average optimality gap for each method according to benchmarks

B r a nKFigure 5 :Figure 6 :

 56 Figure 5: Makespan minimisation -Proportion of optima found for each method according to benchmarks

Figure

  Figure Makespan minimisation -Average relative deviation to the best solution found for each method according to benchmarks

2 Figure 8 :

 28 Figure 8: Makespan minimisation -Gap to the average number of operations per machine for each method

Figure 9 :

 9 Figure 9: Total completion time minimisation -Proportion of optima found for each method according to benchmarks

Figure 10 :KFigure 11 :Figure 12 :

 101112 Figure 10: Total completion time minimisation -Average optimality gap for each method according to benchmarks

Table 1 :

 1 Numerical example of an instance of the pFJSSP: processing times

Table 2 :

 2 FJSSP instances characteristics

	4.2. Makespan
	Figures 4 to 7

Table 3 :

 3 Makespan minimisation -Performances of decomposition methods for each benchmark

	Benchmarks			LBBD CP O				LBBD B&B
		SP(%) MP(%) SP number time per SP SP(%) MP(%) SP number time per SP
	BrandimarteMk 99.94 0.07	3	502.9	99.81	0.2	69	16.3
	HurinkEdata	100	0.01	3	861.8	100	0.01	42	54
	HurinkRdata	99.99 0.02	35	100.1	93.19 6.82	2855	0.9
	HurinkVdata	99.84 0.17	9	326.6	69.11 30.9	2858	0.4
	DPpaulli	99.57 0.44	1	2809	99.71	0.3	1	2810.5
	ChambersBarnes 99.99 0.02	1	3599.5	100	0.01	1	2614.8
	Kacem	16.67 83.34	9	0.1	0	100	9	0
	Fattahi	99.99 0.02	38	30.4	0.14 99.87	2364	0.1

Acknowledgements

The authors are indebted to Abbas Ebadi and Ghasem Moslehi who very kindly provided their branch-and-bound code.


Andrea Brognara

Beatrice R Bricchi

Ludovic William

Ovidiu Brinza

Maria Konstantakopoulou

Andrea Li Bassi

Matteo Ghidelli

Nathalie Lidgi-Guigui
email: nathalie.lidgi-guigui@univ-paris13.fr

Andrea Li

New Mechanism for Long Photo-Induced Enhanced Raman Spectroscopy in Au Nanoparticles Embedded in TiO 2

Keywords: TiO2, SERS, nanoparticles, cathodoluminescence, photo-induced charge

separation; PIERS

Abstract.

The PIERS effect (Photo-Induced Enhanced Raman Spectroscopy) is a phenomenon taking place when plasmonic nanoparticles deposited on a semiconductor are illuminated by UV light before the Raman measurement. Recent results show enhancement of the Raman scattered intensity even greater that with conventional surface enhanced Raman Scattering that last for about an hour. The proposed mechanism for this effect is the creation of oxygen vacancies in the semiconductor that would create a path for charge transfer between the analyte and the nanoparticles. However, this hypothesis has never been confirmed experimentally. Furthermore, the tested structure of the PIERS substrate has always been composed of plasmonic nanoparticles on top of the semiconductor. Inhere we present PIERS results obtained on gold nanoparticles co-deposited with porous TiO2 which confer them a unique position half buried in the semiconductor. The resulting PIERS intensity is among the highest measured until now but most importantly the duration of the effect is significantly longer (at least 8 days).

Cathodoluminescence measurements on these samples show for the first time that two distinct mechanisms are at stake for co-deposited and dropped casted gold nanoparticles. The oxygen vacancies hypothesis tends to be confirmed for the latter, but a the narrowing of the depletion zone explains the long PIERS effect.

Introduction

Surface Enhanced Raman Spectroscopy (SERS) is known for its high sensitivity and has been widely applied to the detection of biomarkers and molecules [1][2][3][4][5] . Researchers have reported enhancing factors up to 10 14 [6][7][8] and some even claim that it is possible to detect a single molecule [9,10] . The understanding of the origin of SERS allow to go further than the simple detection of chemicals. For example, the study of the conformation of complex molecules [11,12] has been made possible because it is known that the Raman scattering enhancement is dependent on the distance from the enhancing surface. As a consequence, the closest to the surface a molecular bond is the strongest enhancement it will have.

The SERS effect has been experimentally described for the first time in the 1970s when scientists noticed that the Raman spectra were much more intense if the molecules were in the vicinity of a rough metallic surface [13][14][15][16] . The origin of SERS continues to be explored until today, however it is commonly admitted that part of the extraordinary enhancement is due to the generation of an electromagnetic field near the molecule. In the first SERS experiment, a delocalized Surface Plasmon (SP) was involved. Localized Surface Plasmon (LSP) refers to the collective oscillation of the nanoparticle (NP) electronic cloud by the excitation of an incident light and are a much powerful tool to confine and manipulate the electromagnetic field of light at the nanoscale. This explains why most of the SERS related research of these past decades has been focused on SERS with metallic NPs. Another proposition has been made to explain the origin of SERS, the so-called chemical effect [START_REF] Otto | Light Scatt. Solids IV. Top. Appl. Physics[END_REF] takes place when a molecule is binding to a metallic nanoparticle and charge transfer is promoted between the molecule and the metal.

The materials of the surface and of the NPs, as well as the geometry of the system are of crucial importance to set up SERS. For example, the electromagnetic effect may be due to the LSP, yet the intensity of the electric field around the NP is related to its shape. The lightning-rod effect [START_REF] Liao | [END_REF]19] takes place on sharp metallic nanostructure where the electric field is confined. This contributes to considerably enhance the Raman scattered intensity [20][21][START_REF] Gucciardi | Handbook of Enhanced Spectroscopy[END_REF] . Another way to contribute to the electromagnetic field intensity is to confine it in between two close nanoparticles to form hot spots [START_REF] Otto | [END_REF] .

Similarly, it is possible to contribute to the chemical effect for an even greater enhancement of the Raman scattering intensity. In this case the choice of materials has consequences on the electron transfer pathways between the nanostructured surface and the chemical. Traditionally Ag and Au are preferred for the NPs because they are showing the most intense plasmons in the visible [24] , their chemistry is well known and allow a large range of molecules to be grafted.

Au especially doesn't oxidize and is probably the most use material for SERS. Another example is given by semiconductors. The intensity of semiconductor's LSP is indeed weaker, yet the wide use of semiconductors in the industry makes them good candidates for a compromise between cost and gain [25,26] .

When a molecule is grafted on a metal, electron transfers are likely to take place between the Highest Occupied Molecular Orbital (HOMO) of the molecule and the Fermi level of the metal.

In semiconductors, electrons transfer occurs between the HOMO and the conduction band (CB) or between the valence band of the substrate (VB) and the Lowest Unoccupied Molecular Orbital (LUMO) of the analyte. In other words, the use of a semiconductor increases the numbers of possible charge transfer mechanisms. It is especially interesting as their band gap can be tuned, it is thus possible to promote a preferred process for charge transfer, the other or even adapt the transition to a specific wavelength.

Adding metallic NPs to a semiconductor has been demonstrated to be even more efficient for SERS. Plasmonic NPs can contribute to charge transfer in different ways presented in Figure 1. The Plasmon Induced Charge Separation (PICS) mechanism (Figure 1a) where the charges are excited in the NP (either interband transition or hot electron) and have enough energy to overcome the Schottky barrier between the metal and the semiconductor. Another way to transfer electrons from a metallic NP to the semiconductor is to take advantage of its plasmonic activity. In PRET (Plasmon Resonant Energy Transfer) the electromagnetic field emitted by the LSP induces a charge excitation inside the semiconductor (Figure 1b). Finally, SERS can take advantage of the photocatalytic effect where the electron is transferred from the semiconductor into the NP (Figure 1c).

The possibility of adding charges to the plasmonic NP widens the possibilities for SERS as the chemical effect is based on charge transfer between the nanostructured surface and the analyte whose Raman scattering is to be enhanced. The group of J. R. Lombardi has exploited the combinations offered by Ag NPs in TiO2 to induce SERS by charge transfer [25] . In 2016, Ben Jaber et al. [27] have gone one step further by using UV light to irradiate Au NP drop-casted on TiO2 rutile. The enhancement of the Raman intensity is about three times higher by Photo-Induced Enhanced Raman Scattering (PIERS) than with traditional SERS. The authors claim that UV illumination results in oxygen vacancies (VO) formation in the TiO2 whose energy level under the conduction band of TiO2. It eases the charge transfer from VO to the Au NPs and then to the molecule when the system is under the illumination of the Raman spectrometer (Figure 1d). Around 60 minutes later, the VO are cured in air and the PIERS effect disappears. Since then, a few papers have reported results on PIERS. In all cases the NPs are on top of the semiconductor either by drop-casting a previously synthesized solution of Au or Ag NPs or by chemically synthesizing Ag NP directly on the semiconductor surface. So far quite a low number of systems have been investigated: TiO2, ZnO and WO3 are all semiconductors where the proposed mechanism of VO formation upon UV irradiation has been advanced. In these systems, the wavelength of the LSP resonance (LSPR) is always blue shifted after UV irradiation. Other mechanisms have been considered in very specific systems, in 2018 Al-Shammari et al [28] have reported on their study of PIERS on Ag NP drop-casted on lithium niobate and, in 2020, Abid et al [29] have published their results of PIERS on Au NP drop casted on a 2D material, WS2. In the first case, it seems that the Raman enhancement is favored by a photocatalytic effect. For WS2 the authors suggest that the charge transfer is coming from the Au NPs toward the semiconductor and then to the analyte like what was propose in [30] . PIERS has already been demonstrated successful on a diversity of molecules: Raman probes [27][28][29]31] , biomolecules (DNA [32] , tyrosine [33] , glucose [27] ), explosives [27,34] , and organic pollutants [35,36] .

It has also been used for the study of VO dynamics in semiconductors [37,38] . Nevertheless, this technique is still young and, as Zhao et al. are pointing out in their 2021's review [39] , several issues must still be addressed. Among them, the optimization of the system "Semiconductor + NPs" and the study of the mechanisms of PIERS.

In the present paper we propose to focus on these two questions. Instead of drop-casted NPs, we are considering Au NPs that have been co-deposited together with the TiO2, so they are embedded in the semiconductor (in the following they will be referred as "embedded Au-TiO2").

For the first time we report on a red shift of the LSPR after UV irradiation and most importantly we observe a much stable enhancement (at least one week) than what was reported before.

These results suggest that a distinct mechanism is at stake, therefore we have performed cathodoluminescence (CL) measurements to support our hypothesis on charge transfer mechanism specific to this system. Eventually a comparison of CL results with conventional drop casted Au NP is done to highlight the different possible processes of PIERS.

Results and discussion

TiO2 growth and structure characterization

The embedded Au-TiO2 was grown by the co-deposition of Au and TiO2 with laser ablation (see experimental for the growth details and Bricchi et al. [40] for the characterization). The samples investigated here were obtained after annealing them at 700°C in air. The characterization of the sample morphology was conducted through SEM, on both embedded Au-TiO2 (Figure 2) and bare TiO2 [40] films (i.e. without Au) before and after the annealing treatments. Synthetized films, in the as deposited conditions, presented a characteristic hierarchical 1D vertically oriented, tree-like nanostructure with very large specific surface area [41] . The thermal treatment did visibly affect the shape and dimensions of these nanostructures as the tree-like TiO2 looked more compact. One of the consequences of this is the enlargement of the distance between the tree-like structure making the AuNPs more accessible. The annealing also impacts the size of the Au NP as their sized is going from about 5 nm before annealing to around 12 nm after. Figure 2d shows that the AuNPs are positioned in the bulk of the sample and on the surface of the TiO2 tree-like structures. AuNPs are actually pinned to the surface of the trees which makes interactions possible with both TiO2 and the environment. Raman analysis was performed in order to investigate TiO2 crystal structure. Anatase is well known to present six Raman active modes namely at 144 cm -1 (Eg), 197 cm -1 (Eg), 399 cm -1 (B1g), 519 cm -1 (superimposed with the 515 cm -1 band) (A1g, B1g) and 639 cm -1 (Eg). Rutile phase, instead, has five Raman active modes at: 143 cm -1 (B1g) 240 cm -1 (multi-photon process) 447 cm -1 (Eg) 612 cm -1 (A1g) and 826 cm -1 (B2g). Figure 3 shows the Raman spectra obtained with an excitation wavelength of 514.5 nm and 633 nm; both spectra have been normalized to the intensity of the 144 cm -1 peak. The spectra acquired with the green excitation shows a very intense peak at 144 cm -1 and weaker peaks at 399 cm -1 , 519cm -1 and 639 cm -1 . The spectra acquired with an excitation wavelength of 633 nm displays the same peaks, however as it is less noisy new peaks can be identified 233 cm -1 , 450 cm -1 , 615 cm -1 . These peaks are characteristics of a rutile phase. A very bright peak at 685 cm -1 is not conventional for TiO2, other data (not shown) indicates that it is linked to the presence of the embedded Au NPs and the thermal treatment.

Optical properties

The extinction spectra of the samples have been measured before UV irradiation, immediately after and, at several times until one day (Figure 4.) after. These results are then used in the study of the influence of UV irradiation on the Raman intensity. The position of the peak before UV irradiation is 580 nm. Just after irradiation it has red-shifted to 609 nm and this position remains stable for almost two hours (Figure 4b). One day after the UV irradiation, the position of the LSPR is blue shifted but is still 14 nm greater that the original position. This is an important difference with other PIERS studies where the exposition to UV irradiation of a metallic NP/semiconductor system led to a blue shift. In the literature many combinations of materials have been tested for both the semiconductor and the plasmonic NPs. The size of the NPs as well as their growth process have also been varied. Among the parameters that have not been investigated yet is the position of the NPs with respect to the semiconductor (partially buried in the bulk instead of on top of the surface).

SERS measurement

The SERS measurements were performed after soaking the samples in a Mercaptobenzoic acid (MBA) solution. This molecule is a well-known Raman reporter whose SH group has a high affinity with gold but none with TiO2, this guarantes a specific grafting on the Au NPs. A single layer of molecule is made sure by thorough rinsing [42][43][44][45] . SERS measurement were perfomered on a non irriadated sample and on another sample 30 minutes and 8 days after UV irradiation (30 minutes being the duration for the AuNPs functionalization, see experimental part) (Figure 5). On the three spectra the two broad peaks characteristics of MBA can be seen at 1080 cm -1 and 1590 cm -1 which are due to ring breathing modes, respectively in plane and axial. After irradiation these peaks are even more intense and weaker peaks emerge at 1184 cm -1 and 1486 cm -1 (CO and COO -stretching).

Previously reported PIERS experiments dealing with MBA are not always successful to measure an enhancement of these two weaker peaks as compared with conventional SERS. The enhancement measured here may have several possible origins such as the distance of the CO and COO -bonds from the surface of the Au NPs, or the properties of the AuNPs embedded in TiO2 which could be more suitable for an enhancement of the chemical effect as it is demonstrated in the following.

The enhancement factor for SERS (EFSERSbefore UV) and PIERS (EFPIERSafter UV) are calculated in a similar way as follow:

𝐸𝐹 𝑆𝐸𝑅𝑆 = 𝐼 𝑆𝐸𝑅𝑆 . 𝐶 𝑅 𝐼 𝑅 . 𝐶 𝑆𝐸𝑅𝑆 (1)
𝐸𝐹 𝑃𝐼𝐸𝑅𝑆 = 𝐼 𝑃𝐼𝐸𝑅𝑆 . 𝐶 𝑅 𝐼 𝑅 . 𝐶 𝑃𝐼𝐸𝑅𝑆 (2)
Where ISERS, IPIERS and IR stands for the SERS, PIERS and Raman intensity respectively. CSERS, CPIERS and CR are the concentrations of MBA in each case. CR = CSERS = CPIERS as the functionalization does not depend on light. The PIERS gain is given by the comparison between EFPIERS and EFSERS:

𝐺 𝑃𝐼𝐸𝑅𝑆 = 𝐸𝐹 𝑃𝐼𝐸𝑅𝑆 𝐸𝐹 𝑆𝐸𝑅𝑆 = 𝐼 𝑃𝐼𝐸𝑅𝑆 𝐼 𝑆𝐸𝑅𝑆 (3)
GPIERS is summarized in Table 1 and is of about one order of magnitude for the two main peaks at 1080 cm -1 and 1590 cm -1 . Furthermore, this enhancement is stable at least for 8 days after UV irradiation. For comparison GPIERS is equal to 7.5, 9.0, 4.5 and 3.1 in, respectively, ZnO [31] ,

WO3 [34] , WS2 [29] and TiO2 [38] (with Au NPs drop casted on top) (for comparison with systems including AgNP a comprehensive table is available in [39] ). In each of these cases the effect lasts for about one hour. 1. GPIERS measured at 1080 cm -1 and 1590 cm -1 as compared to the one obtained before irradiation.

Cathodoluminescence.

The results presented above confirm the finding of a Photo Induced Enhanced Raman Scattering (PIERS) effect. Even though the structure of the samples is very similar to what can be found in the literature the results are better in terms of enhancement and duration. We also observe a red shift of the LSPR when a blue shift is usually seen after UV irradiation which is a sign that UV irradiation does not affect the environment of the Au NPs in the same way as previously proposed.

To investigate the mechanism in the embedded Au-TiO2, we have performed cathodoluminescence (CL) measurements on bare TiO2 and embedded Au-TiO2. In a CL experiment, an electron beam impinges a material and excite some energies transition. This results in the emission of photon at specific wavelengths that reveals charge recombination in the material. For example, as anatase bandgap is 3.2 eV, an emission is expected at the corresponding wavelength of 380 nm. CL is also able to excite charges in Au NPs, either interband transitions (from the d to the sp band) or hot electrons produced during the plasmon decay. All CL spectra below have been normalized to the 380 nm peak intensity to ease the comparison.

Peak position (nm)

CL of bare TiO2

Figure 6a shows the CL spectrum of bare TiO2 before UV irradiation. The deconvolution of the spectrum indicates the presence of seven peaks whose position and relative intensities are given in Table 2. The relative intensities are the ratio of the intensity of the peak under consideration to the one at 380 nm, this latter has been chosen as the reference since it corresponds to anatase bandgap. The large pattern in the infrared region is composed of two peaks: a weak one at 801 nm and another very bright at 850 nm. These two peaks are attributed to Ti 3+ defects in rutile phase [START_REF] Plugaru | Proc. Int. Semicond. Conf. CAS[END_REF][START_REF] Plugaru | Proc. Int. Semicond. Conf. CAS[END_REF][START_REF] Fernàndez | [END_REF] : in presence of VO two electrons are distributed to the adjacent Ti 4+ ions becoming two Ti 3+ . At the other end of the spectrum peaks attributed to anatase are found: 380 nm correspond to anatase band gap, 460 nm is attributed to self-trapped excitons and 540 nm is due to shallow traps ascribed to VO. However, anatase presents a very bright peak at 520 nm when rutile does not [START_REF] Plugaru | Proc. Int. Semicond. Conf. CAS[END_REF]49] which is the case here. These first observations confirm the results of Raman spectroscopy: the crystalline structure of TiO2 is made of both anatase and rutile. It also points out the presence of VO already before UV irradiation.

After UV irradiation (Figure 6b), the structure of the spectrum is overall the same. However, one can notice slight changes in the intensity ratio between the peaks (Table 2.). Especially, the 850 nm luminescence is more intense than the one at 540 nm after UV irradiation. This is the sign of an increase in Ti 3+ defects due to VO formation [START_REF] Fernàndez | [END_REF] .

CL of embedded Au-TiO2

Before UV irradiation, the intensity ratio between the peaks of the CL spectra of embedded Au-TiO2 (Figure 6c) is very different from bare TiO2. Table 2 shows more explicitly the differences: an increase by a factor 6.7 and 15 of the 460 and 540 nm peaks relative intensity;

The shift of the peaks at 605 nm and 680 nm to the positions of 660 nm and 750 nm; the quenching of the peak at 800 nm and 850 nm.

The fact that the peaks in the IR have almost disappeared reveals the conservation of the Ti 4+ ions. This mean either that there are less VO in the TiO2 and therefore less Ti 3+ ; or that the presence of Au prevents the charges let available by the VO to be distributed to the Ti 4+ .

At the same time, the peaks intensity at 460 nm and 540 nm have considerably increased. In CL, increased intensity is taking place only if there are more charge carriers that can recombine and consequently emit a photon.

The increase of the first peak demonstrates an increase of self-trapped exciton in the TiO2 lattice.

The increase of the peak at 540 nm can have several origins. As mentioned above, they are already found in bare TiO2 where they are due to the shallow traps [50] . Another explanation could be related to PRET (Figure 1b) where the electromagnetic field generated by the LSPR promote charge transition in the TiO2 bandgap. However, PRET is mostly taking place for NPs about 10 nm apart from the semiconductor surface which is not the case here. Another possibility would be a thermally activated mechanism. The temperature increases around the NP are less than 50 K [51] which is negligeable for accounting for the observations. Eventually, the enhancement can be attributed to PICS (Figure 1a). This effect takes place at the LSPR wavelength when Au NPs are in contact with the semiconductor. Here 540 nm is close to the LSPR position and also corresponds to the Au interband transition. In other words, CL electrons excites hot electrons in the Au NPs coming either from interband transition or LSPR, which have enough energy to overcome the Schottky barrier to be transferred at the VO energy level [52] .

In bare TiO2 there is only one possible source of charge carriers in these regions of the spectrum whereas with the embedded Au-TiO2 two more sources are available. More charge carriers implies more CL emission and explains the increase before UV irradiation.

The fact that the absence of Ti 3+ coincides with the increase of self-trapped excitons suggests that the electrons left available by the VO have not been redistributed to the Ti 4+ . They are either transformed in self-trapped exciton or distributed to the Au NPs. This would explain the increase of the peaks at 460 nm and would be another source of luminescence at 540 nm.

The peak at 605 nm has shifted to 660 nm and has increased by a factor 20. The one at 680 nm has shift to 750 nm and has kept a similar intensity as the peak at 380 nm. These peak positions have already been reported in rutile powder. They are related to a lower number of radiative shallow traps [START_REF] Plugaru | Proc. Int. Semicond. Conf. CAS[END_REF] . The CL results on embedded Au-TiO2 demonstrate the importance of the differences in the crystalline structure as compared to bare TiO2. This, in turn, has consequences on the band diagram and charge transfer mechanism between Au and TiO2.

Immediately after UV irradiation, the CL spectra of embedded Au-TiO2 (Figure 6d) has significantly evolved and show high similarities with the spectra of bare TiO2. The peaks relative intensities are very similar to what is measured in bare TiO2. Especially the IR peaks are bright which is the sign of Ti 3+ appearance. Another striking feature is the disappearance of the CL increase at 460 nm and 540 nm.

In the present experiment, PICS explains the CL increase before UV irradiation. How can this effect disappear afterwards? Other conditions for PICS to take place are that the Schottky barrier between the Au NP and TiO2 has to be (i) high enough to be called a barrier (otherwise the contact would be ohmic, Figure 7a) but not too high so the LSPR energy is sufficient to overcome it and (ii) wide enough so back-transfer charges is not authorized (Figure 7b) [52] .

After UV irradiation, LSPR red shifts from 580 nm to 609 nm (Figure 4). LSPR wavelength is further away from the shallow trap peak and PICS is less likely to happen. The LSPR shifts also means that the permittivity of the Au NPs surrounding medium is greater, in other words less charge carriers are available in the vicinity of the Au NPs, which is consistent with a decrease of the PICS effect (Figure 1a). The case of an ohmic contact between the Au NPs and the TiO2 can also be excluded as it would allow charge transfer from the metal to the semiconductor.

The decrease of the depletion zone width is more likely to explain our observations. Backtransferred charges is coherent with a red shift of the LSPR (less charges in the vicinity of the NP) and the decrease of the interband transition (the energy loss being accomplished via the TiO2). The increase of Ti 3+ defects is associated with an increase of VO as the self-trapped excitons have decreased, we propose that part of these electrons is transferred to the Au NPs.

CL of Au NP drop-casted on the surface of TiO2

The literature so far has reported cases of PIERS using metallic NP on the surface of the semiconductors. Typically, these NPs are synthesized in solution then a drop is deposited and dried on the semi-conductor. We have fabricated such samples for CL experiments before and after UV irradiation. The purpose is to demonstrate that two distinct mechanisms are at stakes when the Au NPs are co-deposited with the TiO2 and drop-casted on the top of the TiO2 surface. Figure 8 shows a TEM image of the Au NPs drop casted on a carbon membrane. The absorption spectrum of this solution displays a peak at 525 nm which corresponds to the LSPR. Figure 8b show the CL spectra obtained before and immediately after UV irradiation on Au NPs drop casted on top of the bare TiO2 which has already been described in the previous paragraph.

Before UV, the spectrum is very similar to the one of bare TiO2, although the intensity of the IR region and the 540 nm peak are less intense. After UV irradiation the intensity of the peaks at 540 nm has decreased and the IR region completely quenched.

Drop casted Au NPs are most sensitive to surface evolution of the TiO2 structure as in this experiment the Au NPs are in contact with the top horizontal surface of the TiO2. Giving the high absorption of TiO2 in the UV, it makes sense that the density of VO created by the UV is greater on the surface. However VO are less mobile than Ti 3+ which migrates inside the bulk [START_REF] Fernàndez | [END_REF] .

As a consequence, CL peaks attributed to VO will be more intense on the surface whereas those associated with Ti 3+ will be found in the bulk. The quenching of the IR peaks here are explained by the fact that the Ti 3+ defects are further away from the surface.

Mechanisms of PIERS

The enhancement in PIERS (Figure 1d) is based on the chemical effect where charges are transferred between the analyte and the nanostructured surface. Until now the proposed mechanism was based on charge injection from VO in TiO2 to Au NPs. This hypothesis is coherent with the CL results presented above for drop casted Au NPs: UV light induces VO preferentially on the surface in position close to the Au NPs.

In the case of embedded Au-TiO2, the position of Au NP partly buried in TiO2 and partly available to MBA grafting imposes another mechanism. The analysis of CL and LSPR results suggests that the depletion zone width is narrower after UV irradiation. This is a consequence of VO formation in the vicinity of the Au NPs. The unique position of the Au NPs in the TiO2 allow them to be a reservoir of electrons from Ti 3+ defects and then to transfer these charges into MBA. This, in turn, is enhancing the chemical effect of the surface enhanced Raman scattering. The defects produced in TiO2 bulk are believed to be less mobile than those at the surface [53,54] . In other words, the duration of the PIERS effect is attributed to durable bulk defects local to the Au NPs.

Conclusions

In conclusion we have studied the PIERS effect on Au NP co-deposited together with TiO2.

The enhancement factor due to UV irradiation of the sample is increases by one order of magnitude which is among the highest values reported in the literature so far. CL experiments allowed us to conclude that this enhancement is due to a back transfer of charges which is typical of PICS in Shottky barrier with narrow depletion zone. The effect is stable in time contrary to what was previously reported thanks to the fact that the Au NPs are in the bulk and grown together with TiO2. The CL analysis highlighted the differences between the mechanisms taking place when Au NPs are drop casted on the surface of the samples and when they are co-deposited with the TiO2. In the first case, VO are formed following UV irradiation, the energy level of the VO is such that it is possible to excite electron transfer from TiO2 to the Au NP with visible light, i.e. the laser used for the Raman scattering. In the second case, defects created by UV irradiation impact the width of the depletion zone and promote back-transfer charges to Au NP. This decreases the number of charges in the surrounding of the Au NPs and red shifts its LSPR. The enhancement of the Raman scattered intensity is possible thanks to the number of electrons in excess on the Au NP. These results demonstrate the influence of the growth mechanism on the PIERS effect. It would be interesting to study further the impact of the material on PIERS in a co-deposition process.

Experimental

Sample growths:

The co-deposition of Au-TiO2 nanostructured films was realized with a composite target made of a TiO2 target, on which three Au plates were attached, in order to reach a 2.9 % of Au coverage. Similarly, bare TiO2 films were grown by ablation of a pure TiO2 target without any Au plates. Target-to-substrate distance value was 5 cm. This condition represents the optimum in terms of interaction between ablated species and surrounding gas, because of low kinetic energy of the ablated species resulting in vertically oriented porous films. Deposition was carried out at room temperature at 8 Pa in oxygen atmosphere. Finally, the samples were annealed at 700 °C in air for 2 hours.

Scanning Electron Microscopy (SEM):

A field emission scanning electron microscope (FEG-SEM, Zeiss Supra 40) was used to perform morphological characterization analyzing films deposited on Si(100) substrate.

Average size distribution of Au NPs was estimated through statistical analysis on SEM images with the open-source software ImageJ ® .

Raman spectroscopy (Sample characterization).

Raman spectra were acquired with a Renishaw InVia micro Raman spectrometer, for the laser excitation wavelength of 514.5 nm (green) and Jobin-Yvon micro-Raman spectrophotometer (Labram 300) for the 633 nm wavelength. In both cases, the power was of 1 mW. The SERS spectra were recorded with the latter spectrometer, using a 100× magnification objective (NA = 0.90) in back-scattering geometry, with a spectral resolution of 3 cm -1 and a spatial resolution of about 1 µm for an acquisition time of 300 s. The typical peak of silicon at 521 cm -1 was used as an internal reference to normalize the intensities of all the spectra. The spectra presented here are the average of five spectra taken on different points of each sample, the details of the five spectra are available in the supplementary information file.

LSP measurements.

The LSPR position was measured thanks to extinction spectroscopy in transmission configuration with a 10x objective (NA=0.25) on an area of 100x100 µm 2 selected by the confocal hole of the Jobin-Yvon micro-Raan spectrophotometer (Labram 300) from which the edge filter was removed. The sample is illuminated was illuminated in normal incidence with collimated white light.

Figure 1 .

 1 Figure 1. Mechanisms of charges transfer between a metallic nanoparticle and a semiconductor: a) PICS, b) PRET, c) Photocatalysis and d) Oxygen vacancy mediated PIERS. The Schottky barrier is described by EF the Fermi level of the metal, VB and CB the valence and conduction band, EG the energy of the band gap and ES the energy of the Schottky barrier.

Figure 2 .

 2 Figure 2. SEM images of the embedded Au-TiO2 before a) and after b) annealing at 700°C. c) and d) are magnifications of respectively a) and b). The scale bar stands for 100 nm

Figure 3 .

 3 Figure 3. Raman of TiO2 with Au NPs deposited at 8 Pa annealed at 700 °C. Spectra were acquired at 514.5 nm (green) and 633 nm (red). The gray dashed lines indicate the theoretical positions of anatase peaks and the yellow dashed lines the theoretical positions of rutile peaks

Figure 4 .

 4 Figure 4. a) Extinction spectra of the sample acquired before UV irradiation (black) and immediately after (blue). The two vertical lines show the position of the laser excitations for Raman experiment. b) Evolution of the LSPR wavelength with time.

Figure 5 .

 5 Figure 5. SERS spectra of MBA deposited on the samples before UV irradiation (black),30 minutes after UV irradiation (blue) and 8 days after UV irradiation (red). For comparison the Raman spectra of MBA powder divide by 3 is plotted in green, and the structure of MBA displayed in inset.

Figure 6 .

 6 Figure 6. CL spectra of bare TiO2 and embedded Au-TiO2 before UV irradiation respectively a) and c) and immediately after UV irradiation respectively b) and d). The experimental data are plotted in black, deconvoluted peaks in green and the sum of these peaks in red.

Figure 7 :

 7 Figure 7: Proposed mechanisms for PIERS in embedded Au-TiO2 a) Ohmic contact (no depletion zone) b) Back electron transfer in PICS with narrow depletion zone (Wd).

Figure 8 .

 8 Figure 8. Au NP drop casted on top of TiO2 surface a) TEM image and absorption spectra showing a peak at 527. b) CL spectra before and after UV irradiation, the CL spectra of bare TiO2 is reminded for comparison.

  Table

		1080 cm -1	1590 cm -1
	Before UV	1	1
	30 minutes after UV	10.2 ± 3.8	9.0 ± 2.6
	8 days after UV	13.2 ± 4.4	8.8 ± 1.9

TiO2 before UV Bare TiO2 after UV Au-TiO2 before UV Au-TiO2 After UV

	380	1	1	1	1
	460	2.6	2.6	17.4	2.9
	540	3.3	3.8	49.8	3.3
	605	2.1	1.9	-	2.1
	660	-	-	39.9	-
	680	0.7	1.2	-	0.7
	750	-	-	0.9	-
	801	0.5	0.4	0.5	0.4
	850	7.2	9.3	0.3	6.7

Table 2 .

 2 Relative intensity of the CL peaks compared to the peak at 380 nm

UV irradiation.

UV irradiation was performed under a UV bulb (λ = 254 nm) of power of 15 W and at distance of about 10 cm between the bulb and substrates, for 3 hours. The extinction spectra were measured immediately after the UV irradiation and at different time after up to one day.

Chemicals.

Mercaptobenzoic acid (MBA), and ethanol were purchased from Sigma Aldrich. MBA was diluted in ethanol at the concentration of 2.9 mM. Embedded Au-TiO2 samples were then soaked in the solution for 30 minutes. Finally, they were thoroughly rinsed with ethanol before drying with nitrogen. The porosity of the film allowed MBA to penetrate along the whole TiO2 film thickness.

The solution of Au NPs drop casted on top of the bare TiO2 was synthesize using the Turkevitch methods which consist in reducing an HAuCl4 salt with sodium citrate.

Cathodoluminescence.

The CL analysis have been performed with a Horiba HCLUE coupled with a scanning electron microscope ZEISS EVO MA15. The CL analysis have been made with an acceleration voltage of the electron beam of 10 kV. The measurement was performed before UV irradiation or immediately after.