MSc Johanna Strandell
email: johanna.strandell@who-umc.org

MSc Stina Wahlin

Pharmacodynamic and pharmacokinetic drug interactions reported to VigiBase, the WHO Global Individual Case Safety Report Database

Keywords: Pharmacovigilance, VigiBase, enzyme inhibition, additive effects

Objective: Drug interactions resulting in adverse drug reactions (ADRs) represent a major health problem both for individuals and the community. Despite this, there is limited information in the literature regarding drug interaction categories responsible for causing ADRs.

In this study we investigated the drug combinations most frequently co-reported as interacting in the WHO Global Individual Case Report (ICSR) Database, VigiBase, and categorised them in respect to the drug interaction mechanism. Methods: Reports with drug combinations coreported as interacting on at least 20 reports in VigiBase during the past 20 years were included in the study. Each drug combination was reviewed in the literature to identify the mechanism of interaction and classified as pharmacodynamic and/or pharmacokinetic. Report characteristics were also analysed. Results: In total 3766 case reports of drug interactions from 47 countries were identified. Of 123 different drug combinations 113 were described in the literature to interact. The mechanism were categorised as: pharmacodynamic in 46(41%), pharmacokinetic in 28(25%), a combination of both types in 18(16%), and unidentified in 21(19%) drug interactions. Pharmacodynamic drug interactions primarily concerned pharmacological additive effects whereas enzyme inhibition was the most frequent pharmacokinetic interaction. The reviewed combinations primarily implicated drugs such as warfarin, heparin, carbamazepine and digoxin. Conclusions: Drug interactions reported on globally collected ADR reports covers both pharmacodynamic, specifically additive pharmacological effects, and pharmacokinetic mechanisms primarily accredited inhibition of hepatic CYP enzymes. These ADR reports often concerns serious threats to patients' safety, particularly related to usage of high risk drugs such as warfarin and heparin.

Introduction

Polypharmacy increases the complexity of therapeutic management and thereby the risk of clinically important drug interactions, which may result in adverse drug reactions (ADRs) or reduced therapeutic effect in individuals (1). However, the magnitude of ADRs related to drug interactions in the existing literature is inconsistent, probably reflecting the variety of settings and populations studied. A recently published study based on individual case safety reports (ICSRs) found that 22% of patients exposed to a potential drug interaction experienced an associated ADR [START_REF] Leone | Identifying adverse drug reactions associated with drug-drug interactions: data mining of a spontaneous reporting database in Italy[END_REF], while in specific hospital settings drug interactions have been reported to cause up to 59% of all ADRs [START_REF] Pirmohamed | Adverse drug reactions as cause of admission to hospital: prospective analysis of 18 820 patients[END_REF][START_REF] Davies | Adverse drug reactions in hospital in-patients: a prospective analysis of 3695 patient-episodes[END_REF].

A large proportion of potentially clinically significant drug interactions are reported to occur by alterations in the hepatic drug metabolism mostly in the activity of cytochrome P450 (CYP) enzymes such as CYP3A4, CYP2C9, CYP2C19, CYP1A2 and CYP2D6, glucuronidation and drug transporters such as P-glycoprotein. Hence pharmacokinetic properties and related drug interactions are often well supported in clinical studies referred to in SPC (Summary of the Product Characteristics) texts and specific drug interaction references. While pharmacodynamic interactions, which are apparent from the main pharmacological action of the drugs are often expected to be understood by prescribing physicians [START_REF] Griffin | A manual of adverse drug Interactions[END_REF], are often undersupplied in drug reference texts unless the drug combination may result in serious toxicity such as prolonged QT interval.

Adverse effects due to drug interactions are a common and to a large extent a preventable health care issue. As ICSRs are reflections of drug related problems within health care, these reports can give insight into which drug interactions that are of particular concern and the characteristics of these. However, few studies have actually examined drug interaction categories responsible for causing ADRs. Subsequently, this study was conducted to explore the ICSRs with drug combinations most frequently co-reported as interacting in the WHO Global ICSR Database, VigiBase, and to categorise them with respect to the drug interaction mechanisms.

Methods and data

To study mechanisms of suspected drug interactions reported globally, drug combinations coreported as interacting on at least 20 reports in VigiBase during the past 20 years were included in the study. Each drug combination was reviewed in the literature for the mechanism of interaction and classified according to pre-defined categories. To further characterise these suspected drug interactions reported to VigiBase, information on date of report, gender, reporter and country of origin were studied.

Data source

The WHO Programme for International Drug Monitoring was initiated in 1968 to detect previously unknown drug safety problems and still remains as one of the central elements for global safety surveillance [START_REF] Edwards | The WHO International Drug Monitoring Programme[END_REF]. To maintain the programme's operation ICSRs (also referred to as spontaneous reports of suspected ADRs and synonymously referred to as reports in this paper) are collected in the WHO Global ICSR Database, VigiBase [START_REF] Lindquist | the WHO Global ICSR Database System: Basic facts[END_REF]. The reports are collected on national basis by the individual member countries (n=104) of the WHO Programme for International Drug Monitoring, and then forwarded to, processed and stored in VigiBase.

Each report contains at least a drug, an ADR, the country submitting the report and an identification number. Drugs listed on the reports are assigned as 1) 'suspected' (drugs suspected for the reaction, but not explicitly as due to a drug interaction), 2) 'interacting' (if an adverse drug reaction is suspected of being related to a drug interaction between two or more drugs), or 'concomitant' (drugs used concurrently but not suspected by the reporter to have caused the adverse event). Information on the reports are provided by a primary reporter or through a second evaluation performed by the National Centre. The individuals providing information listed on the reports are referred to as reporter. The reports also contain other information such as age, gender, type of report (spontaneous, study report) etc.

Classification

Drug interaction mechanisms were categorised into two main groups, pharmacokinetic and pharmacodynamic [START_REF] Baxter | Stockley's Drug Interactions[END_REF][START_REF] Pirmohamed | Drug Interactions of Clinical Importance[END_REF]. Pharmacokinetic interactions were further divided into mechanistic subgroups with additional sub-classifications given in brackets: absorption (changes in gastrointestinal pH, changes in gastrointestinal motility, chelation and adsorption, damage to gastrointestinal tract, induction or inhibition of drug transport proteins, reduction of gut flora); distribution (protein-binding 'displacement', induction or inhibition of drug transport proteins); metabolism (hepatic uptake -induction or inhibition of drug transport proteins, enzyme induction, enzyme inhibition); and excretion (hepatic secretion into the bile -induction or inhibition of drug transport proteins, changes in urinary pH, active tubular secretion -induction or inhibition of drug transport proteins). Pharmacodynamic interactions were initially divided into two categories: 'direct effect at receptor function', 'interference with a biological or physiological process. In a pilot phase we discovered that many of the pharmacodynamic drug combinations concerned additive pharmacological effects rather than synergistic effects.

Additive pharmacological effects were therefore included as a subgroup of pharmacodynamic mechanisms, even though these are not covered by the general definition of a drug interaction ("pharmacological or clinical response of one drug is changed in the presence of another drug" (8)) as it's effects are not changed. Pharmacodynamic interactions were divided into the following subgroups: 'direct effect at receptor function', 'interference with a biological or physiological control processes' and 'additive/opposed pharmacological effect'.

Those drug combinations established to interact but with an unidentified mechanism were listed as 'unidentified mechanism'. Drug combinations concluded with negative results for a potential drug interaction were noted as 'no interaction'. Drug combinations without published information of a possible interaction were classified as 'unknown in the literature'.

Analyses

Reports with drug combinations co-reported as interacting on at least 20 reports in VigiBase during the past 20 years were scrutinized. To characterise this subset of suspected drug interactions, information on date of report, gender, reporter and country of origin were retrieved and analysed. Selected drug combinations were reviewed in the literature for the mechanism of interaction and classified according to the pre-defined categories. The following literature sources were reviewed for interaction mechanism in given order: 1) Stockley's Drug Interaction [START_REF]Stockley's Drug Interaction[END_REF], 2) FASS (Swedish Drug Compendium) [START_REF]FASS for health care professionals[END_REF], 3) DrugDex (12) and 4) PubMed (13). When the information in Stockley's Drug Interaction, FASS for health care professionals and DrugDex was consistent no further literature search in PubMed was made. For combinations where more than one mechanism was suggested for the interaction all mechanisms of interaction were listed. To clarify the involvement in each mechanism drugs were classified as object (the affected drug) and precipitant (induced the interaction) [START_REF] Horn | Proposal for a new tool to evaluate drug interaction cases[END_REF]. Both drugs were noted as object in cases where the interaction was documented to result in an additive or synergistic effect. From the literature further information for each mechanism were extracted: expected outcome specified as toxic effect or reduced efficacy and type of pharmacological effect noted as additive, synergistic or antagonistic for pharmacodynamic interactions.

Supplementary analyses

As a drug may be involved in several clinically important mechanisms, all mechanisms found for the drug in the literature review were summarised. To investigate if reported response (based on reports in VigiBase) corresponded to the expected outcome of verified drug interactions, top reported ADR terms [START_REF]MedDRA Term Selection points to consider[END_REF] for a drug combination were reviewed.

Results

From January 1990 to February 2010, 4149345 reports were entered in VigiBase, of these included 18409 reports two drugs as interacting. During the study period 123 drug combinations were co-reported as interacting on at least 20 reports (in total 3766 reports) and thus included in the analysis. The analysis included reports from 47 countries with the majority (67%) from Europe; this contrasts general distribution of reports in VigiBase whereof USA represents 50%. When excluding reports lacking gender specification, females (52%) were slightly more common than males (48%) which also disparities from the general distribution where 60% of VigiBase reports concerns females. In total 83% of the reports were submitted from health care professionals (physicians (78%), pharmacists (4%), nurses and dentists (1%)).

