Jérémy Domergue

Jacques Pécaut

Olivier Proux

Colette Lebrun

Christelle Gateau

Alan Le Goff

Pascale Maldivi

Carole Duboc
email: carole.duboc@univ-grenoble-alpes.fr

Pascale Delangle
email: pascale.delangle@cea.fr

Alan Le Goff

Mononuclear Ni(II) Complexes with a S3O Coordination Sphere Based on a Tripodal Cysteine-Rich Ligand: pH Tuning of the Superoxide Dismutase Activity

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

Introduction

Superoxide Dismutase (SOD) is a key enzyme in all aerobic organisms as it degrades the radical anion superoxide (O2 • -), one of the toxic reactive oxygen species (ROS), constantly produced as a by-product during aerobic respiration. In the specific case of O2 • -, the SODs protect the cell against severe damage by catalyzing its disproportionation into H2O2 and O2 using a redox-active metallic (M) cofactor (eq. 1 & 2). [START_REF] Sheng | Superoxide Dismutases and Superoxide Reductases[END_REF] M red SOD + O2 • -+ 2H + à H2O2 + M ox SOD eq. 1

M ox SOD + O2 • -à O2 + M red SOD eq. 2
With N/O coordination spheres, the metallic cofactors are Mn, Fe, Cu/Zn or Cu only. [START_REF] Miller | Superoxide dismutases: active sites that save, but a protein that kills[END_REF][START_REF] Tainer | Structure and mechanism of copper, zinc superoxide dismutase[END_REF][START_REF] Grasbon-Frodl | Analysis of Mitochondrial Targeting Sequence and Coding Region Polymorphisms of the Manganese Superoxide Dismutase Gene in German Parkinson Disease Patients[END_REF][START_REF] Grove | SECOND-SPHERE TUNING OF THE METAL ION REDUCTION POTENTIALS IN IRON AND MANGANESE SUPEROXIDE DISMUTASES[END_REF][START_REF] Miller | Redox Tuning over Almost 1 V in a Structurally Conserved Active Site: Lessons from Fe-Containing Superoxide Dismutase[END_REF][START_REF] Tierney | X-ray Absorption Spectroscopy of the Iron Site in Escherichia coli Fe(III) Superoxide Dismutase[END_REF][START_REF] Grove | Spectroscopic and Computational Insights into Second-Sphere Amino-Acid Tuning of Substrate Analogue/Active-Site Interactions in Iron(III) Superoxide Dismutase[END_REF][START_REF] Robinett | Eukaryotic Cu-only superoxide dismutases (SODs): A new class of SOD enzymes and SOD-like protein domains[END_REF] In 1996, a SOD with a thiolate-based Ni complex was discovered. [START_REF] Youn | A novel nickel-containing superoxide dismutase from Streptomyces spp[END_REF] This Ni-SOD has attracted attention of bioinorganic chemists for several reasons. First, this is one of only four enzymes that contain a mononuclear Ni catalytic center (in addition to acireductone dioxygenase, glyoxylase and methyl-coenzyme M reductase). [START_REF] Sigel | Nickel and Its Surprising Impact in Nature[END_REF] Second, the coordination sphere of the Ni II ion is intriguing with the presence of two cysteinates, bearing in mind that metal-bound thiolates are well known to react with O2 • -and even O2 and H2O2, leading to oxidative damage. [START_REF] Grapperhaus | Oxygen capture by sulfur in nickel thiolates[END_REF][START_REF] Kaasjager | Unique Reactivity of a Tetradentate N2S2 Complex of Nickel:  Intermediates in the Production of Sulfur Oxygenates[END_REF] Third, the coordination sphere of the Ni site is completed by donor ligands from only the first six amino acids of the N terminal part of the peptide chain, in an original motif involving the terminal amine and an amidate in the Ni II reduced state. The square plane around the Ni II ion becomes a square pyramid in the Ni III state, with the additional coordination of an imidazole of a histidine in the axial position (Scheme 1). [START_REF] Barondeau | Nickel superoxide dismutase structure and mechanism[END_REF][START_REF] Wuerges | Crystal structure of nickel-containing superoxide dismutase reveals another type of active site[END_REF][START_REF] Choudhury | Examination of the nickel site structure and reaction mechanism in Streptomyces seoulensis superoxide dismutase[END_REF] Apart from the characterization of these two states (oxidized and reduced) that are involved in a ping-pong mechanism, nothing is known about the mechanism of the NiSOD.

Scheme 1. Active and catalysed reaction centre by the NiSOD

With the aim of better understanding the key-elements of this active site, chemists have designed bio-inspired synthetic complexes to investigate the role of the amidate for the SOD activity, the stability of the thiolates in catalytic conditions, the role of the axial ligand, and finally, the different possible mechanisms to probe inner or outer sphere processes. To address these questions, two strategies have been followed based on Ni II complexes either designed with peptide-based ligands [START_REF] Shearer | A Nickel Superoxide Dismutase Maquette That Reproduces the Spectroscopic and Functional Properties of the Metalloenzyme[END_REF][START_REF] Neupane | The influence of amine/amide versus bisamide coordination in nickel superoxide dismutase[END_REF][START_REF] Schmidt | Solution structure of a functional biomimetic and mechanistic implications for nickel superoxide dismutases[END_REF][START_REF] Tietze | New Insight into the Mode of Action of Nickel Superoxide Dismutase by Investigating Metallopeptide Substrate Models[END_REF][START_REF] Shearer | Metallopeptide Based Mimics with Substituted Histidines Approximate a Key Hydrogen Bonding Network in the Metalloenzyme Nickel Superoxide Dismutase[END_REF][START_REF] Krause | Novel Tripeptide Model of Nickel Superoxide Dismutase[END_REF][START_REF] Tietze | Development of a Functional cis-Prolyl Bond Biomimetic and Mechanistic Implications for Nickel Superoxide Dismutase[END_REF][START_REF] Krause | MAPping the Chiral Inversion and Structural Transformation of a Metal-Tripeptide Complex Having Ni-Superoxide Dismutase Activity[END_REF][START_REF] Tietze | Revealing the Position of the Substrate in Nickel Superoxide Dismutase: A Model Study[END_REF][START_REF] Shearer | Cysteinate Protonation and Water Hydrogen Bonding at the Active-Site of a Nickel Superoxide Dismutase Metallopeptide-Based Mimic: Implications for the Mechanism of Superoxide Reduction[END_REF][START_REF] Broering | Synthetic Analogues of Nickel Superoxide Dismutase: A New Role for Nickel in Biology[END_REF] or synthetic ligands. [START_REF] Broering | Synthetic Analogues of Nickel Superoxide Dismutase: A New Role for Nickel in Biology[END_REF][START_REF] Shearer | Me4N](NiII(BEAAM)): A Synthetic Model for Nickel Superoxide Dismutase That Contains Ni in a Mixed Amine/Amide Coordination Environment[END_REF][START_REF] Mullins | Synthesis and Sulfur Oxygenation of a (N3S)Ni Complex Related to Nickel-Containing Superoxide Dismutase[END_REF][START_REF] Jenkins | Imidazole-Containing (N3S)-NiII Complexes Relating to Nickel Containing Biomolecules[END_REF][START_REF] Gale | Versatile Methodology Toward NiN2S2 Complexes as Nickel Superoxide Dismutase Models: Structure and Proton Affinity[END_REF][START_REF] Ma | Scorpionatesupported models of nickel-dependent superoxide dismutase[END_REF][START_REF] Gale | Exploring the Effects of H-Bonding in Synthetic Analogues of Nickel Superoxide Dismutase (Ni-SOD): Experimental and Theoretical Implications for Protection of the Ni-SCys Bond[END_REF][START_REF] Mathrubootham | Bisamidate and Mixed Amine/Amidate NiN2S2 Complexes as Models for Nickel-Containing Acetyl Coenzyme A Synthase and Superoxide Dismutase: An Experimental and Computational Study[END_REF][START_REF] Gennari | Reversible Apical Coordination of Imidazole between the Ni(III) and Ni(II) Oxidation States of a Dithiolate Complex: A Process Related to the Ni Superoxide Dismutase[END_REF][START_REF] Gale | Toward Functional Ni-SOD Biomimetics: Achieving a Structural/Electronic Correlation with Redox Dynamics[END_REF][START_REF] Gale | Dipeptide-Based Models of Nickel Superoxide Dismutase: Solvent Effects Highlight a Critical Role to Ni-S Bonding and Active Site Stabilization[END_REF][START_REF] Herdt | Kinetic study of nickel-thiolate oxygenation by hydrogen peroxide. Implications for nickel-containing superoxide dismutase[END_REF][START_REF] Lee | A Discrete Five-Coordinate NiIII Complex Resembling the Active Site of the Oxidized Form of Nickel Superoxide Dismutase[END_REF][START_REF] Nakane | A Novel Square-Planar Ni(II) Complex with an Amino-Carboxamido-Dithiolato-Type Ligand as an Active-Site Model of NiSOD[END_REF][START_REF] Chiang | Synthesis and Characterization of NiIIIN3S2 Complexes as Active Site Models for the Oxidized Form of Nickel Superoxide Dismutase[END_REF][START_REF] Broering | Accessing Ni(III)-Thiolate Versus Ni(II)-Thiyl Bonding in a Family of Ni-N2S2 Synthetic Models of NiSOD[END_REF] Because only the first residues of the N-terminal part are involved, the reported peptide-based models mainly contain between 7 and 12 residues. They closely reproduce the spectroscopic features of the Ni-SOD and the SOD reactivity, although still with less efficiency. [START_REF] Shearer | Insight into the Structure and Mechanism of Nickel-Containing Superoxide Dismutase Derived from Peptide-Based Mimics[END_REF] From their investigation, it was evidenced that the presence of a residue that can axially coordinate to the Ni site drastically enhances the activity but is not critical. [START_REF] Neupane | Probing variable axial ligation in nickel superoxide dismutase utilizing metal lopeptide-based models: Insight into the superoxide disproportionation mechanism[END_REF][START_REF] Tietze | New insights into the mechanism of nickel superoxide degradation from studies of model peptides[END_REF] The first series of synthetic bioinspired complexes have evidenced that mixed amidate/amine coordination sphere allows for fine-tuning the redox properties of the bis-thiolate Ni motif in order to protect, at least partially, sulfur-centered degradation processes. [START_REF] Truong | Steric Enforcement about One Thiolate Donor Leads to New Oxidation Chemistry in a NiSOD Model Complex[END_REF][START_REF] Huang | The Role of Mixed Amine/Amide Ligation in Nickel Superoxide Dismutase[END_REF] The role of the fifth ligand in the axial position to stabilize the Ni III oxidation state has been also reproduced. [START_REF] Gennari | Reversible Apical Coordination of Imidazole between the Ni(III) and Ni(II) Oxidation States of a Dithiolate Complex: A Process Related to the Ni Superoxide Dismutase[END_REF][START_REF] Chiang | Synthesis and Characterization of NiIIIN3S2 Complexes as Active Site Models for the Oxidized Form of Nickel Superoxide Dismutase[END_REF][START_REF] Broering | Accessing Ni(III)-Thiolate Versus Ni(II)-Thiyl Bonding in a Family of Ni-N2S2 Synthetic Models of NiSOD[END_REF] However, the great majority of the low-molecular weight synthetic Ni II complexes, despite their apparent appropriate redox properties for SOD activity, are not active as catalysts even if they can mimic the partial [START_REF] Nakane | A Novel Square-Planar Ni(II) Complex with an Amino-Carboxamido-Dithiolato-Type Ligand as an Active-Site Model of NiSOD[END_REF][START_REF] Chiang | Synthesis and Characterization of NiIIIN3S2 Complexes as Active Site Models for the Oxidized Form of Nickel Superoxide Dismutase[END_REF] or full [START_REF] Chatterjee | Hexacoordinate Nickel(II)/(III) Complexes that Mimic the Catalytic Cycle of Nickel Superoxide Dismutase[END_REF] catalytic cycle under stoichiometric conditions. Their lack of reactivity has often been rationalized either by their sensitivity to the superoxide or derivatives, or by the irreversibility of the Ni III /Ni II redox process. [START_REF] Gale | Dipeptide-Based Models of Nickel Superoxide Dismutase: Solvent Effects Highlight a Critical Role to Ni-S Bonding and Active Site Stabilization[END_REF] Finally, these two bio-inspired strategies have led to the proposal of different mechanisms for the NiSOD reactivity, with the disproportionation of the superoxide occurring through either inner [START_REF] Krause | MAPping the Chiral Inversion and Structural Transformation of a Metal-Tripeptide Complex Having Ni-Superoxide Dismutase Activity[END_REF][START_REF] Nakane | A Novel Square-Planar Ni(II) Complex with an Amino-Carboxamido-Dithiolato-Type Ligand as an Active-Site Model of NiSOD[END_REF] or outer [START_REF] Chatterjee | Hexacoordinate Nickel(II)/(III) Complexes that Mimic the Catalytic Cycle of Nickel Superoxide Dismutase[END_REF][START_REF] Truong | Simultaneous nitrosylation and N-nitrosation of a Ni-thiolate model complex of Nicontaining SOD[END_REF] sphere pathways.

To evaluate the importance of the amidate/amine N-donor environment to produce active SOD Ni-based catalysts, we report here the investigation of two mononuclear Ni II SOD catalysts based on a sulfur-rich pseudo-peptide ligand. This so-called pseudo-peptide is derived from nitrilotriacetic acid (NTA), with the three acid functions grafted with cysteines (L 3S in Scheme 2).

Such architectures with amino acids anchored on a tripodal chemical scaffold are highly soluble in water, and hence, their complexes' properties can be studied in conditions relevant to biology.

They have been demonstrated to promote the coordination of three sulfur donors from either cysteines, D-penicillamines, or methionines to soft metal ions. [START_REF] Pujol | A Cysteine-Based Tripodal Chelator with a High Affinity and Selectivity for Copper(I)[END_REF][START_REF] Pujol | A Series of Tripodal Cysteine Derivatives as Water-Soluble Chelators that are Highly Selective for Copper(I)[END_REF][START_REF] Pujol | Mercury-Sequestering Pseudopeptides with a Tris(cysteine) Environment in Water[END_REF][START_REF] Jullien | Mercury Complexes with Tripodal Pseudopeptides Derived from D-Penicillamine Favour a HgS3 Coordination[END_REF][START_REF] Jullien | D-Penicillamine Tripodal Derivatives as Efficient Copper(I) Chelators[END_REF][START_REF] Jullien | Pseudo-peptides Based on Methyl Cysteine or Methionine Inspired from Mets Motifs Found in the Copper Transporter Ctr1[END_REF] In particular, the coordination properties of L 3S for Cu I resemble those of the detoxification proteins, i.e. metallothioneins, [START_REF] Jullien | X-ray Absorption Spectroscopy Proves the Trigonal-Planar Sulfur-Only Coordination of Copper(I) with High-Affinity Tripodal Pseudopeptides[END_REF] and have been exploited to design a very efficient Cu intracellular chelator. 57 L 3S stabilizes the trigonal planar coordination of Cu I with three thiolates in very stable complexes in water at physiological pH: a mononuclear complex under (sub)stoichiometric conditions of Cu I and a well-defined Cu I -thiolate Cu6S9 cluster in excess of Cu I . [START_REF] Pujol | A Series of Tripodal Cysteine Derivatives as Water-Soluble Chelators that are Highly Selective for Copper(I)[END_REF] Interestingly, a similar pseudo-peptide ligand derived from histidine in place of cysteine moieties was demonstrated to coordinate both Cu I and Cu II oxidation states in very different geometries: Cu I was found in a tetrahedral geometry whereas Cu II was demonstrated to be in a distorted square planar geometry. [START_REF] Conte-Daban | A Trishistidine Pseudopeptide with Ability to Remove Both Cu-I and Cu-II from the Amyloid-beta Peptide and to Stop the Associated ROS Formation[END_REF] This highlights the versatility of the coordination environments that can be accessed with such tripodal peptide-like architectures. Interestingly, the complex found at physiological pH, NiL 3S (OH2), exhibits catalytic SOD activity, whereas the hydroxo species NiL 3S (OH) does not. This difference in reactivity is interpreted on the basis of the spectroscopic data.

Results

Evidence for Ni II complex formation with L 3S at pH 7.4. The synthesis of the L 3S ligand has been previously described. [START_REF] Pujol | A Series of Tripodal Cysteine Derivatives as Water-Soluble Chelators that are Highly Selective for Copper(I)[END_REF] Because of the sensitivity of the thiolate-based Cu I complexes and clusters characterized before with L 3S and derivatives towards O2 oxidation, the investigation of the coordination of Ni II with L 3S has been carried out under anaerobic conditions. The complexation properties of L 3S have been studied by UV-visible spectroscopy, since intense ligand-to-metal-charge transfer (LMCT) features from the thiolates to Ni II are expected in the UV region. [START_REF] Stetson | A new material with alternating metal-oxide and metal-phosphide layers: barium manganese phosphate (Ba2Mn3P2O2)[END_REF][START_REF] Stibrany | Structural and Spectroscopic Features of Mono-and Binuclear Nickel(II) Complexes with Tetradentate N(amine)2S(thiolate)2 Ligation[END_REF] Aliquots of Ni II (NiSO4) have been added to a solution of L 3S in HEPES buffer (20 mM, pH 7.4, [NaCl]=100 mM), from 0 to 4 equiv. per ligand, and the titration is reported in Figure 1.

While the L 3S solution displays no UV-vis transition above 250 nm, addition of Ni II leads to the appearance of two intense bands at 289 nm (ε = 10 500 M -1 cm -1 ) and 345 nm (ε = 6 300 M -1 cm -1 ), assigned to the expected LMCTs and a broad and less intense band at 462 nm (ε = 1 000 M -1 cm -1 )

that could be tentatively attributed to a d-d transition. [START_REF] Cotton | Advanced Inorganic Chemistry[END_REF] The inset of Figure 1 displays the variations of the molar absorption coefficients (ε) of these main bands with the number of Ni II equiv. added. The regular increase of the ε up to 1 equiv. points to the formation of one complex, which evolves into a second species from 1 to 2 equiv. A plateau is then observed after 2 equiv.

These data are consistent with the successive formation of two Ni II complexes depending on the number of equivalents of Ni II per ligand (1 equiv. and 2 equiv., respectively). To confirm this analysis, circular dichroism (CD) experiments have been carried out. Spectra in black correspond to samples between 0 and 1 equiv. of Ni II per L 3S , spectra in blue correspond to samples between 1 and 2 equiv. of Ni II . Inset: evolution of the absorbance at 289 nm and 345 nm.

The CD titration in HEPES buffer (20 mM, pH 7.4, [NaCl]=100 mM) is represented in Figure 2 and confirms the formation of two successive Ni II complexes with notably different CD features.

Only one complex is formed in Ni II -limiting conditions as shown by the isodichroic points at 286, 314, and 462 nm. The spectrum is dominated by two main bands at 298 nm (+) and 351 nm (-) that can be attributed to S -à Ni II LMCT, [START_REF] Kozlowski | Nickel(II) complexes with sulfhydryl containing peptides. potentiometric and spectroscopic studies[END_REF] and one at 405 nm (-) assigned to a d-d transition as an indication of a square planar geometry. [START_REF] Chang | Visible circular dichroism of planar nickel ion complexes of peptides and cysteine and derivatives[END_REF] The spectrum dramatically changes between 1 and 2 Ni II equiv. (main bands in the new spectrum at 248 nm (+), 282 nm (-), 307 nm (-), 378 nm (-), 440 nm (+), 562 nm (+)), with no further evolution with a larger excess of metal ion.

Interestingly, isodichroic points (at 333, 357, 404 and 533 nm) are also observed from 1 to 2 equiv. of Ni II , in agreement with an equilibrium between two distinct complexes only. Based on these experiments, it can be proposed that with up to 1 equiv. of Ni II , a mononuclear complex corresponding to a Ni:L 3S 1:1 ratio is exclusively formed. This complex transforms into the higher nuclearity Ni:L 3S 2:1 species in excess of Ni II . Spectra in black correspond to samples between 0 and 1 equiv. of Ni II per L 3S , spectra in blue correspond to samples between 1 and 2 equiv. of Ni II . Inset: evolution of the absorbance at 300 nm, 350 nm and 440 nm.

The electrospray ionization mass spectrometry experiments (ESI-MS) performed in ammonium acetate aqueous solution (20 mM, pH 6.9) are consistent with these spectroscopic observations (Figure S1). Indeed, in Ni II limiting conditions, the main ion detected in the (-)ESI-MS spectrum is Overall, these data acquired at pH 7.4 evidence that, up to 1 Ni II equiv., only one species is formed, corresponding to a mononuclear complex with a 1:1 stoichiometry. Considering the large molar absorption coefficient of the S -to Ni II LMCT bands and based on the following NMR and XAS spectroscopic studies, this complex is proposed to contain three S-donor atoms arising from the three cysteines and one O-donor atom arising from a water molecule (vide infra) in a square planar geometry: [NiL 3S (OH2)] -. The following experiments focus on the latter species, formed under slightly sub-stoichiometric conditions (Ni:L 3S 0.9:1) to fully avoid the formation of the 2:1 complex.

Evolution with pH. The pH effect on the speciation of the Ni II complexes was investigated by UV-vis and CD spectroscopy from pH 4 to pH 11 by the successive addition of potassium hydroxide (KOH) into a water solution of Ni:L 3S 0.9:1 (Figure 3). The characteristic transitions previously identified for NiL 3S (OH2) at pH 7.4, at 289, 345 and 462 nm, are detected starting as low as pH 5.3. The maximum amount of this species is formed at pH 6.9. Above pH 7.5, the initial species evolves exclusively into a second species, NiL 3S (OH), as attested by the presence of three isobestic points at 290, 312 and 337 nm. The two LMCT bands are shifted to 270 nm (ε = 15 800 M -1 cm -1 ) and 325 nm (ε = 8 600 M -1 cm -1 ), and the d-d band to 483 nm (ε = 270 M -1 cm -1 ). The formation of these two pH dependent species is confirmed by CD experiments (Figure S3).