This also contrasts to VigiBase in general, where 63% are received from health care professionals.

Mechanisms

Of the 123 reviewed drug combinations, 113 were verified in the literature to interact. In total were 65 pharmacodynamic and 68 pharmacokinetic mechanisms acknowledged in the literature (table I). Interactions via additive pharmacological effects and inhibition of metabolic pathway were most common among the studied drug combinations. Of the interactions acknowledged to a specific enzyme, CYP3A4 and CYP2C9 were particularly frequent, these accounted for 42% and 24%, respectively. Other enzymes involved were CYP1A2, CYP2B6, CYP2C19, CYP2C8 and epoxide hydrolase. For 40 drug combinations more than one mechanism was accredited for the interaction. Whereas some were purely pharmacokinetic as for digoxin and clarithromycin involving drug distribution (induction or inhibition of drug transport proteins [START_REF]Stockley's Drug Interaction[END_REF][START_REF] Drugdex | [END_REF] and reduction of gut flora (10-12)), and excretion (changes in renal blood flow [START_REF]Stockley's Drug Interaction[END_REF][START_REF]FASS for health care professionals[END_REF][START_REF] Drugdex | [END_REF]); or as a mix of pharmacodynamic and pharmacokinetic mechanisms as for warfarin and celecoxib that functions via additive pharmacological effect [START_REF]Stockley's Drug Interaction[END_REF][START_REF]FASS for health care professionals[END_REF] and enzyme inhibition (10, 12)(table II). For the reviewed drug combinations, protein-binding displacement, inhibition of drug transport proteins and inhibition of the gut flora were often described as minor mechanisms and rarely reported as exclusively responsible for the drug interaction.

When reviewing the unique nature of the 113 verified interactions, 46 (41%) were identified as purely pharmacodynamic; 28 (25%) as pharmacokinetic; and 18 (16 %) were a mix of both types. For 11 otherwise purely pharmacodynamic and pharmacokinetic interactions additional mechanisms, yet unidentified, were proposed, as the main mechanism of action was assumed to not explain the interaction's total effect. In addition, 21 (19%) drug combinations (e.g. selective serotonin re-uptake inhibitors (SSRIs) with lithium, or warfarin with tramadol or warfarin with norfloxacin) were reported to interact though without detailed description of a mechanism in the literature, though the interactions had been acknowledged on case reports or case series.

Reported characteristics

The reviewed combinations primarily concerned well established drugs, i.e. drugs that have been marketed for more than 10 years. Among pharmacodynamic interactions antithrombotic agents were most frequent (table III), while pharmacokinetic interactions involved a range of drugs that inhibit or compete for hepatic CYP enzymes. The substantial influence of antithrombotic agents amongst frequently reported pharmacodynamic interactions were reflected by the overall ADR pattern reported for pharmacodynamic interactions in VigiBase (ordered by total number of reports): gastrointestinal haemorrhage, haematoma, melaena and prothrombin level decreased. While for pharmacokinetic interactions the variety of drugs involved reflected the range of ADRs reported but also alterations in therapeutic effect (ordered by total number of reports): drug level increased, prothrombin level decreased, rhabdomyolysis and therapeutic response increased. ADRs reported for verified interactions were well associated with the expected effect of the object drug (table II). This is shown with the increased frequency of reports for warfarin related effects (increased international normalised ratio (INR) and or decreased prothrombin level) during concurrent use of roxithromycin and miconazole, or risk of statin induced rhabdomyolysis during concurrent use of gemfibrozil.

None interacting drug combinations

For ten drug combinations, the literature did not include information of a possible interaction. Among these none interacting drug combinations were warfarin and digoxin; three drug combinations involving drugs used in standard tuberculosis regime (ethambutol with pyrazinamide, ethambutol with rifampicin, and isoniazid with pyrazinamide); a vitamin K antagonist, fluindione, with various agents (amiodarone, ceftriaxone, ciprofloxacin, fluconazole and ofloxacin) with all reports submitted from France; and acetylsalicylic acid (ASA) with abciximab, whereas the drugs' antithrombotic effects are used in combination for patients undergoing percutaneous coronary intervention [START_REF]FASS for health care professionals[END_REF].

Discussion

This study demonstrated that the scope of drug interactions reported on globally collected ADR reports is broad and concerns interactions with both pharmacokinetic, foremost inhibition for hepatic CYP enzymes, and pharmacodynamic mechanisms primarily as additive pharmacological effects. This is particularly noteworthy since pharmacodynamic interactions have been reported to have less clinical impact than pharmacokinetic interactions [START_REF] Griffin | A manual of adverse drug Interactions[END_REF].

Moreover, ICSRs of suspected drug interactions often concerns serious threats to patients' safety, particularly related to usage of high risk drugs such as warfarin and heparin [START_REF] Bates | Incidence of adverse drug events and potential adverse drug events. Implications for prevention. ADE Prevention Study Group[END_REF][START_REF] Cullen | Preventable adverse drug events in hospitalized patients: a comparative study of intensive care and general care units[END_REF].

Even though the spontaneous reporting system is a cornerstone of the early detection of previously unknown single drug-single ADR combinations [START_REF] Wiholm | In Spontaneous reporting systems outside the US[END_REF], there is a clear overrepresentation of established associations. We deliberately used this phenomenon when selecting drug combinations (inclusion criteria ≥20 reports) to identify drug interaction categories reported on ICSRs. There were a range of mechanisms reported, and the scrutinised combinations were often the expression of more than one mechanism. CYP3A4 was the most common metabolic pathway in this subset, and this is expected from its general involvement in drug metabolism. Even if the proportion of CYP2C9 (24%) interactions was higher than expected these were explained by the numerous adverse drug interactions involving warfarin. Furthermore, were enzyme inhibition more common than enzyme induction in this subset, which may be because of various reasons: its general occurrence; or that induction more rarely leads to an effect that has clinical impact; or that enzyme inhibition is more easily associated to drug use as its ADR response occurs more rapidly [START_REF] Baxter | Stockley's Drug Interactions[END_REF][START_REF] Pirmohamed | Drug Interactions of Clinical Importance[END_REF]. Drug combinations not reported in the literature which in general are interesting in from signalling value [START_REF] Edwards | Harmonisation in pharmacovigilance[END_REF], were explain by common drug therapies whereas the individual drugs for the combination were likely to interact with a range of other drugs (e.g. digoxin -warfarin, ASA -abciximab and drug combinations involving drugs used in standard tuberculosis regime driven by the fact that rifampicin induces the metabolism of isoniazid); or a reflection of lack of information in the international literature as for the vitamin K antagonist, fluindione, for which several of the suspected interacting agents are established to interact with the more widely used vitamin K antagonist, warfarin [START_REF] Drugdex | [END_REF]. This subset primarily concerned well established drugs which are expected since information for well established drugs increases over time. Even though we focused on well known drug interactions in this analysis, previous reports have shown that there is a continuous need for monitoring of well established drugs as new problems, such as drug interactions related to the concurrent use of new drugs, are still being discovered [START_REF] Yue | Concomitant Use of Glucosamine Potentiates the Effect of Warfarin[END_REF][START_REF] Knudsen | Potential glucosamine-warfarin interaction resulting in increased international normalized ratio: case report and review of the literature and MedWatch database[END_REF][START_REF] Henderson | St John's wort (Hypericum perforatum): drug interactions and clinical outcomes[END_REF]. This is also emphasised from other reviews of drug safety issues which to a large extent concerns drugs well known to interact [START_REF] Johansson | An analysis of Vigimed, a global e-mail system for the exchange of pharmacovigilance information[END_REF][START_REF] Meyboom | Detecting Adverse Drug Reactions[END_REF].

The reporting patterns for this subset of reports contrast the general reporting in VigiBase in two perspectives: drug interactions are to a greater extent reported by health care professionals; and reports for females were less frequent in this subset [START_REF] Fridén | Gender Differences in International Adverse Drug Reaction Surveillance[END_REF]. A higher rate of reports from health care professionals are expected as greater pharmacological knowledge is required to understand the more complex character having more than one drug associated to the adverse outcome. For gender distribution Leone et al. found a similar result, where the proportions of potential interactions were greater for females, though men were more likely to experience an ADR related to a drug interaction (2). However, considering the nature of data and the small set of drug interactions used in this analysis, disparities for gender in terms of experiencing drug interactions needs to be further investigated. This descriptive analysis did not intend to present the frequency of mechanisms for drug interactions outside this subset, or the frequency of these drug combinations in VigiBase related to their background reporting or outside the database. Though, it is possible that certain mechanisms are more frequently acknowledged and therefore are drug combinations more frequently reported, or reversely, the literature is more limited for some mechanisms such as transport proteins and therefore are these less well represented in the subset. Furthermore, VigiBase is heterogeneous with respect to origin of data and level of suspicion such as assignment of drugs related to ADRs varies between member countries. For example drugs involved in a drug interaction may be assigned as interacting or as suspected, for the latter the suspected drug interaction may then be noted in the case narratives or as an ADR term. However these notations lack of assignment to the specific drugs involved in the interaction as many more drugs may be listed as suspected on the individual case report. Subsequently, there is a clear under-reporting of drug interactions listed in the drug assignment in VigiBase, which results in a selection bias of drug combinations undertaken for this review. However, this is not necessarily a problem as the reports in this analysis were received from a variety of countries.

Increased reporting related to increased publicity is one of the general limitations of the ADR surveillance system, that may have amplified further differences in drug assignment as interacting on the individual case report [START_REF] Strandell | Drug-drug interactions -a preventable patient safety issue?[END_REF], or could have lead to increased reporting and hence inclusion in this review.

Despite that adverse effects due to drug interactions are common, ICSRs have previously been limitedly used in the early discovery of drug interactions signals. This analysis has contributed to identify which drug interactions that are of particular concern and the mechanistic scope of these. Overall are much more efforts are needed to appropriately manage and acknowledge the risk of potential drug interactions to prevent these in the early stage of prescribing or monitor them thoroughly.