Between pH 7.0 and 11.0, the evolution of the CD spectra leads to five isodichroic points with notable changes between the spectra recorded at pH 7.1 and that at pH 10.6. ESI-MS was used to investigate the nuclearity of the second species, and the spectrum recorded at pH 9.5 in ammonium acetate buffer displays the same peak as observed at pH 6.9, corresponding to a 1:1 nuclearity (Ni:L 3S ). The modeling of the effect of the pH on the intensity of the absorbance across the full UV-Vis spectral range has been carried out using SPECFIT software [START_REF] Gampp | Calculation of equilibrium constants from multiwavelength spectroscopic data-II132, 95.: Specfit: two userfriendly programs in basic and standard fortran 77[END_REF][START_REF] Gampp | Calculation of equilibrium constants from multiwavelength spectroscopic data-III: Model-free analysis of spectrophotometric and ESR titrations[END_REF][START_REF] Gampp | Calculation of equilibrium constants from multiwavelength spectroscopic data-I: Mathematical considerations[END_REF] (the evolution at 270 nm is depicted in the inset of Figure 3). Two deprotonation events are observed around pH 6.0 and pH 8.5, involving 3 and 1 proton(s), respectively. These data are consistent with the formation of NiL 3S (OH2), which requires the deprotonation of the three thiol functions of the cysteines with a corresponding logβ 110 value of 14.6. This high equilibrium constant value evidences the high stability of the complex; for comparison the Ni II complexes with two successive cysteines -Cys-Cys-display one to three orders of magnitude lower affinity for Ni II with logβ110 = 12.2-13.5. [START_REF] Rowinska-Zyrek | The -Cys-Cys-motif in Helicobacter pylori's Hpn and HspA proteins is an essential anchoring site for metal ions[END_REF] At higher pH, the second increase reflects another deprotonation assigned to the generation of a hydroxo ligand, leading to the NiL 3S (OH) species. A pKa of 8.6 is thus experimentally determined for a Ni II -bound water molecule in a square planar environment. This value is difficult to compare with literature data. Indeed, to the best of our knowledge, acidity constants for Ni II -bound water molecules are reported for six-coordinate Ni II complexes only: for instance the experimental pKa value for [Ni(OH2)6] 2+ is 9.9. [START_REF] Gilson | Estimation of the pKa values of water ligands in transition metal complexes using density functional theory with polarized continuum model solvent corrections[END_REF] The Ni II species distribution profile with pH, depicted in Figure S4, shows that the major complex at physiological pH is NiL 3S (OH2) (> 97% at pH 7 and > 94% at pH 7.4), whereas NiL 3S (OH) becomes predominant above pH 9. The spectrum of NiL 3S (OH) did not show significant evolution with temperature, from 278 K to 308 K, as seen in Figure S6. All peaks of the 1 H NMR spectrum at 278 K, recorded in light water at pH 10.1, have been attributed based on a detailed analysis of 2D-NMR experiments leading to structural information (Table S1). Whereas the primary amide NH2 protons are not detected in light water, as expected for such a high pH, the NH protons of the 3 secondary amide functions are detected as narrow doublets. Indeed, these latter protons exhibit low temperature coefficients (between -1 and -3 ppb/K), characteristic of their involvement in intra-molecular hydrogen bond interactions. [69][70] This also confirms that the secondary amides are not deprotonated at pH 10.1, and therefore not coordinated to the Ni II ion. Interestingly, the proton of the hydroxo ligand coordinated to the Ni II ion has been detected as a large signal at 3.9 ppm, integrating for 1 proton, which disappears with D2O addition. A strong NOE correlation in the 2D-NOESY spectrum indicates that this hydroxo proton is close to one of the Hβ protons from a cysteine (see NOESY in Figure S5). Besides, its temperature coefficient (δΔ/ΔT = -3 ppb/K) also shows an intra-molecular hydrogen interaction. All of these interactions lead to an embedded environment around the Ni-OH unit allowing the observation of its 1 H NMR signal. The overall data confirm that at pH 10.1, the coordination sphere of the Ni II ion is completed by the three thiolates of L 3S and a hydroxo ligand in a square planar geometry.

While the structure of NiL 3S (OH) is dissymmetric and rigid, as attested by sharp and well resolved peaks, the 1 H NMR spectrum of NiL 3S (OH2) indicates that dynamic processes occur on the NMR timescale. The signals of NiL 3S (OH2) are very broad at room temperature and although some of them are better resolved by lowering the temperature to 278 K, it was not possible to get a well-resolved spectrum for this complex (Figure S7). This is consistent with the presence of an exchangeable water molecule at pH 7.2 instead of a strongly coordinated hydroxo molecule at pH 10.1. The exchange of the Ni-bound water molecule between the 4 different positions accessible in the square-planar geometry and the intrinsic dissymmetry of the complex leads to a spectrum displaying unresolved and broad peaks that could not be investigated in more detail.

XAS characterization of the two complexes. Ni K-edge X-ray absorption spectroscopy (XAS)

has been used to probe the local chemical, electronic, and structural environment of the Ni II ion in NiL 3S (OH2) and NiL 3S (OH). While the X-ray absorption near-edge structure (XANES) is informative regarding the geometry as well as the spin and oxidation state of the metal ion, the X-ray absorption fine structure (EXAFS) provides information about the coordination sphere and metal-ligand distances. The XAS spectra of NiL 3S (OH2) and NiL 3S (OH) are very similar. The XANES spectra display a weak pre-edge transition at 8333 eV that is assigned to a Ni (1sà3d) transition (Figure 6). [START_REF] Colpas | X-ray spectroscopic studies of nickel complexes, with application to the structure of nickel sites in hydrogenases[END_REF] Such a feature is formally dipole forbidden, but can gain intensity in noncentrosymmetric coordination environments through mixing between the 4p and 3d orbitals. An additional shoulder at 8338 eV is observed, attributed to a Ni (1sà4pz) transition. Such transitions are only observed in complexes with four-coordinate planar or five-coordinate pyramidal geometries. The presence of both a weak pre-edge peak and a Ni (1sà4pz) transition evidences a square planar geometry for both complexes NiL 3S (OH2) and NiL 3S (OH). [START_REF] Colpas | X-ray spectroscopic studies of nickel complexes, with application to the structure of nickel sites in hydrogenases[END_REF] The presence of more than two S-donor atoms in the coordination sphere of the Ni II ion in NiL 3S (OH2)

and NiL 3S (OH) is proposed based on the comparison of their XANES spectra with that of a reference Ni complex with a N2S2 environment: [START_REF] Gennari | Reversible Apical Coordination of Imidazole between the Ni(III) and Ni(II) Oxidation States of a Dithiolate Complex: A Process Related to the Ni Superoxide Dismutase[END_REF] (i) the slopes of the edges for NiL 3S (OH2) and NiL 3S (OH) are smaller than that of the Ni(N2S2) complex and (ii) their edges are shifted to a lower energy. Such observations are consistent with the fact that the presence of polarizable ligands such as thiolates decreases the positive charge density on the Ni II ion. S2 for more details). These structural data are fully consistent with the EXAFS data.

In agreement with the NMR and XANES data, only the singlet state leads to a true energy minimum checked with all real frequencies (see computational details in SI). The TD-DFT predicted UV-vis properties of both complexes are consistent with the experimental data. The two main transitions experimentally observed at around 300 nm and 340 nm are calculated at 295 nm and 343 nm for NiL 3S (OH2). In the case of NiL 3S (OH), the experimental shifts to higher energies of both transitions are also well reproduced at 272 nm and 323 nm (see Figure S13). An analysis of these transitions confirmed their LMCT nature, being mainly S (p orbitals) to Ni (dx²-y²) excitations.

Redox properties of NiL 3S (OH2) and NiL 3S (OH). The cyclic voltammograms (CVs) of NiL 3S (OH2)

and NiL 3S (OH) have been recorded in HEPES solutions buffered at pH 7.4 and 9.5, respectively (Figure 8). The CV of NiL 3S (OH2) displays only one irreversible oxidation process at Epa = 0.48 V vs SCE that can be attributed to the oxidation of Ni II into Ni III . The CV of NiL 3S (OH) reveals the presence of two irreversible oxidation processes at Epa = 0.31 V and Epa = 0.59 V vs SCE. Since it is expected that the exchange of a water by a hydroxo ligand should decrease the oxidation potential of the Ni II ion (charge effect), the first redox system is assigned to Ni II àNi III .

Furthermore, the current intensity of this irreversible oxidation was compared with the reversible reduction of the redox probe Ru III (NH3)6Cl3 in HEPES. Similar current intensity for this system corroborates the monoelectronic nature of the oxidation of both NiL 3S (OH2) and NiL 3S (OH). The second redox system is consistent with the oxidation of the ligand (see the CV of the ligand in Figure S10). Because the first oxidation is irreversible at all scan rates in the range 10 mV.S -1 -1 V.s -1 , the Ni III species is unstable and it can be proposed that its degradation releases the ligand into the solution. Interestingly, the anodic potentials to oxidize both complexes are in an appropriate redox range to achieve SOD activity (Eox(O2 • -) = -0.2 V; Ered(O2 • -) = 0.85 V vs SCE). In this assay, superoxide is produced constantly by the enzyme and reacts with the para-nitro blue tetrazolium chloride (NBT) to generate the blue pigment formazan (λ max ≈ 560 nm (∼35 000 M -1 cm -1 )). On the other hand, when a SOD catalyst is added to the system, the generation of formazan decreases because the catalyst prevents the oxidation of NBT by O2 • -through its consumption (Scheme S1). An IC50 of about 1 µM has been measured at pH 7.4 for NiL 3S (OH2) (Figure S11), which represents 93% of the Ni II species in these conditions. For comparison, controls with the ligand or the Ni II salt alone showed no activity (See Figure S12B andC). The catalytic activity of NiL 3S (OH2) is similar to that reported for peptide-based nickel models, [START_REF] Neupane | Probing variable axial ligation in nickel superoxide dismutase utilizing metal lopeptide-based models: Insight into the superoxide disproportionation mechanism[END_REF] but lower than the one reported for CuZn-SOD (4 10 -8 M).

However, the IC50 is larger than 100 µM at pH 9.6, where NiL 3S (OH) is the major Ni II species (92%). Although the structures of the two complexes only differ in their coordination by the presence of a water molecule or a hydroxo anion, only the NiL 3S (OH2) displays SOD activity.

To confirm these data, stopped-flow experiments have been conducted, where superoxide in DMSO is mixed with an aqueous solution of the complex. In this method, the consumption of superoxide is monitored by UV-vis spectroscopy under catalytic conditions. Without any catalyst, the self-disproportionation of superoxide follows a second order rate law. When an SOD-active molecule is added, the reaction rate becomes pseudo first order. For such measurements, high pH (around pH 8) should be preferred to slow down the O2 • -self-disproportionation reaction.

However, since the NBT/formazan assay evidences a better activity for NiL 3S (OH2), the activity has been tested at pH 7.75, where the ratio between NiL 3S (OH2) / NiL 3S (OH) is about (86:14).

Under these conditions, the rate constant for the superoxide self-disproportionation reaction was found to be kcat = 3(1) 10 4 M -1 s -1 . As expected, the reaction between O2 • -and NiL 3S (OH2) is faster than the self-disproportionation reaction and follows a first order rate law (Figure 9). The experiments have been done at different concentrations to determine the rate constant, kcat = 1.8 10 5 M -1 s -1 . Even though the reaction is much faster between O2 • -and Ni-SOD at pH 8 (kcat ∼ 1 10 9 M -1 s -1 ), [START_REF] Bryngelson | Expression, reconstitution, and mutation of recombinant Streptomyces coelicolor NiSOD[END_REF] it is the first nickel complex displaying activity under catalytic conditions with a coordination that notably differs from that of the enzyme, i.e. with no N-based donor ligand (S3O vs S2N2). NiL 3S (OH2) also displays a sulfur rich environment, a specific originality of the NiSOD with respect to the other SOD enzymes, evidencing the key role of the cysteines in the environment of the Ni ion. Interestingly, the absorption of the solution at 289 nm is similar before and after the catalysis suggesting that NiL 3S (OH2) is robust under catalytic conditions.

Discussion.

Currently, only bio-inspired peptide-based SOD complexes display catalytic SOD reactivity, [START_REF] Shearer | A Nickel Superoxide Dismutase Maquette That Reproduces the Spectroscopic and Functional Properties of the Metalloenzyme[END_REF][START_REF] Neupane | The influence of amine/amide versus bisamide coordination in nickel superoxide dismutase[END_REF][START_REF] Schmidt | Solution structure of a functional biomimetic and mechanistic implications for nickel superoxide dismutases[END_REF][START_REF] Tietze | New Insight into the Mode of Action of Nickel Superoxide Dismutase by Investigating Metallopeptide Substrate Models[END_REF][START_REF] Shearer | Metallopeptide Based Mimics with Substituted Histidines Approximate a Key Hydrogen Bonding Network in the Metalloenzyme Nickel Superoxide Dismutase[END_REF][START_REF] Krause | Novel Tripeptide Model of Nickel Superoxide Dismutase[END_REF][START_REF] Tietze | Development of a Functional cis-Prolyl Bond Biomimetic and Mechanistic Implications for Nickel Superoxide Dismutase[END_REF][START_REF] Krause | MAPping the Chiral Inversion and Structural Transformation of a Metal-Tripeptide Complex Having Ni-Superoxide Dismutase Activity[END_REF][START_REF] Tietze | Revealing the Position of the Substrate in Nickel Superoxide Dismutase: A Model Study[END_REF][START_REF] Shearer | Cysteinate Protonation and Water Hydrogen Bonding at the Active-Site of a Nickel Superoxide Dismutase Metallopeptide-Based Mimic: Implications for the Mechanism of Superoxide Reduction[END_REF] while the low-molecular weight synthetic Ni II complexes are not active as catalysts, [START_REF] Shearer | Me4N](NiII(BEAAM)): A Synthetic Model for Nickel Superoxide Dismutase That Contains Ni in a Mixed Amine/Amide Coordination Environment[END_REF][START_REF] Mullins | Synthesis and Sulfur Oxygenation of a (N3S)Ni Complex Related to Nickel-Containing Superoxide Dismutase[END_REF][START_REF] Jenkins | Imidazole-Containing (N3S)-NiII Complexes Relating to Nickel Containing Biomolecules[END_REF][START_REF] Gale | Versatile Methodology Toward NiN2S2 Complexes as Nickel Superoxide Dismutase Models: Structure and Proton Affinity[END_REF][START_REF] Ma | Scorpionatesupported models of nickel-dependent superoxide dismutase[END_REF][START_REF] Gale | Exploring the Effects of H-Bonding in Synthetic Analogues of Nickel Superoxide Dismutase (Ni-SOD): Experimental and Theoretical Implications for Protection of the Ni-SCys Bond[END_REF][START_REF] Mathrubootham | Bisamidate and Mixed Amine/Amidate NiN2S2 Complexes as Models for Nickel-Containing Acetyl Coenzyme A Synthase and Superoxide Dismutase: An Experimental and Computational Study[END_REF][START_REF] Gennari | Reversible Apical Coordination of Imidazole between the Ni(III) and Ni(II) Oxidation States of a Dithiolate Complex: A Process Related to the Ni Superoxide Dismutase[END_REF][START_REF] Gale | Toward Functional Ni-SOD Biomimetics: Achieving a Structural/Electronic Correlation with Redox Dynamics[END_REF][START_REF] Gale | Dipeptide-Based Models of Nickel Superoxide Dismutase: Solvent Effects Highlight a Critical Role to Ni-S Bonding and Active Site Stabilization[END_REF][START_REF] Herdt | Kinetic study of nickel-thiolate oxygenation by hydrogen peroxide. Implications for nickel-containing superoxide dismutase[END_REF][START_REF] Lee | A Discrete Five-Coordinate NiIII Complex Resembling the Active Site of the Oxidized Form of Nickel Superoxide Dismutase[END_REF][START_REF] Nakane | A Novel Square-Planar Ni(II) Complex with an Amino-Carboxamido-Dithiolato-Type Ligand as an Active-Site Model of NiSOD[END_REF][START_REF] Chiang | Synthesis and Characterization of NiIIIN3S2 Complexes as Active Site Models for the Oxidized Form of Nickel Superoxide Dismutase[END_REF][START_REF] Broering | Accessing Ni(III)-Thiolate Versus Ni(II)-Thiyl Bonding in a Family of Ni-N2S2 Synthetic Models of NiSOD[END_REF] even if they can react with O2 • -, and despite efforts made to reproduce the key structural elements of the active site of the Ni-SOD. In this context, recent studies report on complexes with coordination spheres that deviate from an exact mimicry with the aim of probing the different mechanisms that can be involved and determining structure/activity correlations. Here, we proposed an original approach based on a pseudo-peptide ligand that leads to square-planar Ni complexes without N-donor atom in the Ni coordination sphere, but instead, an aquo or hydroxo ligand not present in the active site of the Ni-SOD.

The characterization of the two planar S3O Ni II complexes [NiL 3S (OH2)] -(NiL 3S (OH2)) and [NiL 3S (OH)] 2-(NiL 3S (OH)) has revealed that the ratio of these two species is pH dependent in aqueous solutions with a pKa of 8.6 for the water molecule bound to the Ni site. The pH speciation also shows that at physiological pH, the three sulphur atoms bound to the Ni II ion belong to deprotonated thiolate functions from the cysteine residues. Therefore, in the SODactive complex NiL 3S (OH2), the cysteine moieties are not protonated. This conclusion is in contrast to that arising from an investigation carried out on metallopeptide based models for which it has been proposed that protonation of one of the cysteines occurs during the catalytic mechanism. [START_REF] Shearer | Cysteinate Protonation and Water Hydrogen Bonding at the Active-Site of a Nickel Superoxide Dismutase Metallopeptide-Based Mimic: Implications for the Mechanism of Superoxide Reduction[END_REF] However, this is perfectly consistent with a more recent study performed on similar maquettes that evidences that the cysteine residues are not protonated. [START_REF] Tietze | NiII Complex Formation and Protonation States at the Active Site of a Nickel Superoxide Dismutase-Derived Metallopeptide: Implications for the Mechanism of Superoxide Degradation[END_REF] The SOD efficiency of NiL 3S (OH2) (IC50 ∼ 1 10 -6 M, pH 7.4) is lower than that of the NiSOD (IC50 = 4-8 10 -8 M per metallic site), [START_REF] Choudhury | Examination of the nickel site structure and reaction mechanism in Streptomyces seoulensis superoxide dismutase[END_REF] and the reaction is slower (kcat = 1.8 10 5 M -1 s -1 , pH 7.75) than that between O2 • -and NiSOD (kcat ∼ 1 10 9 M -1 s -1 , pH 6.0-8.0) [START_REF] Choudhury | Examination of the nickel site structure and reaction mechanism in Streptomyces seoulensis superoxide dismutase[END_REF] or peptide-based models (in the range 6 10 6 -6 10 8 M -1 s -1 , pH 8.0). However, the activity of the present Ni II SOD catalyst is expected to be enhanced at physiological pH, since the measured SOD activity at pH 7.75 contains a significant contribution of the inactive NiL 3S (OH) complex. Unfortunately, since O2 • -dismutation was revealed to be too fast at pH 7.4 to generate reproducible data, the activity at physiological pH, where NiL 3S (OH2) is exclusively present, cannot be measured.

The spectroscopic properties of both complexes highlight that the lability of the aquo and hydroxo ligands are notably different. In NiL 3S (OH2), the water molecule is labile as demonstrating by the broadening of the 1 H NMR resonances, reflecting the dynamics of the complex, while in NiL 3S (OH), the structure is frozen, as attested by the observation of sharp 1 H NMR peaks and of the hydroxo proton, consistent with a non-labile hydroxo ligand. Interestingly, this difference of lability between the aquo and hydroxo ligands is correlated with the SOD activity of the complexes, with NiL 3S (OH2) being the much more active species. Because the redox potentials of the Ni II /Ni III couple in both species are compatible with SOD activity, this difference in reactivity provides insight into the mechanism. It suggests that a labile ligand (water molecule in this case) is required to carry out efficient SOD activity. Consequently, this supports the fact that O2 • -should react with the Ni complex through its direct coordination, resulting in an inner sphere mechanism at least for one of the two reactions. Even though the Ni II /Ni III redox system is irreversible, SOD activity is observed. This suggests that the Ni III species is unstable and quickly reacts with O2 • -, in favor of an outer sphere mechanism for the oxidation of O2 • -into O2. Consequently, we can propose that the reduction of O2 • -occurs via an inner sphere mechanism. This result also shows that the reversibility of the Ni II /Ni III redox system, i.e.

the generation of a stable Ni III complex, is not a mandatory criterion for SOD activity under catalytic conditions.

Conclusion.

Through an original approach based on the use of pseudo-peptide ligands, we described here the first bio-inspired, low-molecular weight, synthetic Ni II complex that displays catalytic SOD activity. Despite the fact that the coordination sphere of NiL 3S (OH2) strongly differs from that of the NiSOD (S3O vs N2S2), NiL 3S (OH2) is active in water at physiological pH. This is rationalized by the fact that the redox potential of the Ni II /Ni III couple is appropriate to perform such O2 • - disproportionation. Another key structural feature is the presence of a labile ligand in the coordination sphere of the Ni II ion that is essential for the activity, thus implying an inner sphere mechanism, at least for the first part of the catalytic SOD cycle generating H2O2.

Experimental section

The synthesis of L 3S was performed as previously published. [START_REF] Pujol | A Series of Tripodal Cysteine Derivatives as Water-Soluble Chelators that are Highly Selective for Copper(I)[END_REF] Solutions preparation: For the preparation of all the aqueous solutions, ultrapure laboratory grade water that has been filtered and purified by reverse osmosis using Millipore MilliQ reverse-osmosis cartridge system (resistivity 18MΩ cm) (Millipore) was used.

In order to prevent the oxidation of the cysteine residues, all the solutions were prepared under an argon atmosphere in a glovebox. Solutions of ligands or complexes were freshly prepared before each experiment in the appropriate deoxygenated buffer.

Ni II solutions were prepared from the sulfate corresponding salt dissolved in water.

The ligand concentration for the different solutions was determined by the Ellman's procedure. [START_REF] Riddles | 8] Reassessment of Ellman's reagent[END_REF] 5,5-dithiobis(2-nitrobenzoic acid) (DTNB) is used as an indicator. Each free thiol group present in the ligand yields 1 equiv. of TNB 2-[λ = 412 nm, ε(TNB 2-) = 14150 M -1 cm -1 ].

For the complex solutions, 0.9 equiv. of Ni II were added to the ligand in the proper buffer so that only the mononuclear complex is formed.

UV and CD spectroscopy:

The UV spectra were recorded with a Varian Cary50 spectrophotometer equipped with optical fibers connected to an external cell holder in a glovebox. The circular dichroism spectra were acquired with an Applied Photophysics Chirascan spectrometer. Spectra were recorded in the 230-630 nm wavelength range with 1 nm bandwidth and 1 second dwell time per point. For each sample, 2 parallel spectra were recorded and the average of these spectra was smoothed by the Savitzky-Golay method with a ''window size'' 7. CD spectra are reported in molar ellipticity [Θ] defined as [Θ] = θobs/(10lc) where θobs is the ellipticity in millidegrees, l the optical path length of the cell in centimeters and c the species concentration in moles per litre. Quartz cells with 1 cm pathlength were used.