Conclusion

Drug interactions reported on globally collected ADR reports covers both pharmacodynamic, specifically additive pharmacological effects, and pharmacokinetic mechanisms primarily via CYP inhibition in the liver. These ADR reports often concerns serious threats to patients' safety, and particularly related to usage of high risk drugs such as warfarin and heparin, and other well established agents. Finally, post-marketed reported drug interactions do not only concern problems related to the drugs' pharmacological action but also to how the drugs are used.

Acknowledgements

The authors are indebted to the National Centres that contribute data. The opinions and conclusions in this study are not necessarily those of the various centres, nor of the World Health Organisation (WHO).

Table I. Overview of mechanisms acknowledged in the literature for drug combinations coreported as interacting on at least 20 reports in Vigibase between January 1990 and February 2010. In total were 123 drug combinations reported in the subset whereof 113 were verified to interact. Several mechanisms may be relevant for the same drug interaction. Protein-binding 'displacement' [START_REF]Stockley's Drug Interaction[END_REF] Drug excretion [START_REF]Stockley's Drug Interaction[END_REF][START_REF]FASS for health care professionals[END_REF][START_REF] Drugdex | [END_REF][START_REF] Strandell | Drug-drug interactions -a preventable patient safety issue?[END_REF] Changes in renal blood flow [START_REF]Stockley's Drug Interaction[END_REF][START_REF]FASS for health care professionals[END_REF][START_REF] Drugdex | [END_REF][START_REF] Strandell | Drug-drug interactions -a preventable patient safety issue?[END_REF] Interference with a biological or physiological control process Reduction of gut flora [START_REF]Stockley's Drug Interaction[END_REF][START_REF]FASS for health care professionals[END_REF][START_REF] Drugdex | [END_REF] Changes in renal blood flow [START_REF]Stockley's Drug Interaction[END_REF][START_REF]FASS for health care professionals[END_REF][START_REF] Drugdex | [END_REF] Drug level in Therapeutic Nausea, Bra Gemfibrozil Cerivastatin 113 Hepatic uptake -induction or inhibition of drug transport proteins [START_REF] Yamreudeewong | Potentially Significant Drug Interactions of Class III Antiarrhythmic Drugs[END_REF][START_REF] Backman | Gemfibrozil Greatly Increases Plasma Concentrations of Cerivastatin[END_REF][START_REF] Neuvonen | Drug Interactions with Lipid-Lowering Drugs: Mechanisms and Clinical Relevance[END_REF] Enzyme inhibition [START_REF] Yamreudeewong | Potentially Significant Drug Interactions of Class III Antiarrhythmic Drugs[END_REF][START_REF] Backman | Gemfibrozil Greatly Increases Plasma Concentrations of Cerivastatin[END_REF][START_REF] Neuvonen | Drug Interactions with Lipid-Lowering Drugs: Mechanisms and Clinical Relevance[END_REF][START_REF] Shitara | Pharmacokinetic and Pharmacodynamic Alterations of 3-Hydroxy-3-Methylglutaryl Coenzyme A (HMG-CoA) Reductase Inhibitors: Drug-Drug Interactions and Interindividual Differences in Transporter and Metabolic Enzyme functions[END_REF] Additive/opposed pharmacological effect


Benjamin Lefaudeux
email: benjamin.lefaudeux@inria.fr

Gwennael Gate
email: gwennael.gate@m4x.org

Fawzi Nashashibi
email: fawzi.nashashibi@inria.fr

Extended occupation grids for non-rigid moving objects tracking

We present an evolution of traditional occupancy grid algorithm, based on an extensive probabilistic calculus of the evolution of several variables on a cell neighbourhood. Occupancy, speed and classification are taken into account, the aim being to improve overall perception of an highly changing unstructured environment. Contrary to classical SLAM algorithms, no requisite is made on the amount of rigidity of the scene, and tracking do not rely on geometrical characteristics. We believe that this could have important applications in the automotive field, both from autonomous vehicle and driver assistance, in some areas difficult to address with current algorithms. This article begins with a general presentation of what we aim to do, along with considerations over traditional occupancy grids limits and their reasons. We will then present our proposition, and detail some of its key aspects, namely update rules and performance consequences. A second part will be more practical, and will begin with a brief presentation of the GPU implementation of the algorithm, before turning to sensor models and some results.

I. OCCUPANCY GRIDS -EXTENDED

To begin with, we present in this part our motivations for this work, and some limits of current algorithms for the specific task which we aim to deal with. A comeback to the occupancy grid paradigm is our next point, before some thoughts about what could be an optimal occupancy grid update rule, and why its practical use is limited. A second part is devoted to our proposition, trying to tackle some of the observations previously made while dealing with some approximations and limits inherent to practical realisation. A last small part presents some performance considerations, which are important for scalability issues in case of collaborative work, and expected evolution with new computing hardware.

A. General considerations 1) Perception of non-structured moving objects: Amid a vast set of localisation and perception algorithms currently developed, among which various SLAM have taken the greater share for the last years, some challenges are still untackled in the perception field. Detection and tracking of moving objects, without pre-requisites on rigidity, structured environment or immobility remains a tough question, and is not yet addressed by many approaches. Different SLAMbased approaches have been used for the last years, some of them being very successful in building a map of the environment from a non-associative sensor while dealing with the identification of some moving objects amid the map.

FastSLAM, using particle filtering and initially presented by Thrun et. al ( [START_REF] Thrun | Fastslam: An efficient solution to the simultaneous localization and mapping problem with unknown data association[END_REF]) or other iterative optimisation techniques (ICP, [START_REF] Wang | A Hierarchical Object Based Representation for Simultaneous Localization and Mapping A Hierarchical Object Based Representation for Simultaneous Localization and Mapping[END_REF] [START_REF] Steux | CoreSLAM: a SLAM Algorithm in less than 200 lines of C code[END_REF]) are very powerful algorithms which can deal with some level of movement amid tracked points, as long as fixed points of the map are enough to estimate robot pose and environment mapping, and to isolate non conforming elements. This proved effective, for example by Wang et. al ( [START_REF] Wang | Simultaneous Localization, Mapping and Moving Object Tracking[END_REF]), in constrained cases where the number of moving parts remains low. Overall scene requisites are indeed strong using these techniques, and would probably not be enough for reliable moving object perception and tracking in a highly unstructured environment. Contrary to SLAM, our aim is thus not primarily to localise oneself in the environment along with building a map of its static features, but instead to be able to reliably detect and monitor position and dynamics of surrounding moving objects, possibly outdoor and without much visible solid infrastructure.

2) Interests and limits of the simple grid-based approach:

Occupancy grids are very common in robotics, since their first introduction by Moravec and Elfes ( [START_REF] Moravec | High resolution maps from wide angle sonar[END_REF]), initially related to sonar based mapping. Principles are simple and effective, relying on the information storage and information source spatial localisation similarities, thus allowing to keep any spatial relations between cells at a minimal cost. Occupancy grids were thus at the heart of most of the latests SLAM propositions (based on filtering or optimisation), and in many of broadly speaking perception systems (Badino et al [START_REF] Badino | Free space computation using stochastic occupancy grids and dynamic programming[END_REF] showed for example a promising free-space perception system based on vision and occupancy grids in 2007). Additional processing of information is present in those examples, due to the very limited nature of conventional grids data integration, usually relying on large number law for any kind of temporal filtering. This is one of the major approximations chosen in most occupancy grids to limit computational complexity, at the expense of information loss. Another major approximation historically in the heart of occupancy grids is the cell independence pre-requisite, which greatly simplifies eventual probabilities calculus. Obviously a big step from accurate world description, this is basically of little consequences in case the aim is, as it was in the original Moravec article [START_REF] Moravec | High resolution maps from wide angle sonar[END_REF], the cartography of still environment. In case we chose the occupancy grid formalism to track moving objects, this is however a major limitation, as one could expect the displacement of physically related points to be correlated. Those limitations are intricate, and could be seen as two limits stemming from the same cell independence (in time and space) from one iteration to another, on conventional grid-based processing and information storage.

3) Optimal occupancy grids: Considering a hypothetical occupancy grid propagation, one could wonder why an optimal Bayesian propagation would not be possible. The probability of any combined cell displacement could be weighted, thus computing the most-probable map prediction from a given set of measurement, allowing a temporal and spatial filtering, and a link between new measurements and known information. Trouble is, computing the formal probability is extremely demanding, if one is to consider every possible move. A complete probability calculus, considering a set of S possible state in any cell of a N * M grid, would imply the consideration of each and every possible map, which is S N * M . Taking the smallest possible state sampling (2 states), and a ridiculously small map of 10*10 cells, and the amount of maps to compute to get to the full solution is already beyond any reasonable range (2 100 ). The key to this complexity surely in a lot of useless probabilities being taken into account, even possibly beyond the causality principle. Anything at a given place have little to no chance of influencing the very next future of a very remote location, and this is the idea behind dealing with neighbourhood-restricted probabilities.

B. Tackling inter-dependence within computing boundaries

We propose the use of extended occupancy grids, able to deal with part of the interactions between cells, in a common prediction/measurement Bayesian cycle. Our algorithm aims at taking into account both temporal and spatial relations between measurements, while keeping computing costs low enough to conceive a real-time use and concurrent use of other more specialised algorithms. Firstly, we introduce the probability for every cell to move to its neighbourhood, given previous knowledge of the scene (occupation, speed, classification) and specific heuristics (separate cells cannot converge, nor can cells from the same object diverge). Secondly, we compare this prediction to a new measurement, and compute the most probable estimate given prediction and latest measurement. Thirdly, we update associated knowledge used in the prediction step, namely occupancy of every cell of the grid, speed, relation between cells (in a neighbourhood) or object classification used for different sensor models. Those principles were presented by Gate in [START_REF] Gate | Fast Pedestrian Detection in Dense Environment with a Laser Scanner and a Camera[END_REF], initially on a standard CPU implementation, and showed very promising results despite a high computing cost making it prohibitive for any real-time application.

1) Bayesian filtering:

Bayesian filtering is at the heart of numerous recent publications, a lot of them being aimed at moving object perception and uncertainty handling. One of the reference article in this domain would be from Coue et. al ( [START_REF] Coue | Bayesian Occupancy Filtering for Multitarget Tracking: An Automotive Application[END_REF]), in which a Bayesian Occupancy Filter is first presented. In this paper, every cell of the occupancy grid is part of a Bayesian network, whose transition probabilities will be estimated by the filter. The end result is an estimation of occupancy and velocity of every cell of the network, given past measures. This article has been followed by [START_REF] Chen | Dynamic Environment Modeling with Gridmap: A Multiple-Object Tracking Application[END_REF], which refines some of the concepts, but keeps most of the initial BOF computations. One difference with the algorithm we propose may be that we iteratively try to estimate the most probable association, or that we explicitly consider relations between close cells through rigidity and non-penetration constraints, thus giving a higher priority on spatial filtering. Another possibility to remove impossible moves from the filter estimation was proposed by Gindele in [START_REF] Gindele | Bayesian Occupancy grid Filter for dynamic environments using prior map knowledge[END_REF], using prior knowledge of the environment to exclude specific moves which could trick a Bayesian occupancy filter. Another very interesting work closely related to our proposition would be the algorithm demonstrated by Danescu et. al in two recent papers ( [START_REF] Danescu | Particle grid tracking system for stereovision based environment perception[END_REF], [START_REF] Danescu | Modeling and Tracking the Driving Environment with a Particle Based Occupancy Grid[END_REF]), in which cell speed is iteratively estimated by a particle filter. Similarly to BOF, this proposition is not based on the simple motion models and combination rules which we rely on, which could make some difference in dense scenes with occultation.

2) Initial definitions: Initial definitions of the used probability mass functions (pmf ) are as follows : -Mapping (occupancy) probability M k (x i ) ∈ [0, 1] of the cell x i in the spatial environment E at the time k, provided the measurements Z 0:k = {z 0 , ..z k } :

P (M k (x i ) = 1|Z 0:k ) ∀x i ∈ E (1)
-Vehicle localisation (including position and speed in E ×V ), at the iteration k. This is not yet addressed by the algorithm, and external sensors (odometers, wheel angle sensor) are used.

P (L k = l j |Z 0:k ) ∀l j ∈ (E × V ) (2)
-Association, ie the probability for a given cell from the iteration k-1 to be associated with another given cell at the iteration k. In our case, only associations coming from a restricted neighbourhood are taken into account, which cuts the number evaluated map candidates from an exponential dependence on the number of cells to a more reasonable dependence on neighbourhood scale.

P (X next k-1 (x i ) = x j |M k-1 (x i ) = 1, Z 0:k ) ∀(x i , x j ) ∈ E 2 (3)
-Velocity probability of a cell, given its occupancy and previous measurements :

P (V k (x i ) = v|M k (x i ) = 1, Z 0:k ) ∀(x i , v) ∈ E × V (4)
-Detection probability, to handle the probability that two given cells x i and x j are part of the same object. The neighbourhood constraint limiting interactions to a finite part of the map is used once more, to limit the intricateness and heavy computing cost. Affiliation to a given object can however be "propagated" further than one cell's neighbourhood, although our span is limited and this could prove to be a problem. Detection probability, D k (x i , x j ) ∈ [0, 1] is 1 if x i x j are from the same object.

P (D k (x i , x j ) = 1|M k (x i ) = 1, M k (x j ) = 1, Z 0:k ) ∀(x i , x j ) ∈ E 2 (5)
-Classification designs the probability of this set of cells to be part of a given class of objects (car, pedestrian, still object,..).

We attempt to model this by matching extended characteristics of a set of cells (beyond geometrical characteristics for example) to a model. This conditions the update rule of association calculus, envisaged future positions of a cell being for example adapted from its class motion model. Classification probability are simultaneously kept from a different set of classes, a cell being capable of a partial fit with different classes. This ensures a more robust classification, initially prone to errors.

P (C k (x i ) = c j |M k (x i ) = 1, Z 0:k ) ∀(C × E) (6)
3) Update rules: Having set these definitions, the proposed update rules make a number of approximations, in order to shorten computing time and adapt to existing sensors information : -Associations are updated in a two-pass mechanism, making an extra initial assumption of independence between cells behaviour, which we attempt to correct in a second part. This behaviour was already present in the [START_REF] Gate | Fast Pedestrian Detection in Dense Environment with a Laser Scanner and a Camera[END_REF] proposition, and is a key to the possible use of massively parallel computing. Approximations are obviously primordial in our attempt to make the calculus feasible in real-time, but we believe most of the interactions between cells are mostly taken into account with this proposition. First we then compute the local associations prediction, which is to say that macroscopic interactions are not yet taken into account :

P local (X next k-1 (x j )|M k-1 (x j ) = 1, Z 0:k ) = η • P local (z k |X next k-1 (x j ), M k-1 (x j ) = 1, Z 0:k-1 ) Correction • P local (X next k-1 (x j )|M k-1 (x j ) = 1, Z 0:k-1 ) P rediction (7)
η is here a normalisation constraint, to ensure that possible moves sum up to one for any given cell. Object previous speed and class are used to predict the asserted new positions. This could be seen, similarly to SLAM particle filters ( [START_REF] Thrun | Fastslam: An efficient solution to the simultaneous localization and mapping problem with unknown data association[END_REF]), as a new set of particles generated for every cell of the grid iteratively, representing this cell's occupancy possible next moves, depending on previous knowledge and motion model.

P local (X next k-1 (x i ) = x j |M k-1 (x j ) = 1, Z 0:k-1 ) = Ψ(x j , x i , V k-1 (x j ), C k-1 (x j )) (8)
The last measurement is then taken into account to produce an estimated local association, still without macroscopic constraints. Predictions are weighted according to the sensor model occupancy output, simply emphasising association estimation matching the measurement on a linear basis. Simple rule from conditional probability is thus applied, making the supposition that the result from our prediction process best represents the knowledge from the past. Initial association estimation is then altered according to additional constraints : unlikely moves are penalised according to different heuristics (different cells cannot converge to the same place, cells from the same rigid object cannot diverge).

Rigidity and non inter-penetration constraints are modelled by the potential function Φ association , which is currently based on two Gaussian weight function whose optimal width is still under investigation on real data.

P (X next k-1 (x j ) = x|M k-1 (x j ) = 1, Z 0:k-1 ) ≃ a k ∈A    1≤j≤N P local (X n k-1 ext(x j )|M k-1 (x i ) = 0, Z 0:k )    • Φ association (a k , E, Z 0:k ) ( 9
)
where A is the set of all possible associations. The process here described can be differently factorised, but was split into several summations in an attempt to increase its readability.

-Mapping is computed taking into account the two cases : in the cell is a newly observed presence, or the displacement (possibly null) of a previously seen cell. In the first case, the sensor model is the only input taken into account, in the second case contributions from all the possible associations are summed up to compute the predicted occupancy. Cell interactions have in this case already been taken into account in the association computation. The two cases are dissociated by a random variable S k , which can take two values : 0 if the cell has never been seen, 1 if the cell has already been seen. Its probability is computed with association computation results : to sum up, if the considered cell corresponds to a local association maximum, P (S k (x i ) = 1|Z 0:k ) takes the value γ ∈ [0, 1], else it takes the value 1γ. The value of γ is chosen depending on the "renewal" rate of the map, that is to say "how often do we think a new object can appear from nowhere" ? A value around 0.5 has proven to work well in practice.

P (M k (x i )|Z 0:k ) = P seen (M k (x i )|S k x i = 1, Z 0:k ) • P (S k (x i ) = 1|Z 0:k ) + P unseen (M k (x i )|S k x i = 0, Z 0:k ) • P (S k (x i ) = 0|Z 0:k ) (10)
with the corresponding calculus (A being the cell neighbourhood) :

P seen (M k (x i )|Z 0:k ) = j∈A {P (X next k-1 (x j ) = x i |M k-1 (x j ) = 1, Z 0:k-1 ) • P (M k-1 (x j ) = 1|Z 0:k-1 )} (11)
P unseen is in this case typically related to the sensor occupancy model.

-Velocities are computed taking into account the same two possibilities, depending if the observed cell is considered a new one, or the association of an already-observed cell to a new position : -considering the velocity of already-observed cells, velocity is simply computed from the associations, summing up speed values steming from all the possible contributors.

-considering appearing cells, the probability distribution of velocities had been proposed by Gate in [START_REF] Gate | Fast Pedestrian Detection in Dense Environment with a Laser Scanner and a Camera[END_REF] as follows, and kept in this proposition :

P (V k (x i )|S k (x i ) = 0, Z 0:k ) = 1 card(V ) (12)
Merging of the two possibilities is done similarly to eq. 10.

-Detection update on the GPU-based algorithm is not yet on par with the initial proposition of G. Gate ([7]), which rightfully took into account updated velocity, mapping and associations estimates, as well as previous detection and classification values. For the sake of simplicity in this initial implementation, detection map update concerning already seen observations is currently done via cross-correlation of updated local associations pmf, thus focusing on rigidity links. This calculus, although a partial exploitation of available information, is very fast (a matter of milliseconds for a map of thousands of cells), albeit not precise enough to handle structured objects behaviour, and is to be refined in a future work.