For the ligand titration with Ni II , 2.5 mL of a ligand solution (50-75 µM) in Hepes buffer (20 mM, For the pH studies, 2.5 mL of a complex solution (50-75 µM) in water were titrated with aliquots of a 0.01 M KOH solution. The pH was measured using a Metrohm 702 SM Titrino equipped with a Mettler Toledo InLabs Micro-electrode. The UV-Vis and CD spectra were recorded after 10 min stabilization. These data were fitted with the SPECFIT program with fixed values for the pKa of L 3S (pKa1 = 10.2, pKa2 = 9.2, pKa3 = 8.5). [START_REF] Pujol | A Series of Tripodal Cysteine Derivatives as Water-Soluble Chelators that are Highly Selective for Copper(I)[END_REF] The best fit was obtained considering the two global constants β110 and β11-1 defined as: The data analyses were performed using the Demeter package, including ATHENA for the data extraction and ARTEMIS for the shell fitting. [START_REF] Ravel | HEPHAESTUS: data analysis for X-ray absorption spectroscopy using IFEFFIT[END_REF] The k 3 -weighted EXAFS spectra were Fouriertransformed over the k range 2-13 Å -1 using a Hanning window. The fits were performed on the Fourier-transformed spectra over the R range 1-2.4 Å. Ni(H2O)6, Ni(cyclam)(CH3CN)2, 78

Ni II + L 3S D NiL 3S (β110) Ni II + L 3S D NiL 3S H-1 + H + (β11-1) NiL 3S D NiL 3S H-1 + H + Ka (NiL 3S /NiL 3S H-1) = β11-
Ni(Acac)2 and NiS2N2 [START_REF] Gennari | Reversible Apical Coordination of Imidazole between the Ni(III) and Ni(II) Oxidation States of a Dithiolate Complex: A Process Related to the Ni Superoxide Dismutase[END_REF] were used as reference complexes to determine the amplitude reduction factor S0² which was averaged and set to 0.76. The aquo complex was prepared at 1 mM in water from NiSO4, the other ones were analyzed as powder in BN pellets.

Xanthine/Xanthine Oxidase assay: The superoxide was generated with the Xanthine/Xanthine

Oxidase system developed by Fridovich and Beauchamp, [START_REF] Beauchamp | Superoxide dismutase: Improved assays and an assay applicable to acrylamide gels[END_REF] and adapted by Tabbi et al. [START_REF] Tabbi | High Superoxide Dismutase Activity of a Novel, Intramolecularly Imidazolato-Bridged Asymmetric Dicopper(II) Species. Design, Synthesis, Structure, and Magnetism of Copper(II) Complexes with a Mixed Pyrazoleâˆ'Imidazole Donor Set[END_REF] In this test, the IC50 is defined as the SOD concentration needed to inhibit 50% of the NBT conversion to formazan.

In a typical experiment, xanthine oxidase is added to a solution (final volume of 2 mL) of 50 µM xanthine, 100 µM NBT in Hepes buffer (20 mM, pH 7.4 or 9.4, [NaCl] = 100 mM) in order to have an increase of the absorbance of ΔA560 = 0.024 min -1 before the addition of the complex. The reaction was monitored during 150 seconds or less to ensure a stationary state for the superoxide production. The IC50 is reached when the slope after the complex addition is ΔA560 = 0.012 min -1 .

To be sure that the complexes have no influence on the superoxide production, the formation of urate without NBT was also monitored at 290 nm in their absence and in their presence, no difference in the slope was observed.

KO2 solution in DMSO: Fresh KO2 solutions were prepared before each experiment by stirring vigorously ≈100 mg of solid KO2 in 10 mL of dry DMSO. The solutions were filtered after 30 minutes (0.45 µM, PTFE) to give slightly yellow solutions and the superoxide concentration was determined by UV spectroscopy (0.2 mm length path cell, ε250 = 2686 M -1 cm -1 ) and was typically ≈5 mM.

Stopped-flow:

Stopped-flow experiments were performed at 25.0°C on a Biologic SFM-400 using the first three syringes and a high density mixer to minimize optical perturbations due to the mix of solvents. A J&M TIDAS diode array detector (integration time 0.8 ms) and a

Hamamatsu L10290 light source were used. The first syringe was filled with Hepes buffer (60 mM, pH 7.75, [NaCl] = 100 mM), the second one with the complex in the same buffer, and the third one with KO2 in DMSO. The ratio for the syringes was set to 5:5:2, respectively in order to have reproducible shots and an excess of superoxide (constant ratio of 5:1 buffer/DMSO). The dismutation of superoxide was monitored by measuring the absorbance at 245 nm during 2.2 s after the injection in the cell. At least 9 shots were averaged for each complex concentration (range 50-150 µM). Shots of the Ni II complex at different concentrations without superoxide evidence that the complexes remain stable in DMSO containing solutions for the duration of the entire experiment. They were averaged and used as baselines. Data were processed using the Biokine software. No catalytic activity was observed in the control experiment with NiSO4 (500 µM).

Computational details: Density Functional calculations in the Kohn-Sham approach have been carried out with Orca 3.0.3. [START_REF] Neese | The ORCA program system[END_REF] Geometry optimizations have been performed with the hybrid functional B3LYP to which the Grimme dispersion correction with Becke-Johnson damping (D3BJ) [START_REF] Grimme | A consistent and accurate ab initio parametrization of density functional dispersion correction (DFT-D) for the 94 elements H-Pu[END_REF][START_REF] Grimme | Effect of the damping function in dispersion corrected density functional theory[END_REF] has been added, and using the Alhrich def2-tzvp basis set [START_REF] Schäfer | Fully optimized contracted Gaussian basis sets for atoms Li to Kr[END_REF][START_REF] Weigend | Balanced basis sets of split valence, triple zeta valence and quadruple zeta valence quality for H to Rn: Design and assessment of accuracy[END_REF] for all atoms. The RIJCOSX approximation [START_REF] Neese | An improvement of the resolution of the identity approximation for the formation of the Coulomb matrix[END_REF][START_REF] Neese | Efficient, approximate and parallel Hartree-Fock and hybrid DFT calculations. A 'chain-of-spheres' algorithm for the Hartree-Fock exchange[END_REF] has been used for all calculations. Harmonic frequencies have been calculated at the same level to check the nature of the stationary points. Electronic transitions have been calculated through the TD-DFT module on 20 roots using the range-separated CAM-B3LYP. [START_REF] Yanai | A new hybrid exchange-correlation functional using the Coulomb-attenuating method (CAM-B3LYP)[END_REF] The latter functional was shown to be the most adapted thanks to a benchmark on the UV spectrum of NiL 3S (OH2) (see SI for details) including normal hybrids and range-separated ones. TightSCF criteria have been used in all calculations. Geometry optimizations, frequencies and TDDFT spectra, were performed with a solvent continuum (COSMO) [START_REF] Sinnecker | Calculation of Solvent Shifts on Electronic g-Tensors with the Conductor-Like Screening Model (COSMO) and Its Self-Consistent Generalization to Real Solvents (Direct COSMO-RS)[END_REF] modeling the water solvent.

Supporting Information

ESI-MS spectra of the complexes, supplementary figures for CD, 1 H NMR, EXAFS, DFT, electrochemistry and xanthine oxidase assay. Comparison between TD DFT and experimental UV data. xyz coordinates in the optimized structures of the two complexes.

Corresponding Author

*email for C. D.: carole.duboc@univ-grenoble-alpes.fr , P. D.: pascale.delangle@cea.fr

Table of contents

The present work reports on the synthesis and detailed characterization of bio-inspired mononuclear Ni(II) complexes based on a sulfur-rich pseudo-peptide ligand, including the first low-weight synthetic Ni(II) complex that displays catalytic SOD activity, in water, at physiological pH. The overall set of data evidences that the presence of a labile ligand (water molecule) in the coordination sphere of the Ni(II) ion is required for optimal activity, in agreement with an inner sphere mechanism.

Figure 1 .

 1 Figure 1. UV titration of L 3S (57 µM) with Ni II at pH 7.4 (20 mM Hepes buffer, 100 mM NaCl).Spectra in black correspond to samples between 0 and 1 equiv. of Ni II per L 3S , spectra in blue correspond to samples between 1 and 2 equiv. of Ni II . Inset: evolution of the absorbance at 289 nm and 345 nm.

Figure 2 .

 2 Figure 2. CD titration of L 3S (76 µM) with Ni II at pH 7.4 (20 mM Hepes buffer, 100 mM NaCl).Spectra in black correspond to samples between 0 and 1 equiv. of Ni II per L 3S , spectra in blue correspond to samples between 1 and 2 equiv. of Ni II . Inset: evolution of the absorbance at 300 nm, 350 nm and 440 nm.

[

  NiL 3S ] -(m/z = 552.0), with small signals due to the free ligand [L 3S +2H] -(m/z = 496.0) and [L 3S +3H+Cl] -(m/z = 532.1). The Ni2L 3S complex is detected only in excess of Ni II with the anion [Ni2L 3S -2H] -(m/z = 607.9) (Figure S2).

Figure 3 .

 3 Figure 3. UV spectra of L 3S (72 µM) and 0.9 equiv. of Ni II in water at different pH. Spectra recorded between pH 4 and 7.5 are shown in black, spectra recorded between pH 8 and 11 are shown in red. Inset: experimental (dots) and simulated (line) evolution of the absorbance at 270 nm with Specfit software, with logβ110 = 14.6 and logβ11-1 = 6.0.

Solution 1 H

 1 NMR investigation. The structures of both complexes have been investigated by 1 H NMR spectroscopy (Figures 4 and 5). Spectral characteristics of fully dissymmetric structures are expected because of the three cysteine units that are present in different environments due to the chirality of the ligand and the square-planar geometry of the complexes. Both spectra are characteristic of diamagnetic species (0-12 ppm), in agreement with a square planar geometry around a low spin Ni II ion. Interestingly, the 1 H NMR spectra of the two complexes are drastically different: that of NiL 3S (OH) displays well-resolved features, while that of NiL 3S (OH2) shows very broad peaks. This discrepancy suggests drastically different intra-molecular dynamics in the two complexes' coordination spheres.

Figure 4 .

 4 Figure 4. 500 MHz 1 H NMR of NiL 3S (OH2) 1.04 mM in H2O/D2O (90:10) at pH 7.2, 298 K, (*) 10% excess ligand. The complex was prepared in situ from NiSO4 (1.04 mM) and L 3S (1.14 mM, 1.1 equiv.), the pH was increased to 7.2 with a KOH solution.

Figure 5 .

 5 Figure 5. 500 MHz 1 H NMR of NiL 3S (OH) 1.04 mM in H2O/D2O (90:10) at pH 10.1, 278 K. Each symbol corresponds to one of the three different arms of the ligand. (*) 10% excess ligand. A similar spectrum is obtained at 298 K, but one Hα is hidden by the water signal. The complex was prepared in situ from NiSO4 (1.04 mM) and L 3S (1.14 mM, 1.1 equiv.), the pH was increased to 10.1 with a KOH solution.

Figure 6 . 73 Figure 7 .

 6737 Figure 6. XANES spectra of NiL 3S (OH2) (black line, offset of 0.2), NiL 3S (OH) (red line, offset of 0.4) and Ni(N2S2) (dashed line, offset of 0.0)

  Experimental errors on the last character are indicated in parentheses . a Sum of CNs was fixed to 4. b Fixed CN value. c σ 2 values were set to be equal. Res = [Σ(χ exp -χ fit )²/Σ(χ exp )²] x 100. χ² : fitting metric normalized by the degrees of freedom in the fit. Theoretical calculations. To validate the proposed structures of NiL 3S (OH2) and NiL 3S (OH) based on spectroscopic investigation, DFT and TD-DFT calculations have been carried out. Both optimized structures run in singlet state support a square planar geometry around the Ni II ion, which is coordinated to the three thiolates arising from the cysteine arms and one oxygen atom coming from either a water or a hydroxo molecule in NiL 3S (OH2) or NiL 3S (OH), respectively. The Ni-S bond lengths are in the normal range for Ni-S (2.20 to 2.28 Å), and the expected decrease of the Ni-O distance is observed when the hydroxo ligand replaces the water ligand (2.01 and 1.88Å, see Figure S9 and Table

Figure 8 .

 8 Figure 8. Cyclic voltammograms at 100 mV/s of NiL 3S (OH2) (black) and NiL 3S (OH) (red) at 570 µM in Hepes buffer (20 mM, pH 7.4 and 9.5 respectively, [NaCl] = 100 mM), (dotted gray) CV at 100 mV/s of the Ru III (NH3)6Cl3 probe

Figure 9 .

 9 Figure 9. Disproportionation of O2 • -(767 µM), self-disproportionation (orange line), and with 57 µM NiL 3S (black line) in Hepes buffer (60 mM, pH 7.75, [NaCl] = 100 mM) and DMSO (5:1 ratio). Inset. Experimental kobs as a function of the concentration of NiL 3S .

pH 7 . 4 ,

 74 [NaCl] = 100 mM) were titrated with aliquots of the Ni II solution. The UV-Vis and CD spectra were recorded after 10 min stabilization.

1 H

 1 1/β110Mass spectrometry: Mass spectra were acquired on a LXQ-linear ion trap (THERMO Scientific) instrument equipped with an electrospray ion source. Electrospray full scan spectra in the range of m/z = 50-2000 amu were obtained by infusion through a fused silica tubing at a flow rate of 2-10 mL/min. The solutions were analyzed in negative and positive ion modes. The LXQ calibration (m/z = 50-2000) was achieved according to the standard calibration procedure from the manufacturer (mixture of caffeine, MRFA and Ultramark 1621). The temperature of the heated capillary for the LXQ was set in the range of 200-250°C, the ion-spray voltage was in the range of 3-6 kV and the injection time was 5-200 ms. The ligand solution (≈ 150 µM) was prepared in ammonium acetate buffer (20 mM, pH 6.9) and aliquots of Ni 2+ were then added. NMR Spectroscopy: The NMR experiments were recorded on a 500 MHz Bruker Avance spectrometer equipped with a BBI probe with triple axis gradient field. Complex samples at ≈1 mM were prepared in H2O/D2O (v/v=9/1) and the pH was adjusted to 10.1 or 7.2 using a KOH solution. Spectra were acquired on a 15 ppm window and 32k data points in the time domain with a presaturation or a watergate pulse program to suppress the water signal. The temperature coefficients of the amide and the hydroxo protons were measured using watergate water suppression between 278 and 308 K.Electrochemistry: Cyclic voltammograms were recorded with a Metrohm Autolab PGSTAT100 potentiostat at 100 mV/s. A glassy carbon electrode was used as the working electrode, a platinum wire as the auxiliary electrode and SCE as the reference. Solutions of NiL 3S (OH2) and NiL 3S (OH) (570 µM) were prepared in Hepes buffer (20 mM, [NaCl] = 100 mM) at pH 7.4 and 9.5, respectively.X-Ray Absorption Spectroscopy: Ni K-edge XANES (X-ray Absorption Near-Edge Structure)and EXAFS (Extended X-ray Absorption Fine Structure) spectra were recorded at the BM30B (FAME) beamline at the European synchrotron radiation facility (ESRF, Grenoble, France) using a Si(220) double-crystal monochromator.The complexes were prepared at 1.0 mM in water/glycerol(80:20) in order to prevent ice crystallization. The pH was then adjusted with KOH to 7.5 or 9.6 to generate NiL 3S (OH2) and NiL 3S (OH). The complex solutions were placed in a sample holder with Kapton tape windows and flash-frozen in liquid nitrogen, and the frozen glass was mounted in a continuous flow helium-vapor cryostat (8 K ≤ T ≤ 20 K) to minimize sample photo-damage. Spectra were measured in fluorescence-yield detection mode with a 30-element Ge Canberra detector. At least nine scans were averaged for each samples. Data were acquired in 5 eV steps in the preedge region (8100-8295 eV), 0.25 eV steps in the edge region (8295 -8375 eV), 2 eV steps in the post-edge region (8375 -9182 eV). The energy was calibrated with a Ni metallic foil, such that the maximum of the first derivative was set at 8333 eV.

Scheme 2 .

 2 Structure of the ligand L 3S and complexes obtained after addition of Ni II under different pH conditions.

Through a detailed spectroscopic investigation, including

[START_REF] Sheng | Superoxide Dismutases and Superoxide Reductases[END_REF]

H NMR, UV-vis, CD, and XAS, combined with theoretical calculations, L 3S is demonstrated here to form two mononuclear Ni II complexes: [NiL 3S (OH2)] -at physiological pH (pH range 5-8) and [NiL 3S (OH)] 2-in more basic conditions (pH>8) (Scheme 2). For both complexes, a similar S3O coordination sphere with three thiolates originating from the cysteines of the ligand is evidenced, and either a water or a hydroxo molecule, respectively. Despite this sulphur-rich coordination and absence of the mixed amine/amidate environment present in the Ni-SOD, the redox properties of these complexes show that the Ni II /Ni III redox potential is appropriate to disproportionate superoxide.

Table 1 .

 1 data. Experimental data in blue lines and fitted data in red lines (parameters used for the fit are those of Table1with fixed CNs). Structural parameters derived from Ni K-edge EXAFS analysis.

	Ni-S			Ni-O/N		ΔE0	Res
	R (Å)	CN	σ 2 .10 3 (Ų) R (Å) CN	σ 2 .10 3 (Ų)	(eV)	(%)	χ²
	NiL 3S (OH2) 2.22(1) 2.8(8) a 1(1) c	1.99(1) 1.2(8) a 1(1) c	3(3)	1.2	173
	NiL 3S (OH) 2.21(1) 2.7(3) a 3(1)	1.95(2) 1.3(3) a 7(4)	7(2)	0.9	92
	NiL 3S (OH2) 2.22(1) 3 b	1(1) c	1.98(2) 1 b	1(1) c	2.6(7) 1.2	143
	NiL 3S (OH) 2.21(1) 3 b	4(1)	1.94(2) 1 b	7 (4)	5.9(9) 0.8	84
	NiL 3S (OH2) 2.24(1) 2	0.0(4) c	2.01(1) 2	0.0(4) c	7(1)	1.3	163
	NiL 3S (OH) 2.24(1) 2	2.0(9)	1.99(2) 2	4(2)	12(2) 1.8	166

Acknowledgements

. The authors gratefully acknowledge research support of this work by the French National Agency for Research in the framework of the "Investissements d'avenir" program (ANR-15-IDEX-02), the Labex ARCANE (ANR-11-LABX-003) and the CBH-EUR-GS (ANR-17-EURE-0003). Olivier Sénèque and Fabrice Thomas are acknowledged for their help to set-up the stopped-flow experiments. The authors acknowledge the CRG-SOLEIL program committees for provision of synchrotron radiation beamtime (proposal 20170141) and all the FAME beamline staff for his help during the experiment.

Notes

The authors declare no competing financial interest.


Margaux Nattaf
email: margaux.nattaf@grenoble-inp.fr

Arnaud Malapert
email: arnaud.malapert@unice.fr

Filtering rules for flow time minimization in a Parallel Machine Scheduling Problem

Keywords: Parallel Machine Scheduling, Job families, Flow time, Machine Disqualification, Filtering Algorithm, Cost-Based Filtering

This paper studies the scheduling of jobs of different families on parallel machines with qualification constraints. Originating from semi-conductor manufacturing, this constraint imposes a time threshold between the execution of two jobs of the same family. Otherwise, the machine becomes disqualified for this family. The goal is to minimize both the flow time and the number of disqualifications. Recently, an efficient constraint programming model has been proposed. However, when priority is given to the flow time objective, the efficiency of the model can be improved.

This paper uses a polynomial-time algorithm which minimize the flow time for a single machine relaxation where disqualifications are not considered. Using this algorithm one can derived filtering rules on different variables of the model. Experimental results are presented showing the effectiveness of these rules. They improve the competitiveness with the mixed integer linear program of the literature.

Introduction

This paper considers the scheduling of job families on parallel machines with time constraints on machine qualifications. In this problem, each job belongs to a family and a family can only be executed on a subset of qualified machines.

In addition, machines can lose their qualifications during the schedule. Indeed, if no job of a family is scheduled on a machine during a given amount of time, the machine lose its qualification for this family. The goal is to minimize the sum of job completion times, i.e. the flow time, while maximizing the number of qualifications at the end of the schedule.

This problem, called scheduling Problem with Time Constraints (PTC), is introduced in [11]. It comes from the semiconductor industries. Its goal is to introduce constraints coming from Advanced Process Control (APC) into a scheduling problem. APC's systems are used to control processes and equipment to reduce variability and increase equipment efficiency. In PTC, qualification constraints and objective come from APC and more precisely from what is called Run to Run control. More details about the industrial problem can be found in [10].

Several solution methods has been defined for PTC [7,10,11]. In particular, the authors of [7] present two pre-existing models: a Mixed Integer Linear Program (MILP) and a Constraint Programming (CP) model. Furthermore, they define a new CP model taking advantage of advanced CP features to model machine disqualifications. However, the paper shows that when the priority objective is the flow time, the performance of the CP model can be improved.

The objective of this paper is to improve the performances of the CP model for the flow time objective. To do so, a relaxed version of PTC where qualification constraints are removed is considered. For this relaxation, the results of Mason and Anderson [9] are adapted to define an algorithm to optimally sequence jobs on one machine in polynomial time. This algorithm is then used to define several filtering algorithms for PTC.

Although, the main result of this paper concerns the filtering algorithms for PTC, there is also two more general results incident to this work. First, those algorithms can be directly applied to any problem having a flow time objective and which can be relaxed to a parallel machine scheduling problem with sequence-independent family setup times. Secondly, the approach is related to cost-based domain filtering [3], a general approach to define filtering algorithms for optimization problems.

The paper is organized as follows. Section 2 gives a formal description of the problem the CP model for PTC. Section 3 presents the relaxed problem and the optimal machine flow time computation of the relaxed problem. Section 4 shows how this flow time is used to define filtering rules and algorithms for PTC. Finally, Section 5 shows the performance of the filtering algorithms and compares our results to the literature.

Problem description and modeling

In this section, a formal description of PTC is given. Then, a part of the CP model of [7] is presented. The part of the model presented is the part that is useful to present our cost based filtering rules and correspond to the modeling of the relaxation. Indeed, as we are interested in the flow time objective, the machine qualification modeling is not presented in this paper.

PTC description

Formally, the problem takes as input a set of jobs, N = {1, . . . , N }, a set of families F = {1, . . . , F } and a set of machines, M = {1, . . . , M }. Each job j belongs to a family and the family associated with j is denoted by f (j). For each family f , only a subset of the machines M f ⊆ M, is able to process a job of f . A machine m is said to be qualified to process a family f if m ∈ M f . Each family f is associated with the following parameters:

• n f denotes the number of jobs in the family. Note that f ∈F n f = N .

• p f corresponds to the processing time of jobs in f .

• s f is the setup time required to switch the production from a job belonging to a family f ′ = f to the execution of a job of f . Note that this setup time is independent of f ′ , so it is sequence -independent. In addition, no setup time is required neither between the execution of two jobs of the same family nor at the beginning of the schedule, i.e. at time 0.

• γ f is the threshold value for the time interval between the execution of two jobs of f on the same machine. Note that this time interval is computed on a start-to-start basis, i.e. the threshold is counted from the start of a job of family f to the start of the next job of f on machine m. Then, if there is a time interval ]t, t + γ f ] without any job of f on a machine, the machine lose its qualification for f . The objective is to minimize both the sum of job completion times, i.e. the flow time, and the number of qualification looses or disqualifications. An example of PTC together with two feasible solutions is now presented.