-Classification updates can similarly be done using every gathered information (mapping, velocity, rigidity links,..) correspondence to a given sensor model, which would on the other hand improve prediction steps of the algorithm. This is not yet present in the GPU-based algorithm, and presented results can thus be seen as perfectible. There is however no theoretical constraints on this calculus, which should be in place in our implementation algorithm in a short time for several classes (pedestrian, cars,..)

4) Performance considerations:

As stated in eq. I-A3, complexity constraints on calculus are not to be neglected in occupancy grid update rules, many thinkable algorithms being simply not realistic. The complexity of the mechanism we propose can be computed as follows :

-for the sake of simplicity, we state a N * N grid, every cell being able to move in a M * M neighbourhood.

-considering the propagation of one cell, every possible move of every of its neighbours (O(M 4 )) are to be investigated for each individual envisaged propagation (O(M 2 )), which translates in O(M 6 ) complexity.

-cells updates being independent except for conformation rules already taken into account in the previous step, overall cell considerations is finally of O(N 2 • M 6 ) complexity for the full update step.

It is here important to state that heavy approximations are still present when compared to an optimal calculus, namely that each and every cell moves are initially computed individually, although being later filtered to take some interactions into account. Computation is thus still not intricate, which keeps the complexity "low", although O(N 2 • M 6 ) remains a heavy burden for any realistic dimensions. Several points can be emphasised from this simple complexity calculus : -although the computation remains heavy by all means, key approximations (namely cell propagation initial independence) have cut computing needs, and are moreover a key aspect for practical implementation. As such, the algorithm can easily be thought for massively parallel computing, every probability summation related to cell propagation being doable in a parallel and synchronised way. Our early tests using CUDA prove that real-time computing is possible on current hardware within reasonable grid dimensions. Faster implementation on FPGA should be possible on the same basis, the algorithm having proved to sustain heavy multi-threading -digging into specific complexity aspects, our algorithm is also linear in complexity as regards the number of cells for a given neighbourhood, the size of which being responsible for most of the computational burden. This relative lightness in the grid size complexity is a key benefit for sharing applications : extending the size of the grid is not necessarily a problem as regards computational requirements, especially taking the massively parallel implementation which we chose (several GPU could be used to extend possible grid propagation). Extending the domain of tracked speed is however more complicated : tracked speed depends on the width of the move taken into account at every iteration, literally V max = M/2 * ∆ τiteration with ∆ the spatial extension relative to one grid cell. Considering a given iteration maximum computing time (limited for example by the Lidar frequency for real-time operations), the maximum tracked speed is rapidly capped by the computing power at disposal relatively to the maximum computing time. We'll see with our preliminary results that this translates to very acceptable maximum speeds for our initial implementation on current hardware.

II. PRACTICAL IMPLEMENTATION AND RESULTS

We present in this part some elements of the implementation we are currently testing and developing, which notably differs from the initial Gate publication ( [START_REF] Gate | Fast Pedestrian Detection in Dense Environment with a Laser Scanner and a Camera[END_REF]) by its implementation, taking advantage of the CUDA API from nVidia Corp. A few remarks are initially made on this evolution, after which we explain the sensor model used to feed the algorithm, and expected sensor models to develop. We finally present some results obtained on actual data.

A. GPU-based algorithm

The initial proposition by Gate and Nashashibi ( [START_REF] Gate | Fast Pedestrian Detection in Dense Environment with a Laser Scanner and a Camera[END_REF]) being too much of a burden for current CPU processing despite its performances in tracking moving objects, we investigated different possibilities to make this algorithm a plausible realtime candidate. Due to the very parallel nature of its different information representations, a GPU-based implementation was started, using the nVidia API Cuda. The algorithm presented in this paper is thus partly different from the 2009 work, due to the fundamental differences between Cpu and Gpu processing abilities. Massively-parallel processing indeed comes with intrinsic limitations, being notably negatively affected by branching and conditional calculus. The main differences could be summarised as follows : -cells differentiation into "key-cells" representing objects geometrical key points and standard cell (whose propagation is not investigated) could not be used within this non-branching restrictions, and the algorithm is now possibly more generic, considering displacements and constraints for each and every cell of the grid. -cells neighbourhood, previously considered on-the-fly depending on their dynamic characteristics is now fixed, each and every cell keeping a given influence area on which interactions are considered. At stake is the capability of computing map updates in real-time with a neighbourhood far enough so that appropriate speeds are tracked. This reliability limit can easily be computed given the map pitch, sensor frequency, time between updates and corresponding neighbourhood.

B. Some results

As usual when dealing with grid-based algorithms, sensor occupancy models are a key factor in our proposition. A standard simple Lidar occupancy model is used in our initial implementation, computed on GPU. Occupancy of areas in the shadow of Lidar impacts are chosen to 0.5 out of 1, neutral in our occupancy ratio. Although not entirely implemented yet, this algorithm is currently tested on real data involving Lidar measurements in an urban environment. Logging and replay framework is RTMaps software from Intempora, for every considered data. It is important to remember the exhaustiveness and generic nature of the algorithm : every mapped cell of the environment is considered equal, and no a priori is ever made on geometrical bounding, preferred positions, structures, stationary or moving parts. Although still quite demanding on computing resources, the algorithm works in near real-time on current state-of-the-art hardware. The first scene computed below need 120ms to compute on a early 2010 GF100 GPU from nVidia (counting 448 CUDA cores), which should translate to well below 100 ms on current higher-end offerings. As regards performance, this algorithm is also an initial port, and could certainly be greatly improved. The second scene computed below used a larger neighbourhood, which drives to 1s calculus on the same hardware, but is not compulsory for this task. This can be seen as "best case" reasonably feasible if the algorithm was ported onto a dedicated FPGA for example.

1) Algorithm memory:

In this example, we emphasise a temporary occlusion situation, where a pedestrian shadow hides another previously seen pedestrian (figures 1). Only the Lidar sensor is used in this case, camera captures being presented for illustrative purpose, along with bounding boxes. Lidar shadow occupancy is set to 0.3. On the pmf representations (figures 2 and 3), the point of view is from above, in a common "bird-view" perspective. All the boxes are drawn for illustrative purpose, we don't present here the output of a detection algorithm. The resolution of grid mapping is 15cm, speeds up to 4.5m/s being theoretically tracked. This last value can be improved without any computing cost by simultaneously degrading the spatial resolution and increasing the range of the measurements, which could be a dynamic trade-off depending on the vehicle speed. The shadowed pedestrian is still clearly visible on the occupancy map, although the Lidar cannot get through the first occluding person. Its position spread over time, which shows that our knowledge decreases with the age of the data. We thus stress the importance of sensor filtering, taking into account possible spatial and temporal correlation. In this case, consequences of the pedestrian not being visible without filtering has no practical consequences, but this is not always the case and we believe that such filtering would be compulsory for autonomous vehicle navigation in an urban area.

2) Dynamics estimation: This example plans to emphasise dynamics estimation capabilities of the algorithm, along with segmentation of the scene. Although this is already possible via bounding boxes in the case of clearly separated persons, those matchings often miss when persons are too close to Fig. 2. Lidar output when occluded Fig. 3. Occupancy evaluation from our algorithm each other, or when groups change in size due to some people joining and leaving. The exhaustive approach that we carry on a per-cell basis insures a reliable estimation of the probable speeds. All boxes presented on figures 4 5 6 are here on illustrative purpose, and do not come from a detection algorithm. In green are the crossing pedestrians, which may have been difficult to track on sensor data alone (cf figure 5), due to the pushchair and their proximity. In blue is the road sign, which is obviously standing still, but which shows the residual speed of the vehicle (end of the braking sequence) and noise on Lidar data. It is barely visible on the speed map, due to the very low residual speed of the car. Segmentation of the scene after the algorithm process between moving and still parts proves effective. In red is the car coming on the other way, which is also going slow due to the crossing pedestrians, and have very few Lidar impacts (laser beam was oriented upwards, maybe too much). Tracking on geometrical grounds on Lidar data alone may have been difficult in this case.

C. Future works

Alternative source of occupancy, velocity or classification are planned, mainly based on vision processing. Stereo-vision is for example a proven source of free-space measurement, as proven by Moravec once again in [START_REF] Moravec | Robot Spatial Perceptionby Stereoscopic Vision and 3D Evidence Grids[END_REF], or more recently Badino et al. using dense disparity calculus and occupancy grids ( [START_REF] Badino | Free space computation using stochastic occupancy grids and dynamic programming[END_REF] and articles following). Motion detection and evaluation have also be proven to be a valuable output from stereovision capture, Argrawal et al. proving in [START_REF] Agrawal | Real-time detection of independent motion using stereo[END_REF] that platform ego-motion could also be removed from the initial optical flux in order to track moving objects. Initial theoretical work on this use would be from Adiv et. al ([15]), although this field has received a lot of attention in the past years, notably since dense stereo-vision processing is now possible in real-time. To finish with, the state of the art as regards vision-based SLAM (notably Davison [16] [17])) leads us to believe that laser-based sensors could possibly be replaced in the near future for most perception tasks, this being a strong incentive for us to develop visual inputs. Another source of possible improvements would be an evolution to handle collaborative perception, by means of merging grid-based beliefs in our algorithm.

III. CONCLUSION

Perception of moving objects, such as pedestrians, with minimal requirements on their size, moves or behaviour is a difficult task ; which will nevertheless be a key to enable autonomous navigation in urban environments, or even comprehensive assistance on current automotive devices. We proposed a novel technique based on an extension of the traditional occupancy grids registration, using probabilist propagation and extensive consideration of displacements and interactions over a restricted neighbourhood. An evolution from an initial ambitious proposition, our work shows promising results while being capable of real-time execution, although still being a work-in-progress. An interesting evolution would be its extension towards collaborative perception, which should be easier than for some other approaches due to the grid-based principle being kept. This proposition alone would be far from cooperative perception of moving objects. Key problems are indeed to be considered for this development to occur, among which relative localisation inaccuracies, or synchronisation problems. However, the grid-based framework we propose is naturally simpler to use in information-sharing applications than some other techniques, among which common SLAMs based on Kalman-related filters. We finally believe this application could be an interesting development from current work.