Example 1. Consider the instance with N = 10, M = 2 and F = 3 given in Table 1(a). Figure 1 shows two feasible solutions. The first solution, described by Figure 1(b), is optimal in terms of flow time. For this solution, the flow time is equal to 1 + 2 + 9 + 15 + 21 + 1 + 2 + 12 + 21 + 30 = 114 and the number of qualification losses is 3. Indeed, machine 1 (m 1 ) loses its qualification for f 3 at time 22 since there is no job of f 3 starting in interval ]1, 22] which is of size γ 3 = 21. The same goes for m 2 and f 3 at time 22 and for m 2 and f 2 at time 26. The second solution, described by Figure 1(c), is optimal in terms of number of disqualifications. Indeed, in this solution, none of the machines loses their qualifications. However, the flow time is equal to 1 + 2 + 9 + 17 + 19 + 9 + 18 + 20 + 27 + 37 = 159.

CP model

In the following section, the part of the CP model of [7] which is useful for this work is recalled. This part corresponds to a Parallel Machine Scheduling Problem (PMSP) with family setup times. New auxiliary variables used by our cost based filtering rules are also introduced. These variables are written in 1 3 9 1 25 {2} 2 3 6 1 26 {1,2} 3 4 1 1 21 {1,2}

f n f p f s f γ f M f
f 1 f 1 f 1 f 2 f 2 f 2 f 3 f 3 f 3 f 3 (b) An optimal solution for the flow time objective m 1 m 2 2 3
9 11 17 20 27 37