Fig. 1 .

 1 Fig. 1. Successive camera views

Fig. 4 .

 4 Fig. 4. Camera capture

Fig. 5 .

 5 Fig. 5. Lidar sensor output


Ben Chihaoui

Enit Faten

Imed Kacem
email: kacem@univ-metz.fr

Universite Paul

Verlaine Metz

Informatique Hadj-Alouane

Enit Dridi

Najoua ; Enit

Ben Faten

Chihaoui

Atidel B Hadj-Alouane

Najoua Dridi

Nidal Rezg

shop to Minimize the Makespan under Non-Availability Constraints and Different Release Dates

Keywords: FLOW SHOP SCHEDULING, AVAILABILITY, MAKESPAN, MAINTENANCE SCHEDULING, META-HEURISTICS scheduling, flow-shop, no-wait, non-availability, branch-and-bound algorithm scheduling, flow-shop, no-wait, non-availability, branch-and-bound algorithm

In this paper, we consider the two-machine no-wait flow-shop scheduling problem, when every machine is subject to one non-availability constraint and jobs have different release dates. The nonavailability intervals of the machines overlap and they are known in advance. We aim to find a nonresumable schedule that minimizes the makespan. We propose several lower bounds and upper bounds. These bounding procedures are used in a branch-and-bound algorithm. Computational experiments are carried out on a large set of instances and the obtained results show the effectiveness of our method.

Introduction

In this paper, we study the two-machine no-wait flowshop problem under non-availability constraints, when jobs have different release dates. The aim is to minimize the makespan under the three mentioned assumptions. We assume that each machine is unavailable during a fixed interval.

The intervals overlap and are known in advance. We assume that if a job cannot be finished before the non-availability period of a machine, the job needs to completely restart once the machine becomes available. This practical assumption is motivated by several real practical situations (preventive maintenance for instance). The second practical assumption considered in this work is related to the no-wait constraint. The main reasons of such a constraint consist in the technological structure of the shop itself. In no-wait scheduling, a job has to be continuously processed without idle-time between successive machines. Given the aim of this study, we recall some works related to the considered application and assumptions.

The numerous applications of our first assumption can be found in the paper by [START_REF] Bagchi | A review of TSP based approaches for flowshop scheduling[END_REF], in which they proposed several no-wait and blocking scheduling models. Moreover, they illustrated some ways in which the used modern manufacturing systems such as robotic cells may be modelled as a TSP (Travelling Salesman problem). [START_REF] Ronconi | A Branch-and-Bound Algorithm to Minimize the Makespan in a Flowshop with Blocking[END_REF] considered the minimization of the makespan criterion for the flowshop problem with blocking. A lower bound exploiting the occurrence of blocking is proposed. A branch-and-bound algorithm incorporating this lower bound is described and its efficiency is evaluated on several problem instances. The makespan minimization problem in a two-machine flowshop under no-wait constraints can be solved to optimality in ( ) n n O log time, where n is the number of jobs [START_REF] Gilmore | Sequencing a one-state variable machine: a solvable case of the travelling salesman problem[END_REF]. However, this problem is strongly NP-hard for 3 ≥ m where m is the number of machines, even if the buffer storage is limited [START_REF] Röck | The three machine-machine no-wait flow shop problem is NP-complete[END_REF]. Moreover, if the no-wait constraint is restricted to a sub-set of jobs then, the problem remains NP-hard in the strong sense [START_REF] Finke | Flowshops and extensions[END_REF]. The m-machine no-wait flowshop scheduling problem with the aim of minimizing the makespan and the total completion time was studied in [START_REF] Allahverdi | No-Wait Flowshops with Bicriteria of Makespan and Total Completion Time[END_REF]. A dominance rule and heuristics were proposed and used in a branch-and-bound algorithm. For more details on no-wait and blocking scheduling problems, the reader is invited to consult the state-of-the-art paper by [START_REF] Hall | A survey of machine scheduling problems with blocking and no-wait in process[END_REF].

The second assumption, that is, the non-availability constraint is one of the new modern concepts in the scheduling theory. Abundant literature exists on the related problems. Lee was the pioneer of this research field in scheduling theory [START_REF] Lee | Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint[END_REF]. Many papers were published during the last two decades and they involved various works on the flow-shop configuration. The makespan minimization on the two-machine flow-shop problem under non-availability constraints was proven to be NP-hard, even with a single non-availability period [START_REF] Espinouse | Minimizing the makespan in the two-machine no-wait flow-shop with limited machine availability[END_REF]. Aggoune and Portmann proposed a heuristic method for the general flow-shop problem under non-availability constraints on a subset of the machines [START_REF] Aggoune | Flow shop scheduling problem with limited machine availability: A heuristic approach[END_REF]. Lee studied the twomachine flowshop problem under the assumption that the non-availability time is known in advance [START_REF] Lee | Two-machine flowshop scheduling with availability constraints[END_REF]. Moreover, he considered the semiresumable, the resumable and the nonresumable cases. Lee also conducted a complexity analysis and elaborated a pseudo-polynomial dynamic programming algorithm to solve the problem to optimality. Heuristic algorithms were proposed and evaluated in the worst-case [START_REF] Lee | Two-machine flowshop scheduling with availability constraints[END_REF]). non-availability interval on the first machine under the nonresumable scenario [START_REF] Allaoui | Scheduling of a two-machine flowshop with availability constraints on the first machine[END_REF].

They improved the dynamic programming model proposed by [START_REF] Lee | Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint[END_REF]. This method allowed them to reduce the computational effort. Some conditions, where Johnson's rule gives the optimal solution were specified. They proved that the worst-case performance bound of Johnson's rule is 2 [START_REF] Allaoui | Scheduling of a two-machine flowshop with availability constraints on the first machine[END_REF]. For more details on the non-availability constraints in scheduling problems, we refer to the survey-papers by [START_REF] Schmidt | Scheduling with limited machine availability[END_REF] and [START_REF] Ma | A survey of scheduling with deterministic machine availability constraints[END_REF].

Finally, our third assumption states that jobs have different release dates. Several literature works considered this case. A sample of them is summarized as follows. First, we note that the classical version consisting in the makespan minimization on two-machine flow-shop subject to jobs release

dates ( max / / 2 C r F j
) is NP-hard in the strong sense [START_REF] Lenstra | Complexity of machine scheduling problems[END_REF]. Thus, heuristic approaches were widely studied. In [START_REF] Potts | Analysis of heuristics for two-machine flow-shop sequencing subject to release dates[END_REF] four heuristics were proposed to solve the same problem. For three of them, the worst-case performance ratio is of 2. Each one of the heuristics can be implemented in ( ) . In [START_REF] Kashyrskikh | A (3/2)-approximation algorithm for twomachine flwo-shop sequencing subject to release dates[END_REF], by modifying Potts algorithm [START_REF] Potts | Analysis of heuristics for two-machine flow-shop sequencing subject to release dates[END_REF], the authors reduced the worst-case performance ratio to 2 / 3 however, the time complexity remains in

n n O log time.
) log ( 3 n n O
. A polynomial time approximation scheme (PTAS) was proposed in [START_REF] Hall | Approximability of flowshop scheduling[END_REF]. In [START_REF] Kovalyov | A polynomial approximation scheme for problem F2/r j /C max[END_REF] a polynomial approximation procedure was elaborated for the max / / 2 C r F j problem. Such a procedure was based on a dynamic programming approach using modified release dates and processing times. Compared to the one proposed in [START_REF] Hall | A polynomial approximation scheme for a constrained flow-shop scheduling problem[END_REF]) a better time complexity was obtained for large values of n. Branch-and-bound methods were exploited in [START_REF] Cheng | A computational study with a new algorithm for threemachine permutation flow shop problem with release times[END_REF] for solving the max / / 3 C r F j problem by incorporating a lower bound determined for some particular cases. Two dominance rules were used to construct an initial schedule. These rules reduced the search space by decomposing the problem into a finite set of sub-problems.

To conclude, according to this literature review we can mention that in all studied papers, at most two of the three assumptions were considered. A sample of these works includes [START_REF] Cheng | 3/2 approximation for two-machine no-wait flowshop scheduling with availability constraints[END_REF][START_REF] Espinouse | Minimizing the makespan in the two-machine no-wait flow-shop with limited machine availability[END_REF][START_REF] Espinouse | Complexity results and approximation for the two-machine no-wait flow-shop with limited machine availability[END_REF][START_REF] Kubzin | Approximation Algorithms for Two-Machine Flow Shop No-Wait Scheduling with a Non-Availability Interval[END_REF][START_REF] Wang | Heuristics for two-machine no-wait flowshop scheduling with availability constraints[END_REF], where no-wait and non-availability constraints were jointly considered. Finally, the non-availability constraint and the different job release dates were considered at the same time by [START_REF] França | Genetic algorithms for the no-wait flowshop sequencing problem with time restrictions[END_REF], where genetic algorithms were elaborated. Moreover, the same problem was solved in Bianco et al 1999 by a mathematical programming method and two heuristics. However, according to the best of our knowledge there is no previous work related to the studied problem, that is, the minimization of the makespan in two-machine no-wait flow-shop under non-availability constraints and different job release dates assumption. For this reason, this paper is a first successful attempt to design a branch-and-bound algorithm with an interesting performance.

The reminder of the paper is organized as follows. Section 2 gives a precise formulation. In Section 3, we describe the proposed branch-and-bound method. Computational results are given and discussed in Section 4. Finally, we conclude the paper by some remarks and perspectives in the last section.

Problem formulation