f 1 f 1 f 1 f 2 f 2 f 2 f 3 f 3 f 3 f 3 (c)
An optimal solution for qualification losses bold in the variable description. To model the PMSP with family setup times, (optional) interval variables are used [5,6]. To each interval variable J, a start time st(J), an end time et(J), a duration d(J) and an execution status x(J) is associated. The execution status x(J) is equal to 1 if and only if J is present in the solution and 0 otherwise. The following set of variables is used:

• jobs j , ∀j ∈ N : Interval variable modeling the execution of job j;

• altJ j,m , ∀(j, m) ∈ N × M f (j) : Optional interval variable modeling the assignment of job j to machine m;

• flowtime m and f lowtime: Integer variables modeling respectively the flow time on machine m and the global flow time; • nbJobs f ,m , ∀(f, m) ∈ F × M f : Integer variable modeling the number of jobs of family f scheduled on m;

• nbJobs m , ∀m ∈ M: Integer variable modeling the number of jobs scheduled on m. To model the PMSP with setup time, the following sets of constraints is used:

f lowT ime = j∈N et(jobs j ) (1) alternative jobs j , altJ j,m |m ∈ M f (j) ∀j ∈ N (2) noOverlap altJ j,m |∀j s.t. m ∈ M f (j) , S ∀m ∈ M (3) f lowtime = m∈M f lowtimem (4) f lowtimem = j∈N et(altJ j,m ) ∀m ∈ M (5) nbJobs f,m = j∈N ;f (j)=f x(altJ j,m ) ∀(f, m) ∈ F × M f (6) m∈M nbJobs f,m = n f ∀f ∈ F (7) f ∈F nbJobs f,m = nbJobsm ∀m ∈ M (8) m∈M nbJobsm = N (9)
Constraint ( 1) is used to compute the flow time of the schedule. Constraints ( 2)-( 3) are used to model the PMSP with family setup time. Constraints (2) model the assignment of jobs to machine. Constraints (3) ensure that jobs do not overlap and enforce setup times. Note that S denotes the setup time matrix: (S f,f ′ ) is equal to 0 if f = f ′ and to s f otherwise. A complete description of alternative and noOverlap constraints can be found in [5,6]. In [7], additional constraints are used to make the model stronger, e.g. ordering constraints, cumulative relaxation. They are not presented in this paper. Constraints ( 4)-( 9) are used to link the new variables to the model. Constraints ( 4) and ( 5) ensure machine flow time computation. Constraints ( 6) compute the number of jobs of family f executed on machine m. Constraints (7) make sure the right number of jobs of family f is executed. Constraints ( 8) and ( 9) are equivalent to constraints ( 6) and ( 7) but for the total number of jobs scheduled on machine m. The bi-objective optimization is a lexicographical optimization or its linearization [2].

3 Relaxation description and sequencing

R-PTC description

The relaxation of PTC (R-PTC) is a parallel machine scheduling problem with sequence-independent family setup time without the qualification constraints (parameter γ f ). The objective is then to minimize the flow time. In this section, it is assumed that a total the assignment of jobs to machines is already done and the objective is to sequence jobs so the flow time is minimal. Therefore, since the sequencing of jobs on M machines can be seen as M one machine problems, this section presents how jobs can be sequenced optimally on one machine. In Section 4, the cost-based filtering rules handle partial assignments of jobs to the machines.

Optimal sequencing for R-PTC

The results presented in this section were first described in [8]. They are adapted from Mason and Anderson [9] who considers an initial setup at the beginning of the schedule. The results are just summarized in this paper.

First, a solution can be represented as a sequence S representing an ordered set of n jobs. Considering job families instead of individual jobs, S can be seen as a series of blocks, where a block is a maximal consecutive sub-sequence of jobs in S from the same family (see Figure 2). Let B i be the i-th block of the sequence, S = {B 1 , B 2 , . . . , B r }. Hence, successive blocks contain jobs from different families. Therefore, there will be a setup time before each block (except the first one). The idea of the algorithm is to adapt the Shortest Processing Time (SP T ) rule [12] for blocks instead of individual jobs. To this end, blocks are considered as individual jobs with processing time

f 1 f 1 f 1 f 2 f 3 0 5
P i = s fi + |B i | • p fi and weight W i = |B i |
where f i denotes the family of jobs in B i (which is the same for all jobs in B i ).

The first theorem of this section states that there always exists an optimal solution S containing exactly |F | blocks and that each block B i contains all jobs of the family f i . That is, all jobs of a family are scheduled consecutively.

Theorem 1. Let I be an instance of the problem. There exists an optimal solution S * = {B 1 , . . . , B |F | } such that |B i | = n fi where f i is the family of jobs in B i . Sketch. For a complete proof of the theorem, see [8]. Consider an optimal solution S = {B 1 , . . . , B u , . . . , B v , . . . , B r } with two blocks B u and B v (u < v), containing jobs of the same family f u = f v = f . Then, moving the first job of B v at the end of block B u can only improve the solution.

Indeed, let us define P and W as:

P = v-1 i=u+1 P i +s f and W = v-1 i=u+1 |B i |.
In addition, let S ′ be the sequence formed by moving the first job of B v , say job j v , at the end of block B u . The difference on the flow time between S and S ′ , is as follows:

F T S ′ -F T S = W • p f -P if |B v | = 1 W • p f -P - r i=v+1 |B i | • s f if |B v | > 1
Using Lemma 1 of [8] stating that P/W ≥ p f , then F T S ′ -F T S < 0 and flow time is improved in S ′ . Hence, moving the first job of B v at the end of block B u leads to a solution S ′ at least as good as S.

Therefore, a block B i contains all jobs of family f i . Indeed, if not, applying the previous operation leads to a better solution. Hence, |B i | = n fi and there are exactly F blocks in the optimal solution, i.e. one block per family. 1 2 11 2 12 2 3 12 9 15 (a) Instance with N = 5 and

f n f p f s f M P T f
F = 2.
Family 1 precedes family 2 (SMPT). At this point, the number of block and theirs contents are defined. The next step is to order them. To this end, the concept of weighted processing time is also adapted to blocks as follows.

Definition 1. The Mean Processing Time (MPT) of a block B i is defined as

M P T (B i ) = P i /W i .
One may think that, in an optimal solution, jobs are ordered by SM P T (Shortest Mean Processing Time). However, this is not always true since no setup time is required at time 0. Indeed, the definition of block processing time always considers a setup time before the block. In our case, this is not true for the first block. Example 2 gives a counter-example showing that scheduling all blocks according to the SMPT rule is not optimal.

Example 2 (Counter-example -Figure 3). Consider the instance given by Table 3(a) that also gives the MPT of each family (M P T f = p f + (s f ÷ n f )). Figure 3(b) shows the SMPT rule may lead to sub-optimal solutions when no setup time is required at time 0. Indeed, following the SMPT rule, jobs of family 1 have to be scheduled before jobs of family 2. This leads to a flow time of 198. However, schedule jobs of family 2 before jobs of family 1 leads to a better flow time, i.e. 181.

Actually, the only reason why the SM P T rule does not lead to an optimal solution is that no setup time is required at time 0. Therefore, in an optimal solution, all blocks except the first one are scheduled according to the SM P T rule. That is the statement of Theorem 2 for which a proof is given in [8].

Theorem 2. In an optimal sequence of the problem, the blocks 2 to |F | are ordered by SM P T (Shortest Mean Processing Time). That is, if

1 < i < j then M P T (B i ) ≤ M P T (B j ).
The remaining of this section explains how these results are used to define a polynomial time algorithm for sequencing jobs on a machine so the flow time is minimized. This algorithm is called sequencing in the remaining of the paper.

Theorem 1 states that there exists an optimal solution S containing exactly |F | blocks and that each block B i contains all jobs of family f i . Theorem 2 states that the blocks B 2 to B |F | are ordered by SM P T . Finally, one only needs to determine which family is processed in the very first block.

Algorithm sequencing takes as input the set of jobs and starts by grouping them in blocks and sorting them in SMPT order. The algorithm then computes the flow time of this schedule. Each block is then successively moved to the first position (see Figure 4) and the new flow time is computed. The solution returned by the algorithm is therefore the one achieving the best flow time. The complexity for ordering the families in SM P T order is O(F log F ). The complexity of moving each block to the first position and computing the corresponding flow time is O(F ). Indeed, there is no need to re-compute the entire flow time. The difference of flow time coming from the Move operation can be computed in O(1). Hence, the complexity of sequencing is O(F log F ).

B 1 , . . . , B f -1 s f B f s f +1 B f +1 , . . . , B |F | (a) SMPT Sequence B f s 1 B 1 , . . . , B f -1 s f +1 B f +1 , . . . , B |F | (b) B f is moved in the first position.

Filtering rules and algorithms

This section is dedicated to the cost-based filtering rules and algorithms derived from the results of Section 3. They are separated into three parts, each one corresponding to the filtering of one variable: f lowtime m (Section 4.1); nbJobs f,m (Section 4.2); nbJobs m (Section 4.3). Note that the two last variables constrained by the sum constraint 8.

During the solving of the problem, jobs are divided for each machine m into three categories based on the interval variables altJ j,m : each job either is, or can be, or is not, assigned to the machine. Note that the time windows of the interval variables are not considered in the relaxation. For a machine m, let N A m be the set of jobs for which the assignment to machine m is decided. In the following of this section, an instance I is always considered with the set N A = ∪ m∈M N A m of jobs already assigned to a machine. Thus, an instance is denoted by (I, N A ). Some notations are now introduced. For a variable x, x (resp. x) represents the lower (resp. the upper) bound on the variable x. Furthermore, let F T * (X ) be the flow time of the solution returned by the algorithm sequencing applied on the set of jobs X .

f n f p f s f 1 3 2 5 2 3 3 3 3 4 4 1 (a) Instance data. f 1 f 3 f 2 0 5 10 f 1 f 3 f 2 f 2 0 5 10

Increasing the machine flow time

The first rule updates the lower bound on the f lowtime m variable and follows directly from Section 3. The complexity of this rule is

O(M • F • log F ). Rule 1. ∀m ∈ M, f lowtime m ≥ F T * (N A m )
Proof. It is sufficient to notice that, for a machine m, sequencing gives a lower bound on the flow time. In particular, F T * (N A m ) is a lower bound on the flow time of m for the instance (I, N A ).