The problem can be stated as follows. We have a set ) has a positive release date r j known in advance. Its first (respectively the second) operation on the first (respectively the second) machine has a positive processing time of a j (respectively of b j ). The objective is to find a feasible schedule with the aim of minimizing the makespan (i.e., the completion time of the last operation performed on the second machine). From Section 1, this problem is NP-hard in the strong sense since it is a generalization of other problems of this type (for instance, see the [START_REF] Lenstra | Complexity of machine scheduling problems[END_REF].

max / / 2 C r F j problem in

Branch-and-bound algorithm

Motivated by the practical advantages of the branch-and-bound approach, we elaborated an algorithm of this type to solve our considered problem. Such an approach aims to find an optimal solution (or an enhanced one) by reducing the search space based on different tools (lower bounds, dominance rules, upper bounds…). When it is not possible to obtain the optimal solution such an approach allows us to improve the result of other heuristic methods that can be used as an initial upper bound. In this section we give the description of our branch-and-bound algorithm. It will be noted B&B in the remainder of the paper.

Branching scheme and search strategy

The B&B starts by computing an initial solution which provides the first upper bound. Every node represents a partial schedule. The branching scheme consists in scheduling a new job after a partial schedule. The search space is explored by using the depth first strategy. Before creating a new node, a lower bound is computed. If the value of such a lower bound is greater than the value of the upper bound, then this node is removed. Moreover, before any branching procedure, we increase the release date of every jobs J j ∈ satisfying one of the two following conditions: (

1 s a r j j > + ) or ( 2 s b a r j j j > + +
). Indeed, in the two cases the first operation of job j cannot be performed before s 1 .

Thus, we can increase the release date as follows:

{ } j j j a t t r r - = 2 1 , , max
. Consequently, all the partial sequences beginning with these jobs verifying one of the conditions are eliminated.

Upper bounds

The quality of the used upper bounds is very important to enhance the effectiveness of any branchand-bound algorithm. For this reason, we investigated different ways to determine the initial upper bound. Three methods are used:

A greedy search (denoted as GS): it consists in applying the B&B for only n nodes by using the depth best first strategy.

Two Heuristics (H1 and H2) developed by Ben Chihaoui et al 2009.

A genetic algorithm (denoted as GA).

For self-consistency, we recall the principle of of Heuristics (H1 and H2). These two heuristics are based on the algorithms in [START_REF] Gilmore | Sequencing a one-state variable machine: a solvable case of the travelling salesman problem[END_REF]Cheng and[START_REF] Cheng | 3/2 approximation for two-machine no-wait flowshop scheduling with availability constraints[END_REF]. Before describing these heuristics, we present additional notations. 1. Try to find a good schedule in which the availability constraint is inactive (a fictitious job is added).

2. Relax the availability constraint, and then move some jobs from the beginning to the end or vice versa to meet the unavailability constraint.

3. Optimally schedule some critical job and its adjacent jobs and schedule the other jobs according to Gilmore and Gomory's algorithm.

Description of H1

The first heuristic, H1, is based on the decomposition of the problem into many sub-problems.

Description of H2

The second heuristic, H2, is based on a modification of H1 to use the concept of a reactive scheduling. Indeed, a job j can arrive to the shop after a job i. However, the execution of j before i may give a better solution.

In H2, sub-problems are defined as follows. First, jobs arriving at i r are temporarily scheduled to obtain their finish date, referred to as i f . Then the sub-problem consists in rescheduling all jobs arriving at i r along with jobs arriving before i f .

The first sub-problems concern the jobs in set 0 D . We apply CL to schedule set 0 I . The makespan obtained is considered as 0 f . Set 0 D includes jobs of set 0 I and those which release dates verify the condition:

0 0 f r r j ≤ ≤ . Let { } j j k r r max = .
We keep from the solution obtained by the application of CL on 0 D , the sequence of jobs beginning their execution on 1 M before the date 1

+ k r . Let 2 k σ be the obtained sequence.
The second sub-problem concerns jobs of set 1 D .

CL is applied to schedule the set

Description of the genetic algorithm:

We use a classical genetic algorithm in which the solutions or chromosomes are represented as a permutation of J indicating for every job its position in the schedule (Fig. 1 (a)). The mutation operator consists in choosing two random positions of the mutated genes and in swapping the two corresponding jobs (Fig. 1 (b)). The crossover operator consists in selecting a random position and in exchanging the genetic information between two parents to construct two offspring according to the selected position (Fig. 1 (c)). The construction consists in copying each subset of jobs in the same order as they appear in the corresponding parent so that the offspring will be feasible. The number of generations is fixed to 100 and the initial population is fixed to 100 chromosomes randomly generated by iteratively mutating the FIFO sequence (the FIFO sequence consists in scheduling jobs in non-decreasing order of their release dates).

The initial upper bound used in the B&B is the minimum of the obtained values with these three methods.

//Please insert Figure 1 about here

Lower bounds

It is well known that the quality of the lower bound is one of the most critical elements of any branch-and-bound algorithm. In most cases, computing a lower bound consists in relaxing some constraints (in different ways) and in solving a new easier problem. In this paper, we consider two main relaxations to derive lower bounds. The first one replaces the two non-availability intervals by two fictitious jobs. The second relaxation reduces the flow-shop configuration to a single-machine problem. Before presenting the proposed lower bounds we need to define the data of the fictitious jobs. Let f1 be the first fictitious job and f2 be the second one. Their processing times are defined as follows:

1 2 1 s s a f - = , 2 1 1 s t b f - = , 1 1 s r f = , 2 1 2 s t a f - = , 1 2 2 t t b f - = , 2 2 s r f = . Moreover, we define a global set of jobs f J as follows { } 2 , 1 f f J J f ∪ = .
We derived five lower bounds denoted: LB1, LB2, LB3, LB4 and LB5. Before computing each lower bound the release date of every job J j ∈ , not yet scheduled, is updated according to whether or not the completion time of the scheduled jobs is greater than the starting time of the non-availability interval on machine M 1 . The construction of every lower bound is described as follows.

LB1

In this lower bound, we transform the problem into an instance of a single-machine problem of the type 1/r j /C max . More precisely, the first machine is removed and we only consider the second machine. In the new obtained instance, we first generate the two fictitious jobs. Then, with every f J j ∈ it is associated a new job to be performed on the single-machine such that the release date and the processing time are respectively equal to j j a r + and b j . The resulting problem is optimally solved by the FIFO (First In First Out) rule.

LB2

In this lower bound, we transform the problem into an instance of the type 1, h 1 /r j , q j /C max . More precisely, the second machine is removed and the second operation of every job

f J j ∈
is replaced by a tail (or a delivery time) equal to b j . In the new obtained instance, we first generate the two fictitious jobs. Then, with every

f J j ∈
it is associated a new job to be performed on the singlemachine such that the release date, the processing time and the tail are respectively equal to j r , j a and b j . Moreover, the new fictitious jobs must start exactly at their respective release dates. The resulting problem is NP-Hard, but the lower bound is obtained by solving the preemptive version to optimality using Jackson's rule (see [START_REF] Carlier | Exact resolution of the one-machine sequencing problem with no machine idle time[END_REF].

LB3

The principle of this bound is similar to the previous one. We follow the same relaxations as in LB2

to transform the problem into an instance of the type 1/r j , q j /C max . The only difference is the fact that the new jobs associated with the fictitious jobs are not constrained to start exactly at their respective release dates. The resulting problem is solved by the branch-and-bound proposed in [START_REF] Carlier | The one-machine sequencing problem[END_REF].

LB4

The principle of this bound is based on the relaxations used in LB1. We follow the same relaxations.

The only difference is that the new jobs associated with the fictitious jobs are constrained to be performed exactly in the interval ( 2 2 ,t s ). Thus, they can be considered as a non-availability interval.

Moreover, the resumable scenario is considered. The resulting problem belongs to the productive than LB1.

LB5

The fifth lower bound is obtained by transforming the problem into an instance of the 1, h 1 /r j , nrs/C max type. In such a case, the first machine is removed and we only consider the second machine. In the new obtained instance, we do not generate any fictitious job. Then, with every J j ∈ it is associated a new job to be performed on the single-machine such that the release date and the processing time are respectively equal to j j a r + and b j . Moreover, the single-machine is considered as non-available during the interval ( 2 2 ,t s ). The resulting problem is solved (under the nonresumable scenario) by the dynamic programming algorithm proposed in [START_REF] Kacem | Approximation algorithms for single machine scheduling with one unavailability period. 4OR[END_REF]. Clearly, this bound outperforms LB1. However, it needs more computation time.

Numerical experiments

In this section, we describe the numerical experiments carried out in order to evaluate our algorithms. The B&B was implemented in the C language and tested on an Intel Pentium IV 3 GHz ) of the defined horizon, where

n T s t / 1 1 + = , n T s s / 25 . 0 1 2 × + = and n T s t / 25 . 1 2 2 × + = .
Based on the values of parameters R and s 1 , we define eight groups of instances (1, 2, 3, 4, 5, 6, 7 and 8) as it is shown in Table 1.

//Please insert Table 1 about here

Lower and upper bounds evaluation

To evaluate the performance of the lower bounds presented in this paper, we compute the average value obtained from ten instances for every combination of parameters. In order to check the effectiveness of GS and GA compared with H1 and H2, we compute the average value obtained from the ten instances. The different results are reported in Tables 23456. For every group the best lower bound (LB) is written in boldface. For the upper bound (UB) the Gap in percentage is calculated with respect to the best lower bound. From Tables 23456, we can make the following remarks:

//Please insert

• Except for the case where n=5, one can remark that either GS or GA gives the best results in most cases.

• For the lower ranges of release dates, H2 gives better results than H1. This is due to the reactive aspect of H2. However, for a larger range of release dates, H1 gives better results than H2.

• For the lower range of the release dates, LB5 is the best lower bound. However, we can remark that LB1 gives almost the same results as LB5. Hence, LB1 represents an interesting bound with a good quality and a short computation time.

• For a larger range of the release dates values, the different lower bounds give similar results.

• When the non-availability is in the middle of the horizon, the bounds values are generally better (the gap is smaller), and we notice that LB5 and LB1 generally remain the best in the two cases.

• The computation time of the different lower bounds is close to zero. However, the computation time of LB5 for n=20 is about 120 s.

• The gap between the lower and upper bounds values is relatively small. This allows us to elaborate an efficient B&B.

Given the above remarks, and taking into account the time complexity of every lower bound, we have decided to mainly use LB1 in the B&B and to employ LB3 and LB5 in the Greedy Search.

B&B performance

In order to evaluate the B&B performance, computational experiments are conducted on the same instances used to evaluate the LB and UB. From Tables 7-10, we can make the following remarks:

• The average value of the gap is about 3%. This value clearly shows the good performance of the B&B and the tightness of the upper and lower bounds.

• The average value of the gap decreases when n increases.

• Computation time is larger for higher values of n.

• Computation time and average number of the explored nodes are relatively high when the release dates range is independent of n (r j in [1,100] and in [1,200]) and the non-availability interval is in the middle of the horizon. Consequently, the problem is more difficult for lower range of release dates and when the non-availability is in the middle of the horizon. Indeed, if the non-availability is in the beginning of the horizon, it is skipped early in the horizon (after sequencing some jobs), then the two machines become available.

• The B&B can solve instances with up to 20 jobs, except for instances of groups 1 to 4 (r j in [1,100] and in [1,200]). Indeed, the low range of release dates in these groups increases the search space. Consequently, the search tree is bigger and the problem is difficult to solve.

• The preliminary elimination is more efficient when n is large.

• The lower bounds and, in particular, LB1 and LB5 allow for an extensive elimination of nodes. Thus, they enhance the B&B effectiveness.

For larger values of n (30, 40 and 50) we tested the performance of the Greedy Search heuristic by reporting the following parameters in Table 8:

• LB: average of the best lower bound values

• t_GS: average of the GS computation times

• G_H(%): average value of the gap between H (H can be H1, H2, GA and GS) and LB.

The average values of the computation times required by H1, H2 and GA are close to zero second.

The obtained performances are reported in Table 11.

//Please insert Table 11 about here

From Table 11, we can make the following conclusions:

• The maximum value of the gap obtained for the different methods is in average of 11% and the minimum is of 1%. Thus, the methods that we developed as well as the elaborated lower bounds yield good results.

• The value of G_GS is of 1% whereas G_GA ≈ 8%, G_H1 ≈ 4% and G_H2 ≈ 11%. Hence, the Greedy Search clearly outperforms all the other algorithms. The GS has a larger computation time (about 0,4s in average) than the other algorithms. Nevertheless, such a value is very small in practical situations.

• In conclusion, our GS algorithm seems to be a very interesting method in order to obtain a nearoptimal solution (gap of 1%) in a short computation time (in less than 1s) despite the strong NP-Hardness of the studied problem.

Conclusion

This paper studied the two-machine no-wait flow-shop scheduling problem, when every machine is subject to one non-availability constraint and jobs have different release dates. The aim is to minimize the makespan. Several lower and upper bounds are proposed and incorporated in a branch-and-bound algorithm. Numerical experiments were carried out on a large set of instances.

The obtained results showed that we can find the optimal solution for problems with up to 20 jobs within a reasonable amount of computation time. Moreover, the branch-and-bound algorithm can be converted into a greedy search heuristic, GS, that has a good performance. Such a heuristic is able to give a near-optimal solution (gap of 1%) in a short computation time (in less than 1s) despite the

  of jobs arriving at the time k r ; • k O ( k D ): Set of jobs of the sub-problem k in H1 (H2); The sequence found by scheduling the jobs of k O ( k D ) in H1 (H2); • CL: Algorithm 3 of Cheng and Liu 2003. Description of CL In Cheng and Liu 2003, the authors study the two-machine no-wait flowshop problem in which each machine may have an unavailable interval. A 3/2-approximation algorithm is developed for the problem resolution when the unavailable intervals on the two machines overlap. It consists in the following steps:

Iσ

  to which we include jobs of the set 0 D not kept in the sequence 2 0 σ . The makespan of the resulted solution is 1 f . Beside the jobs of the set 1 to obtain a new partial sequence (Ben Chihaoui et al 2009).

  processor and 512 M RAM, in the WINDOWS XP environment. The instances were randomly generated. For the experiments, we generated ten instances for every combination of parameters as follows. The number of jobs n was chosen in{

Fig. 1 .

 1 Fig. 1. Representation and operators

  The fourth one is based on the iterative use of the third heuristic

	and it has a worst-case performance ratio of	5	/	3	and a time complexity of	O	( 3 n	log	n	)

Table 2 about here //Please insert Table 3 about here //Please insert Table 4 about here //Please insert Table 5 about here //Please insert Table 6 about here

insert Table 7 about here //Please insert Table 8 about here //Please insert Table 9 about here //Please insert Table 10 about here

  The computation time is limited to 7200s. For the node evaluation we use first LB1, if the node is not eliminated, we use LB5. The B&B performances are

	presented in Tables 7-10, where the following parameters are reported:
	• Copt: average of the optimal makespan values
	• UB: average of the best upper bound values
	• CPU: average of the B&B computation time values in seconds
	• N d : average number of eliminated nodes in the preliminary elimination
	• N ex : average number of explored nodes
	• N el : average number of eliminated nodes • Gap (%): average value of the gap between UB and Copt F o r //Please
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y
	11/19

  Hardness of the studied problem.In a future work, we aim to develop new lower bounds with possibly other types of relaxations, as well as a branch-and-cut method to optimally solve instances of larger sizes. Moreover, the study of new metaheuristic algorithms and representations seems to be interesting in order to improve the

	strong NP-B&B performances.
	F o r F o r F o r F o r
	P P P P
	e e e e
	e r e r e r e r
	R R R R
	e e e e
	v i e v i e v i e v i e
	w w w w
	O n l O n l O n l O n l
	y y y y
	13/19 16/19

Table 5 . Results of lower and upper bounds for n=20

 5

		Average values of LB	Gap of UB (in %)
	Groups LB1 LB2 LB3 LB5 H1 H2 GA GS
	1	1126 1140 1128 1138 20 20 13 32
	2	1199 1195 1195 1199	8 16 13 30
	3	1221 1109 1099 1231 13 18	8 27
	4	1244 1154 1154 1250 12 19 12 22
	5	2034 2034 2029 2034	0	6	3	0
	6	2060 2068 2068 2060	2	6	5	1
	7	4022 4022 4022 4022	2	4	2	0
	8	4016 4015 4015 4016	1	2	2	1

Table 6 . Summary of computational times of LB and UB (in seconds)

 6

	n LB1 LB2 LB3 LB5 H1	H2	GA	GS
	5	0	0	0	0	0	0 0,15 0,02
	10	0	0	0	0	0	0 0,15 0,02
	15	0	0	0	2	0	0 0,31 0,05
	20	0	0	0 120	0	0 0,31 0,05

Table 7 .

 7 B&B performance for n=5Groups UB Copt CPU N d N el N ex Gap

	1	453 443	0	3 12 33	2
	2	484 467	0	0 23 45	3
	3	520 489	0	6	7 25	6
	4	594 562	0	1 19 33	6
	5	592 553	0	7 10 15	7
	6	644 628	0	5 10 19	2
	7	906 902	0	2	5	7	0
	8	1009 1009	0	2	4	3	0

Table 8 . B&B performance for n=10

 8

	Groups UB Copt CPU N d	N el	N ex	Gap
	1	748 708	0 4 146217 134475	6
	2	749 713	1 0 287549 143090	5
	3	766 736	0 6 131878 147749	4
	4	780 745	0 2 95430 42601	5
	5	1094 1084	0 10	2220	1760	1
	6	1052 1034	0 17 11246	9482	2
	7	1899 1899	0 3	2333	1571	0
	8	1968 1957	0 5	4424	2518	1

Table 9 . B&B performance for n=15

 9

	Groups UB Copt CPU N d	N el	N ex	Gap
	1	1045 1010 1154 3 247862574 316505246	3
	2	1059 1019 3483 0 1623109776 495159902	4
	3	1065 1019 952 9 170304340 254320785	5
	4	1024 974 2247 5 1039966545 404465743	5
	5	1616 1604 320 14	4941954	3579316	1
	6	1611 1550 3600 24	24620459 16281991	4
	7	2937 2935 180 6	4771824	2984638	0
	8	2925 2920 1600 17	91077335 130196286	0
		Table 10. B&B performance for n=20
	Groups UB Copt CPU N d	N el	N ex	Gap
	1,2,3,4	The B&B failed to improve the upper bound before the time limit
	5	2089 2065 1356 18 10440088 16649816	1
	6	2225 2145 7200 57 218131733 192697602	4
	7	3899 3887 5360 12 138114617 58012023	0
	8	3810 3809 6200 5 152033322 232010045	0

Table 11 . Performance of algorithms H1, H2, GA and GS for n=30 to 50

 11

	n LB	GA	GS	H1	H2	G_H1 G_H2 G_GA G_GS t_GS
	30 3087 3245 3104 3195 3403	3%	10%	5%	1%	0,1
	40 4042 4318 4077 4154 4441	3%	10%	7%	1%	0,3
	50 4971 5524 4999 5189 5521	4%	11%	11%	1%	0,6

http://mc.manuscriptcentral.com/tprs Email: ijpr@lboro.ac.ukInternational Journal of Production Research

Acknowledgements:

We thank referees for their constructive comments which significantly improved the paper.