Example 3. Consider an instance with 3 families. Their parameters are given by Table 5(a). A specific machine m is considered and set N A

m is composed of one job of each family. This instance and N A m is used in all the example of this section. Suppose f lowtime m ∈ [0, 35]. The output of sequencing is given on the top of Figure 5(b). Thus, the lower bound on the flow time can be updated to 2+7+13 = 22, i.e. f lowtime m ∈ [22,35]. Suppose now that an extra job of family f 2 is added to N A m (on the bottom of Figure 5(b)). Thus, F T * (N A m ) = 2+8+11+16 = 37 and 37 > f lowtime m = 35. Thus, the assignment defined by N A m is infeasible. Another rule can be defined to filter f lowtime m . This rule is stronger than Rule 1 and is based on N A m and nbJobs m . Indeed, nbJobs m denotes the minimum number of jobs that has to be assigned to m. Thus, if one can find the nbJobs m jobs (including the one of N A m ) that leads to the minimum flow time, it will give a lower bound on the flow time of machine m. Actually, it may be difficult to know exactly which jobs will contribute the least to the flow time. However, considering jobs in SP T order and with 0 setup time gives a valid lower bound on f lowtime m . First, an example illustrating the filtering rule is presented and then, the rule is formally given.

Example 4. Consider the instance described in Example 3. Suppose N A

m is composed of one job of each family and f lowtime m ∈ [22,60]. Suppose also nbJobs m = 6. Thus, 3 extra jobs need to be assigned to m. Families in SP T order are {f 1 , f 2 , f 3 } and the remaining number of jobs in each family is 2, 2, 3. Hence, the 3 extra jobs are: 2 jobs of f 1 and 1 job of f 2 .

To make sure the lower bound on the flow time is valid, those jobs are sequenced on m with no setup time. In Figure 6, f j denotes "classical" jobs of family f j while f ′ j denotes jobs of family f j with no setup time. Figure 6 shows the results of sequencing on the set of jobs composed of N A m plus the 3 extra jobs, i.e. nbJobs m = 6. Here, F T * = 2+4+6+9+14+20 = 55. Thus, the lower bound on f lowtime m can be updated and f lowtime m ∈ [55,60]. Note that, because Rule 1 does not take nbJobs m into account, it gives a lower bound of 22 in this case.

f 1 f ′ 1 f ′ 1 f ′ 2 f 3 f 2 0 5 10 15 20
Let N O m denotes the set composed of the first nbJobs m -|N A m | remaining jobs in SP T order with setup time equal to 0.

Rule 2. ∀m ∈ M, f lowtime m ≥ F T * (N A m ∪ N O m ) Proof. First note that if N O m = ∅, Rule 1 gives the result. Thus, suppose that |N O m | ≥ 1. By contradiction, suppose ∃m ∈ M such that f lowtime m < F T * (N A m ∪ N O m
). Thus, there exists another set of jobs N O m with:

F T * (N A m ∪ N O m ) < F T * (N A m ∪ N O m ) (10)
First, note that w.l.o.g.

|N O m | = |N O m |. Indeed, if |N O m | > |N O m |,
in ∈ N O m \ N O m . Thus, since p f j i > p fj k , sequence S ′ = {j 1 , • • • , j i-1 , j k , j i+1 , • • • j nbJobsm } has a smaller flow time than S.
Repeated applications of this operation yield to a contradiction with equation (10).

The complexity of Rule

2 is O(M • F • log F ). Indeed, sorting families in SP T order can be done in O(F • logF ). Creating the set N O m is done in O(F ) and sequencing is applied in O(F • logF ) which gives a total complexity of O(F • logF + M • (F + F • log F )).

Reducing the maximum number of jobs of a family

The idea of the filtering rule presented in this section is as follows. For a family f , nbJobs f,m define the maximum number of jobs of family f that can be scheduled on m. Thus, if adding those nbJobs f,m to N A m leads to an infeasibility, nbJobs f,m can be decreased by at least 1. Let denote by N f m the set composed of nbJobs f,m jobs of family f minus those already present in N A m .

Rule 3.

If ∃(f, m) ∈ F × M such that F T * (N A m ∪ N f m ) > f lowtime m , then nbJobs f,m ≤ nbJobs f,m -1
Proof. Suppose that for a family f and a machine m, we have a valid assignment such that F T * (N A m ∪ N f m ) > f lowtime m and nbJobs f,m = nbJobs f,m . By Rule 1, the assignment is infeasible which is a contradiction.

Example 5. Let us consider the instance defined by example 3. In the first part of this example, N A m is composed of one job of each family and f lowtime m ∈ [22,35]. Suppose that nbJobs f2,m = 2. Thus, N A m ∪ N f m contains one job of family f 1 and f 3 and two jobs of family f 2 . The bottom part of figure 5

(b) shows that F T * (N A m ∪ N f m ) = 37 > f lowtime m = 35. Thus, nbJobs f2,m < 2. The complexity of Rule 3 is O(M • F • log F + M • F 2 • log |D MAX nbJobs f,m |) with |D MAX nbJobs f,m
| the maximum size of the domain of variables nbJobs f,m . Indeed, the first part corresponds to the complexity for applying the sequencing algorithm on all machine. This algorithm only need to be applied once since each time we remove jobs from N f m , F T * can be updated in O(F ). Indeed, only the position of the family in the sequence has to be updated. Thus, the second part corresponds to the updating of F T * for each family and each machine. By proceeding by dichotomy, this update has to be done at most log |D MAX nbJobs f,m | times. Thus, the complexity of Rule 3 is

O(M • F • (log F + F • log |D MAX nbJobs f,m |)).

Reducing the maximum number of jobs on a machine

The idea behind Rule 2 can be used to reduce the maximum number of jobs on machine m. Indeed, for a machine m, nbJobs m is the maximum number of jobs that can be scheduled to m. Thus, if it is not possible to schedule nbJobs m on m without exceeding the flow time, then nbJobs m can be decreased. The extra jobs that will be assigned on m must be decided. Note that those jobs must give a lower bound on the flow time for nbJobs m jobs with the preassignment defined by N A m . Thus, jobs can be considered in SP T order with no setup time. Before giving the exact filtering rule, an example is described. [22,60]. Suppose nbJobs m = 7. Thus, the 4 extra jobs assigned to m are: 2 jobs of f 1 and 2 jobs of f 2 . Figure 7 shows the results of sequencing on the set of jobs composed of N A m plus the 4 extra jobs. Here, F T * = 2+4+6+11+14+17+23 = 77 which is greater than f lowtime m = 60. Thus, nbJobs m cannot be equal to 7 and can be filtered.

f 1 f ′ 1 f ′ 1 f ′ 2 f ′ 2 f 3 f 2 0 5 10 15 20
(M • F • log F + M • F 2 • |D MAX nbJobsm |) with |D MAX
nbJobsm | the maximum size of the domain of variables nbJobs m . Indeed, as for Rule 3, the algorithm sequencing only needs to be applied once and then can be updated in O(F ). For each machine and each family, this update has to be done at most |D MAX nbJobsm | times. Indeed, proceeding by dichotomy here implies that F T * cannot be updated but has to be re-computed each time. Thus, the complexity of Rule 4 is O

(M • F • (log F + F • |D MAX nbJobsm |)).

Experimental Results

This section starts with the presentation of the general framework of the experiments in 5.1. Following the framework, the filtering rules are evaluated in Section 5.2. Then, the model is compared to those of the literature in Section 5.3. Last, a brief sensitivity analysis is given in Section 5.4.

Framework

The experiment framework is defined so the following questions are addressed. Q1. Which filtering rule is efficient? Are filtering rules complementary? Q2. Which model of the literature is the most efficient? Q3. What is the impact of the heuristics? Of the bi-objective aggregation? To address these questions, the following metrics are analyzed: number of feasible solutions, number of proven optimums, upper bound quality; solving times; number of fails (for CP only).

The benchmark instances used to perform our experiments are extracted from [10]. In this paper, 19 instance sets are generated with different number of jobs (N ), machines (M ), family (F ) and qualification schemes. Each of the instance sets is a group of 30 instances. There is a total of 570 feasible instances with N = 20 (180), N = 30 (180), N = 40 (30), N = 50 (30), N = 60 (60), N = 70 (90).

The naming scheme for the different solving algorithms is described in Table 1 Table 1: Algorithms Encoding.

All the experiments were led on a Dell computer with 256 GB of RAM and 4 Intel E7-4870 2.40 GHz processors running CentOS Linux release 7 (each processor has 10 cores). The time limit for each run is 300 seconds.

Evaluation of the filtering rules

In this section, the efficiency and complementary nature of the proposed filtering rules are investigated. In other words, the algorithms N *LF are studied. To this end, the heuristics are not used to initialize the solvers. The lexicographic optimization is used since it has been shown more efficient in preliminary experiments.

First, all algorithms find feasible solutions for more than 99% of the instances. Then, for each algorithm, the number of instances solved optimally is drawn as a function of the time in Figure 8(a). The leftmost curve is the fastest whereas the topmost curve proves the more optima. Clearly, compared to N LF, the filtering rules accelerates the proof and allow the optimal solving of around eighty more instances. One can notice that the advanced filtering rules (N FLF, N MLF, N ALF), also slightly improves the proof compared to the simple

Figure 1 :

 1 Figure 1: Two solution examples for PTC.

Figure 2 :

 2 Figure 2: Block representation of a solution.

F

  Scheduling jobs of a family before those of the other one. Numbers are completion times of the jobs.

Figure 3 :

 3 Figure3: Scheduling all blocks according to the SMPT rule is not optimal.

Figure 4 :

 4 Figure 4: SMPT Sequence and Move Operation.

  15(b) Illustration of Rule 1 and Rule 3.

Figure 5 :

 5 Figure 5: Illustration of f lowtime m filtering (Rule 1).

Figure 6 :

 6 Figure 6: Illustration of f lowtime m filtering (Rule 2).

  we can remove jobs from |N O m | without increasing the flow time. Furthermore, w.l.o.g. we can consider that ∀j ∈ N O m , s fj = 0. Indeed, since setup times can only increase the flow time, thus inequality (10) is still verified. Let S = {j 1 , • • • , j nbJobsm } be the sequence returned by the sequencing algorithm on N A m ∪ N O m . Let also j i be the job in N O m \ N O m with the SP T . Finally, let j k be the job with the SP T

Example 6 .

 6 Consider the instance described in Example 3. In the first part of this example, N Am is composed of one job of each family and f lowtime m ∈

Figure 7 :

 7 Figure 7: Illustration of Rule 4.

  . The first letter represents the model where ILP model, CP O model and CP N model denotes respectively the ILP model and CP model of [7], and the CP model detailed in Section 2.2. The models are implemented using IBM ILOG CPLEX Optimization Studio 12.10 [4]. That is CPLEX for the ILP model and CP Optimizer for CP models. The second letter indicates whether two heuristics are executed to find solutions which are used as a basis for the models. These heuristics are called Scheduling Centric Heuristic and Qualification Centric Heuristic [10]. The goal of the first heuristic is to minimize the flow time while the second one tries to minimize the number of disqualifications. The third letter indicates the filtering rules that are activated for the CP N model. Rule 2 is used for the letter L because it has been shown more efficient than Rule 1 in preliminary experiments. The fourth letter indicates the bi-objective aggregation method: lexicographic optimization; linearization of lexicographic optimization. The last letter indicates the objective priority. Here, the priority is given to the flow time in all experiments because the cost-based filtering rules concern the flow time objective. Weighted sum F Flow time O CP O model H All F Rule 3 A All L Lexicographic Q Disqualifications N CP N model M Rule 4