Ph.D Jozsef Haller
email: haller@koki.hu

J Hohmann

T F Freund

The effect of Echinacea preparations in three laboratory tests of anxiety. Comparison with chlordiazepoxide

Keywords: Echinacea, anxiety, rat, elevated plus-maze, social interaction, stress-induced social avoidance Echinacea, anxiety, rat, elevated plus-maze, social interaction, stressinduced social avoidance

Echinacea preparations are traditionally used to treat upper respiratory infections and inflammations. No psychotropic effects of Echinacea were reported so far, although some recently reported active constituents are behaviorally active. Prompted by these findings, we evaluated the anxiolytic potential of 5 different Echinacea preparations. Three of these decreased anxiety but two of them had a very narrow effective dose range. Only one extract decreased anxiety within a wide dose-range (3-8 mg/kg). Anxiolytic effects were consistently seen in three different tests of anxiety, the elevated plus-maze, social interaction and shockinduced social avoidance tests. No locomotor suppressant effects were seen at any dose.

Noteworthy, the doses that showed anxiolytic effects in the present study were much lower than those used in the laboratory models of the traditional indications. Chlordiazepoxide robustly decreased anxiety-like behavior in all tests but suppressed locomotion at higher doses. Perceived and real risks of conventional medications increase the demand for alternative therapies, provided that these are safe and efficient. Earlier evidence shows that Echinacea preparations have an excellent safety profile, while our findings suggest for the first time that certain preparations have a considerable anxiolytic potential. Further research is required to identify factors that differentiate efficient and inefficient preparations.

Introduction

Echinacea preparations have been used for centuries by Native Americans as antiinflammatory agents and for the treatment of upper respiratory infections; such treatments were incorporated into Western medicine about a century ago [START_REF] Barnes | Echinacea species (Echinacea angustifolia (DC.) Hell., Echinacea pallida (Nutt.) Nutt.,Echinacea purpurea (L.) Moench): a review of their chemistry, pharmacology and clinical properties[END_REF][START_REF] Birt | Echinacea in infection[END_REF][START_REF] Blumenthal | The complete German Commission E monographs, Therapeutic guide to herbal medicines[END_REF][START_REF] Borchers | Inflammation and Native American medicine: the role of botanicals[END_REF]. No psychotropic effects of Echinacea preparations have yet been elucidated, but recent studies identified active constituents by which these may affect behavior, especially anxiety-like behavior.

Echinacea preparations contain a large number of different alkamydes, the structures of which are very similar to that of the endocannabinoid anandamide [START_REF] Bauer | TLC and HPLC Analysis of Alkamides in Echinacea Drugs[END_REF][START_REF] Wu | Metabolic profiling of echinacea genotypes and a test of alternative taxonomic treatments[END_REF]. Certain alkamydes behave as cannabinomimetics at both the cannabinoid CB1 and CB2 receptor, and inhibit the anandamide-degrading enzyme fatty acid amid hydrolase (FAAH) [START_REF] Woelkart | The endocannabinoid system as a target for alkamides from Echinacea angustifolia roots[END_REF]. Although the interaction between cannabinoids and anxiety is complex [START_REF] Witkin | A role for cannabinoid CB1 receptors in mood and anxiety disorders[END_REF], CB1 signaling has been repeatedly implicated in the control of anxiety [START_REF] Freund | Interneuron Diversity series: Rhythm and mood in perisomatic inhibition[END_REF][START_REF] Haller | Stress-induced social avoidance: a new model of stressinduced anxiety?[END_REF]. Additionally, FAAH inhibition is considered a promising new anxiolytic drug target [START_REF] Piomelli | Pharmacological profile of the selective FAAH inhibitor KDS-4103 (URB597)[END_REF]. Unidentified components of Echinacea extracts have been shown to be agonists at the transient receptor potential vanilloid-1 (TRPV1) receptors [START_REF] Birt | Echinacea in infection[END_REF], a mechanism that has also been implicated in the control of anxiety [START_REF] Starowicz | TRPV1 receptors in the central nervous system: potential for previously unforeseen therapeutic applications[END_REF]. Certain Echinacea preparations contain rosmarinic acid, which has decreased anxiety in laboratory models at low doses [START_REF] Biber | Analytical characterisation of homoeopathic mother tinctures[END_REF][START_REF] Pereira | Neurobehavioral and genotoxic aspects of rosmarinic acid[END_REF]. In addition, caffeic acid is one of the major constituents of Echinacea; this compound decreases anxiety by indirectly modulating α 1A adrenoceptors [START_REF] Takeda | Caffeic acid produces antidepressive-and/or anxiolytic-like effects through indirect modulation of the alpha 1A-adrenoceptor system in mice[END_REF]. Also noteworthy is the fact that the above-listed constituents of Echinacea preparations readily cross the blood-brain barrier [START_REF] Birt | Echinacea in infection[END_REF][START_REF] Woelkart | Pharmacokinetics and Tissue Distribution of Dodeca-2E,4E,8E,10E/Z-tetraenoic Acid Isobutylamides after Oral Administration in Rats[END_REF][START_REF] Konishi | Pharmacokinetic study of caffeic and rosmarinic acids in rats after oral administration[END_REF]. receptors [START_REF] Woelkart | The endocannabinoid system as a target for alkamides from Echinacea angustifolia roots[END_REF][START_REF] Woelkart | Pharmacokinetics and Tissue Distribution of Dodeca-2E,4E,8E,10E/Z-tetraenoic Acid Isobutylamides after Oral Administration in Rats[END_REF]). Yet, anandamide -the structure of which is very similar to that of alkamides-affects receptors other than the CB1, e.g. de PPARα receptor [START_REF] Mazzola | Fatty acid amide hydrolase (FAAH) inhibition enhances memory acquisition through activation of PPAR-alpha nuclear receptors[END_REF]. It is also worth noting that the TRPV1 agonist activity of Echinacea preparations is rather strong as it is produced at doses similar to those employed here [START_REF] Birt | Echinacea in infection[END_REF]. These considerations suggest that particular components of Echinacea preparations, alone or in combination with synergistic/additive effects, show great promise for anxiolytic drug development.

Prompted by the above findings, we started a series of studies to evaluate the anxiolytic potential of Echinacea preparations. It is noteworthy that, despite the extensive research on and wide use of this plant, no psychotropic effects have thus far been identified. We believe that this paucity of data is mainly due to two factors. First, the anxiolytic effect was detected at doses that were about one order of magnitude lower than those used for the traditional indications (see below). Secondly, only a fraction of Echinacea preparations showed consistent anxiolytic effects in our studies. In addition, the improvement of infectious diseases inherently improves mood, which may subjectively mask the intrinsic anxiolytic effects of the extracts that do show anxiolytic effects.

Materials and Methods

Animals

Subjects were 3-month-old male Wistar rats provided by Charles River Laboratories (Budapest, Hungary), and weighing 250-300 g. Rats were fed on standard laboratory food (Charles River Laboratories). Water was available ad libitum.

Experimental design

Experiment 1 evaluated the anxiolytic potential of Extract No. 1 in the elevated plusmaze test. This experiment was also used to establish effective dose-ranges; therefore, 7 doses were tested (vehicle, 0.5, 1, 1.5, 2, 3, and 6 mg/kg). Rats were submitted to the test 30 min after treatment. Sample size was 10 per treatment group.

Experiment 2-5 tested the efficacy of four additional extracts under similar conditions.

Based on the results of Experiment 1, we tested these extracts in the 1-5 mg/kg dose-range, except for Extract No. V, which proved to have a very narrow effective dose range in preliminary studies. Therefore, the increment of doses was 0.5 mg/kg with this extract. The four extracts were tested in separate experiments. Sample size was 8-10 per group, except for Extract No V, where sample size was 16 per group.

Based on the results of Experiments 1-5, Extract No IV was selected for further analysis. In Experiment 6 and 7, we studied a wider dose range (1-8 mg/kg) in the elevated plus-maze, 30 min and 1h after treatments, respectively. Sample size was 12 per group. The doses that proved most effective in Experiments 6 and 7 were also studied in the social interaction and shock-induced social avoidance tests (Experiments 8-9). Sample size was 12 The behavioral effects of the benzodiazepine chlordiazepoxide were also studied for comparison. In Experiment 11, we studied the effects of 1, 2, 3, 4, 6, 8, 10, 12, 14 mg/kg chlordiazepoxide in the elevated plus-maze, 30 min after treatment. This detailed doseresponse curve was taken as chlordiazepoxide was shown to have a biphasic effect on locomotion. Sample size was 10-14 per treatment group. Experiment 12 established the effects of chlordiazepoxide in the elevated plus-maze 1h after treatments. The dose-range studied was 2-8 mg/kg, and included doses that increased and decreased locomotion in Experiment 11. Sample size was 10 per group. The effects of chlordiazepoxide in the social interaction and shock-induced social avoidance tests were investigated in Experiments 13 and 14. In the social interaction test, rats were given 1, 2, 5, and 10 mg/kg chlordiazepoxide.

Sample size was 12 per group. A specific dose-range was investigated in the shock-induced social avoidance test. Previous experience showed that this test is especially sensitive to the sedative effects of chlordiazepoxide. Therefore, rats were treated with 0.5, 1, 2.5, and 5 mg/kg in this test. Because both the anxiolytic and sedative effects of chlordiazepoxide were robust in earlier experiments, sample size was 7 in this experiment.

Pharmacological treatment

The following extracts were studied in the experiments: Echinacea purpurea root extract (EPO Istituto Farmacochimico Fitoterapico, Milano, Italy; batch No 0700326; extraction procedure: ethanol 4% V/V; ratio herbal drug : drug preparation: 5-12:1; excipient: maize dextrin 30%; marker: Echinacoside 4%), Echinacea purpurea herb extract (Finzelberg GmbH and Co. KG, Andernach, Germany;Batch No. 07022307; extraction: ethanol 60% M/M; ratio herbal drug : native extract: 4-10 : 1; excipients: maltodextrin 13% and colloidal silica anhydrate 2%; marker: total phenols 4%), and 419061; extraction: ethanol 85% V/V; ratio herbal drug : native extract: 6.5-8 : 1; excipient: maltodextrin 30%; marker: Echinacoside 4%). All three extracts were dissolved in 0.4% methylcellulose in saline. We also studied a hydroalcoholic extract of Echinacea purpurea roots (FitoChem Ltd. Monor, Hungary;Batch No. FECH-010011205;extraction: ethanol 70% V/V; ratio herbal drug : native extract: 4-8 : 1; excipient: none; marker: not standardized). Before experimental use, the ethanol was evaporated at 4 o C, and the dry residue was dissolved in 0.4% methylcellulose in saline. Finally, we investigated an Echinacea angustifolia root extract prepared by the Department of Pharmacognosy, Faculty of Pharmacy, University of Szeged (Hungary). Briefly, 80 g air-dried and powdered root of Echinacea purpurea was extracted with 1x300 and 2x200 ml 70% EtOH using an ultrasonic extractor for 10-10 min. The filtered extracts were combined, concentrated and dissolved in 15 ml water. The aqueous solution was lyophilized, yielding 8.67 g dark brown and semifluid extract. Before experimental use, it was physically dispersed, dissolved in small amounts of dimethyl sulphoxide (DMSO) and diluted to the final volume by 0.4% methylcellulose. The final concentration of DMSO was 3.3% at each test concentration.

Controls received a similar mixture of DMSO and methylcellulose. Chlordiazepoxide came from Sigma (Budapest, Hungary) and was dissolved in 0.4% methylcellulose in saline.

All treatments were administered per os in a volume of 2 ml/kg. Controls received 0.4% methylcellulose except for the last mentioned extract (see above).

Behavioral tests

Behavioral studies were performed in the early hours of the dark (active) period between 1100 and 1300 h. Each experiment was performed in several series balanced over groups. Group assignment was random. Behavior was video recorded and later analyzed by an experimenter blind to treatment conditions. The tests were performed as described earlier [START_REF] Haller | Housing conditions and the anxiolytic efficacy of buspirone: the relationship between main and side effects[END_REF][START_REF] Haller | Stress-induced social avoidance: a new model of stressinduced anxiety?[END_REF][START_REF] Haller | Stress, social avoidance and anxiolytics: a potential model of stress-induced anxiety[END_REF][START_REF] Leveleki | Pharmacological evaluation of the stress-induced social avoidance model of anxiety[END_REF]. Briefly, the elevated plus-maze (arm length 50 cm, arm width 15 cm, wall height 30 cm and platform height 80 cm) was illuminated by dim red light. Rats were placed into the center of the apparatus and were allowed to explore it for 5 min. Closed-arm entries were considered indicators of locomotor activity, whereas open arm exploration (duration and % entries) was used as a measure of anxiety [START_REF] Pellow | Validation of open: closed arm entries in an elevated plus-maze as a measure of anxiety in the rat[END_REF]. The social interaction test arena was a plastic box of 40x60x60 cm that was lit by white light. Pairs of similarly treated rats were placed in the arena, and their behavior was recorded for 10 min. Subjects were unfamiliar to each other. In this test, anxiety is shown by the duration of social interactions defined as sniffing movements directed towards the partner rat. Exploration/walking and resting are indicative of sedative or muscle-relaxant effects [START_REF] File | Can social interaction be used to measure anxiety?[END_REF][START_REF] File | Lack of effects of 5HT3 receptor antagonists in the social interaction and elevated plus-maze tests of anxiety in the rat[END_REF][START_REF] Guy | Pharmacological characterization of a modified social interaction model of anxiety in the rat[END_REF]. The social avoidance test was performed on two consecutive days. On the first day, rats were exposed to 10 electric shocks (3 mA) over 5 min in a plastic box of 30x30x30 cm. Controls were placed into the box, but received no shocks. On the next day, rats were studied in a three-compartment plastic cage. The subject was placed in the habituation compartment (15 x 40 cm) that was separated from the rest of the cage by an opaque sliding door. After 3 min, the sliding door was removed and the rat was allowed to explore the test arena (40 cm x 40 cm) for 5 min.

The third compartment contained a large unfamiliar male confined behind a transparent, perforated Plexiglas wall. In this test, anxiety is indicated by the number of entries into, and the time spent in the test arena i.e. in the vicinity of the unfamiliar opponent. Shock exposure strongly inhibits opponent visits, a response that is abolished by anxiolytics [START_REF] Leveleki | Pharmacological evaluation of the stress-induced social avoidance model of anxiety[END_REF]. The open-field was a circular area with a diameter of 90 cm. Rats were placed next to the wall of the open-field and were allowed to explore the arena for 10 min. The arena was

HPLC analysis

HPLC analysis was carried out on a Waters instrument (Milford, MA, USA; solvent delivery system 6000A, pump 600E, UV detector type 2487, Rheodyne 7725i injector, Empower software). The alkamide profile was investigated at 25 ºC on LiChrospher RP-18 column (5 µm, 125-4 mm, Merck) using linear gradient of acetonitrile-H2O 2:3→4:1 (0-30 min) at flow of 1 ml/min detected at 254 nm. Peak assignment was made according to [START_REF] Bauer | TLC and HPLC Analysis of Alkamides in Echinacea Drugs[END_REF].

Statistical analysis

Statistical analysis was made by the STATISTICA software (Tulsa, USA). Data were presented as means ± the standard error of the mean (SEM). Significance level was set at p< 0.05. Behavioral data were analyzed by Kruskall-Wallis ANOVA. Mann-Whitney post-hoc comparisons were also run where appropriate.

Results

Screening experiments

Extract No I significantly increased open arm exploration with marginal effects on locomotion as shown by closed arm entries (Table 1). However, only the 1.5 and 2 mg/kg doses were effective; neither 1 nor 3 mg/kg decreased anxiety in the elevated plus-maze. In 2). In addition, % open arm entries showed no significant changes.

Behavioral effects of Extract No IV

The effects of extract No IV were investigated in the elevated plus-maze over a wider dose-range, both 30 min and 1h after treatments (Fig. 1, upper panels). Locomotion as shown by closed arm entries were not affected at either time-point (H(7,120)= 5.18; p> 0.5, and H(7,120)= 7.01; p> 0.4, respectively). The duration of open arm entries increased at both time points (30 min: H(7,120)= 22.96; p< 0.01); 1h: H(7,120)= 19.65; p< 0.01). Open arm choice was affected significantly after 30 min (H(7,120)= 23.70; p< 0.01) but not after 1h (H(7,120)= 10.79; p= 0.14). Post-hoc comparisons showed that the effective dose-range was 3-6 mg/kg after 30 min and 4-8 mg/kg after 1h.

In the social interaction test, resting, exploration and agonistic interactions showed nonsignificant changes (H(3,80) values were 1.59, 3.79, and 0.42; p values were larger than 0.3 at least) (Fig. 1. lower left-hand panel). Social interactions were increased by both the 3 and 4 mg/kg dose (H(3,80)= 14.72, p< 0.001).

In the shock-induced social avoidance model, the extract abolished social avoidance at 3 and 4 mg/kg (H(6, 80)= 20.11; p< 0.005) (Fig. 1. lower middle panel). Locomotion was not affected by the extract within the 2-16 mg/kg dose range (H(4,79)= 1.4; p> 0.8) (Fig. 1. lower left-hand panel). were not devoid of locomotor effects (30 min: H(9,132)= 33.13; p< 0.0001; 1h: H(4,60)= 9.83; p< 0.04). Post-hoc comparisons showed that 30 min after treatments, chlordiazepoxide increased locomotion at 2 and 3 mg/kg, and decreased locomotion above 8 mg/kg. The dose range within which chlordiazepoxide decreased anxiety without affecting locomotion was 4-6 mg/kg at 30 min, and 4 mg/kg at 1h. Chlordiazepoxide significantly increased social interactions in the social interaction test (H(4,72)= 13.39; p< 0.01) (Fig. 2, lower left hand panel). No locomotion-suppressing effects were noticed in this test, as neither resting, nor exploration were affected significantly (H(4,72)= 8.89; p< 0.07 and H(4,72)= 3.24; p> 0.5). We note that the marginally significant difference in resting shown by the Kruskall-Wallis test was due to differences between chlordiazepoxide-treated groups (the lowest resting value was seen at chlordiazepoxide 2 mg/kg). In contrast to extract No. IV, chlordiazepoxide dramatically reduced agonistic interactions (H(4,72)= 29.60; p< 0.0001). In the shock-induced social avoidance test, 0.5 and 1 mg/kg did, whereas 2.5 and 5 mg/kg did not abolish social avoidance (H(5, 42)= 31.89; p< 0.0001) (Fig. 2. lower right-hand panel). The failure of higher doses to abolish social avoidance was likely due to sedation, as opponent entries were reduced from 5.14±0.70 at 1 mg/kg chlordiazepoxide to 2.29±0.57 and 1.14±0.55 at 2.5 mg/kg and 5 mg/kg chlordiazepoxide, respectively. Conversely, unshocked controls showed 5.57±0.61 entries.

The effects of chlordiazepoxide

HPLC measurements

The results of HPLC measurements were summarized in Fig. 3 these compounds and, more importantly their fingerprint showed considerable differences in these extracts.

Discussion

Out of the five Echinacea extracts studied, three affected anxiety-like behavior. Two of these, however, had a very narrow dose range, encompassing no more than 0.5 mg/kg.

Neither lower nor higher doses proved effective. There was only one extract that robustly decreased anxiety in three different tests, with an effective dose-range that was comparable with that of chlordiazepoxide. Locomotion was not affected by this extract at doses that were 5 times larger than the minimally effective anxiolytic dose. Chlordiazepoxide robustly decreased anxiety-like behavior but also suppressed locomotion.

The anxiolytic effects of chlordiazepoxide were consistent with those reported earlier in the same tests [START_REF] File | Can social interaction be used to measure anxiety?[END_REF][START_REF] Leveleki | Pharmacological evaluation of the stress-induced social avoidance model of anxiety[END_REF][START_REF] Patel | Pharmacological properties of tracazolate: a new nonbenzodiazepine anxiolytic agent[END_REF]Pellow et al., 1982;[START_REF] Treit | Conditioned defensive burying: a new paradigm for the study of anxiolytic agents[END_REF]. Locomotor effects were also similar to those reported earlier; low doses (e.g. 2-3 mg/kg) increased, whereas larger doses (e.g. 5-10 mg/kg) suppressed locomotion [START_REF] Davies | A biphasic effect of chlordiazepoxide on animal locomotor activity[END_REF][START_REF] File | The effects of triazolobenzodiazepines in two animal tests of anxiety and in the holeboard[END_REF][START_REF] Fernandes | Dizocilpine does not prevent the development of tolerance to the anxiolytic effects of diazepam in rats[END_REF][START_REF] Martin | Effects of chlordiazepoxide and imipramine on maze patrolling within two different maze configurations by psychogenetically selected lines of rats[END_REF]McElroy et al., 1982). Also consistent with earlier findings, locomotor stimulation that was seen at 30 min disappeared when effects were tested 1h after injections [START_REF] Davies | A biphasic effect of chlordiazepoxide on animal locomotor activity[END_REF].

To our knowledge, this is the first study showing that Echinacea preparations posses an anxiolytic potential. Unfortunately, however, this potential is not common, as only three out of five preparations showed any anxiolytic effect. In addition, the effective dose range was very narrow (0.5 mg/kg) in the case of two effective extracts. Noteworthy, very narrow dose ranges are irrelevant from a therapeutic perspective as such data are difficult to extrapolate to effective doses in humans. In addition, a very narrow dose-range involves the establishment of precise weight-dependent dosage regimens, which appears unrealistic in a clinical setting. Extract No. 4, however, decreased anxiety at a low dose and over a wide, bell-shaped doseresponse curve that was comparable with that of chlordiazepoxide. Such bell-shaped doseresponse curves are commonly seen with herbal extracts [START_REF] Butterweck | Effects of the total extract and fractions of Hypericum perforatum in animal assays for antidepressant activity[END_REF].

Moreover, this phenomenon -also called hormesis-appears to be a general feature of drug effects [START_REF] Calabrese | Hormesis and medicine[END_REF]Baldwin, 2001, Calabrese, 2008).

Discrepant findings with different extracts are likely explained by the fact that while the main constituents of various Echinacea species are essentially similar, the absolute amounts and the quantitative relationships between different constituents are subject to major variation [START_REF] Kapteyn | Genetic relationships and diversity of commercially relevant Echinacea species[END_REF][START_REF] Pellati | Variability in the composition of anti-oxidant compounds in Echinacea species by HPLC[END_REF][START_REF] Percival | Use of Echinacea in medicine[END_REF][START_REF] Perry | Echinacea standardization: analytical methods for phenolic compounds and typical levels in medicinal species[END_REF][START_REF] Wu | Metabolic profiling of echinacea genotypes and a test of alternative taxonomic treatments[END_REF].

Noteworthy, the immunostimulant effect of Echinacea preparations also show extreme variations [START_REF] Tamta | Variability in in vitro macrophage activation by commercially diverse bulk echinacea plant material is predominantly due to bacterial lipoproteins and lipopolysaccharides[END_REF]. We hypothesized that Echinacea preparations affect anxiety-related behaviors mainly due to their alkamide content (see Introduction). This hypothesis was partly supported by HPLC findings, as the extracts that contained the lowest amounts of alkamides were behaviorally inactive. Efficacy, however, was not directly related to alkamide content. Extract No 5 contained high amounts of alkamides but had modest behavioral effects, while Extract No 4 strongly decreased anxiety despite its relatively lower alkamide content. One can hypothesize that behavioral effects depend partly on the total amount, partly on the fingerprint of the different alkamides. As such, behavioral effects may develop in conjunction with the additive/synergistic and possibly antagonistic effects of various alkamides. The involvement of other components cannot be ruled out either. Further research is required to elucidate the compositions that differentiate efficient and inefficient preparations.

The perceived or real risks of conventional drug treatments -as well as personal beliefs about healthy lifestyles-lead to a strong demand for alternative therapies among both patients and medical practitioners [START_REF] Astin | Why patients use alternative medicine: results of a national study[END_REF][START_REF] Barrett | Themes of holism, empowerment, access, and legitimacy define complementary, alternative, and integrative medicine in relation to conventional biomedicine[END_REF][START_REF] Ben-Arye | Attitudes toward integration of complementary and alternative medicine in primary care: perspectives of patients, physicians and complementary practitioners[END_REF] [START_REF] Calabrese | Hormesis and medicine[END_REF][START_REF] Dilhuydy | Patients' attraction to complementary and alternative medicine (CAM): a reality which physicians can neither ignore nor deny[END_REF]. Such alternative therapies would be welcome provided that the treatment is safe and its efficacy is proven. Among herbs, anxiolytic effects are not unique to Echinacea. Effective doses, however, are rather high in most cases (Albizzia julibrissin: 100-200 mg/kg in the rat plus-maze, [START_REF] Kim | Anxiolytic-like effects of extracts from Albizzia julibrissin bark in the elevated plusmaze in rats[END_REF]; Centella asiatica: 500 mg/kg in the rat plus-maze, [START_REF] Wijeweera | Evaluation of anxiolytic properties of Gotukola (Centella asiatica) extracts and asiaticoside in rat behavioral models[END_REF]; Eschsholzia californica: 25 mg/kg in the mouse light/dark test, [START_REF] Rolland | Behavioural effects of the American traditional plant Eschscholzia californica: sedative and anxiolytic properties[END_REF]; Hypericum perforatum: 100-200 mg/kg in the mouse T-maze, [START_REF] Flausino | Effects of acute and chronic treatment with Hypericum perforatum L. (LI 160) on different anxiety-related responses in rats[END_REF]; Passiflora species: 300-800 mg/kg in the rats plus-maze, [START_REF] Reginatto | Evaluation of anxiolytic activity of spray dried powders of two South Brazilian Passiflora species[END_REF]; Valeriana officinalis: above 100 mg/kg, various tests, [START_REF] Oliva | Neuropharmacological profile of hydroalcohol extract of Valeriana edulis ssp. procera roots in mice[END_REF]. In other cases, the effective dose-range was as narrow as with our Extracts No. 1 and 5 [START_REF] Hasenohrl | Dissociation between anxiolytic and hypomnestic effects for combined extracts of zingiber officinale and ginkgo biloba, as opposed to diazepam[END_REF]. More promising effects were obtained with kava kava (Piper mysticum) that proved to be clinically effective [START_REF] Pittler | Kava extract for treating anxiety[END_REF]. Later research, however, revealed that this plant has major side effects [START_REF] Christl | Toxic hepatitis after consumption of traditional kava preparation[END_REF]Teschke et al., 2008).

Evidence accumulated over many decades demonstrates that Echinacea preparations have an excellent safety profile [START_REF] Barnes | Echinacea species (Echinacea angustifolia (DC.) Hell., Echinacea pallida (Nutt.) Nutt.,Echinacea purpurea (L.) Moench): a review of their chemistry, pharmacology and clinical properties[END_REF][START_REF] Birt | Echinacea in infection[END_REF][START_REF] Blumenthal | The complete German Commission E monographs, Therapeutic guide to herbal medicines[END_REF][START_REF] Borchers | Inflammation and Native American medicine: the role of botanicals[END_REF][START_REF] Izzo | Interactions between herbal medicines and prescribed drugs: a systematic review[END_REF][START_REF] Tesch | 188: S44-S55. survey and critical analysis of 26 suspected cases[END_REF]. In addition, the doses that showed anxiolytic effects in the present study (3-7 mg/kg) were about one order of magnitude lower than those that were efficient in laboratory models of traditional indications (30-130 mg/kg; [START_REF] Abouelella | Phytotherapeutic effects of Echinacea purpurea in gamma-irradiated mice[END_REF][START_REF] Zhai | Enhancement of innate and adaptive immune functions by multiple Echinacea species[END_REF]. This comparison suggests that human anxiolytic doses would be similarly low, which further decreases the risks associated with the potential use of Echinacea preparations for the treatment of anxiety. Taken together, these considerations suggest that from the point of view of safety, Echinacea preparations are excellent candidates for the alternative treatment of anxiety. On the other hand, the remarkable anxiolytic effects demonstrated here suggest that certain Echinacea preparations are excellent alternative anxiolytics from the point of view of efficacy as well.

  administration are too low to effectively modulate the mechanisms involved in anxiety control. For example, the Ki values of CB1 binding and the brain concentrations of alkamydes exclude robust effects of orally administered alkamydes on CB1

  group, respectively. Finally, locomotor effects were studied in the open-field test (Experiment 10). The doses tested were 2-16 mg/kg; sample size was 15-16 per group.

  extract (Euromed SA, Millet del Valles, Spain; Batch No.

  sub-areas by concentric and radial lines. Locomotor activity was shown by the number of line crossings.

  addition, the time spent on the open arms was significantly increased, but open arm choice (% open arm entries) showed non-significant variation only.Extracts No II and III failed to affect behavior (Table2). Extract No IV appeared to dose-dependently increase open arm exploration (Table2). The effect was significant at the highest dose tested. Closed arm entries were not changed by the treatments. Extract No V of open arm exploration at 1 mg/kg only; neither 0.5 nor 1.5 mg/kg were effective (Table

  As expected, chlordiazepoxide significantly decreased anxiety-like behavior in the elevated plus-maze both 30 min and 1h after treatments (% open arm entries 30 min: H(9,132) = 29.27; p< 0.005; % open arm entries 1h: H(4,60) = 15.48; p< 0.005; % time in open arm 30 min: H(9,132) = H(9,132) = 34.38; p< 0.0001; % time in open arm 1h: H(4,60) = 19.63; p< 0.001) (Fig. 2, upper panels). However, the anxiolytic effects of chlordiazepoxide

  . Two of the extracts (No. 2 and No. 3), contained very low amounts of alkamides (Fig. 3 upper right hand panel). Alkamides were not lacking in these extracts (see the insert of Fig. 3 upper right hand panel), but their absorption curves became almost flat when the scale of the absorption curve was set such to accommodate the high levels seen in other extracts. Alkamide contents were considerably higher in Extracts No 1, 4, and 5. The level of

Fig. 1 .

 1 Fig. 1. The effects of extract No 4 on anxiety-like behaviors and locomotion. E-IV, the

Fig. 2 .

 2 Fig. 2. The effects of chlordiazepoxide in three anxiety tests. CDP, chlordiazepoxide; *, significantly different from control in post-hoc comparisons (p< 0.05 at least); + , marginally

Fig. 3 .

 3 Fig. 3. HPLC chromatograms of the 5 extracts tested. The insert (upper right hand

  at 22±2°C and 60±10%, respectively. A light/dark cycle of 12 h was ensured with lights on at 0700 h. All rats were housed in 1354G Eurostandard Type 4 cages (59.5×38×22 cm) in groups of four. Acclimatization to housing conditions lasted at least 1 week. All subjects were experimentally naive and used in only one experiment each (with no drug history prior to the experiment).Experiments were carried out in accordance with the European Communities Council Directive of 24 November 1986 (86/609/EEC) and were reviewed and approved by the Animal Welfare Committee of the Institute of Experimental Medicine.

	humidity were kept
	F o r
	P
	e
	e r
	R
	e
	v i e
	w
	Temperature and relative
	5

Table 1 .

 1 The effects of extract No I in the elevated plus-maze.

		Closed entries	% open entries	% time in open arm
	Group	±SEM	±SEM	±SEM
	vehicle	7,40 ±0,61	28,18 ±2,04	9,53 ±1,44
	E I 0.05 mg/kg	7,30 ±0,63	32,59 ±3,26	12,17 ±1,78
	E I 1 mg/kg	8,80 ±1,16	27,17 ±2,21	12,42 ±2,33
	E I 1.5 mg/kg	8,67 ±0,53	37,62 ±2,08	21,41 * ±4,30
	E I 2 mg/kg	8,30 ±0,91	33,33 ±3,14	17,09 * ±1,99
	E I 3 mg/kg	10,80 ±0,80 +	30,20 ±4,36	12,23 ±3,32
	E I 6 mg/kg	9,30 ±0,68	27,43 ±1,83	10,91 ±1,58
	H(6,80)	12,83	10,62	16,10
	p	0,05	0,1	0,01
	E

I , extract No. I; H, Kruskall-Wallis coefficient; Post hoc comparisons:*, significantly different from control (bolded); + , marginal difference from control (italicized).

Table 2 .

 2 The effect of Extracts No II-V in the elevated plus-maze. , extract No. I-V; H, Kruskall-Wallis coefficient; Post hoc comparisons:*, significantly different from control (bolded); + , marginal difference from control (italicized).

	Treatment	Closed entries ±SEM	% open entries ±SEM	%time in open arm ±SEM
	Control	6.72 ±0.91	21.46 ±4.15	6.07 ±1.36
	E II 1mg/kg	7.75 ±1.28	19.03 ±4.95	6.53 ±2.67
	E II 3mg/kg	6.80 ±1.25	18.75 ±7.89	3.08 ±1.01
	E II 4mg/kg	5.90 ±1.03	19.19 ±5.56	5.43 ±2.15
	E II 5mg/kg	7.00 ±1.02	22.76 ±5.49	8.92 ±3.18
	H(4,56)	1.82	1.23	2.11
	p	0.8	0.9	0.7
	control	7.50 ±0.78	24.69 ±2.67	7.58 ±1.29
	E III 1 mg/kg	8.00 ±0.89	29.88 ±4.67	13.38 ±3.12
	E III 2 mg/kg	5.92 ±1.43	26.34 ±8.52	4.81 ±1.25
	E III 3 mg/kg	8.20 ±0.63	23.19 ±3.73	10.08 ±2.65
	E III 4 mg/kg	7.89 ±1.03	23.58 ±5.09	8.26 ±3.38
	H(4,55)	2.10	3.55	6.26
	p	0.7	0.5	0.2
	control	7.33 ±0.71	11.24 ±3.35	2.18 ±0.57
	E IV 1 mg/kg	7.92 ±0.92	8.46 ±3.57	2.37 ±1.30
	E IV 2 mg/kg	6.50 ±1.10	10.00 ±3.22	2.67 ±0.84
	E IV 3 mg/kg	7.92 ±0.92	18.54 ±4.38	+ ±2.08 6.93
	E IV 4 mg/kg	7.75 ±0.73	23.93 * ±4.12	10.43 * ±3.49
	H(4, 60)	2.36	10.32	10.54
	p<	0.7	0.04	0.03
	Control	8,94 ±0,82	32,85 ±3,93	18,69 ±3,43
	E V 0.5 mg/kg	8,00 ±0,85	34,94 ±4,84	18,64 ±4,43
	E V 1 mg/kg	9,00 ±0,87	41,97 ±4,70	35,18 * ±5,72
	E V 1.5 mg/kg	9,56 ±0,81	40,47 ±2,66	27,66 ±3,46
	E V 2 mg/kg	8,63 ±1,04	37,63 ±3,25	25,81 ±3,90
	H(4,80)	1,65	3,16	9,42
	p	0,80	0,50	0,05
	E I-V

http://mc.manuscriptcentral.com/ptr Phytotherapy Research

http://mc.manuscriptcentral.com/ptr

Acknowledgements

This work was supported by the NKTH Jedlik Anyos grant to HJ and FTF. FTF and HJ are owners of Hungarian patent application No P0600489, PCT patent application No PCT/HU2007/000052, European patent application No EP 07733869.7, US patent application No. 12/304 558 and Hong Kong patent application 09109349.0 concerning the use of Echinacea preparations for the treatment of anxiety. The authors thank Cheryl Myers for her help in editing this manuscript.


Rafael Pastor
email: rafael.pastor@upc.edu

LB-ALBP: The Lexicographic Bottleneck Assembly Line Balancing Problem †

Keywords:

The classic assembly line balancing problem (ALBP) basically consists of assigning a set of tasks to a group of workstations while maintaining the tasks' precedence relations. When the objective is to minimize the number of workstations m for a given cycle time CT , the problem is referred to as ALBP-1; if the objective is to minimize CT given m , then the problem is called ALBP-2. The only objective in ALBP-2 is to minimize CT , i.e., the workload of the most heavily loaded workstation (the bottleneck). However, considering the second-biggest, third-biggest, etc. workloads, can be important. Distributing a workload among six workstations as 10, 10, 10, 4, 3, 3, is not the same as distributing it as 10, 6, 6, 6, 6, 6. The CT value is the same, but the second distribution is beyond question more reliable and balanced. In this paper, we present and formalize a new assembly line balancing problem: the Lexicographic Bottleneck Assembly Line Balancing Problem (LB-ALBP). The LB-ALBP hierarchically minimizes the workload of the most heavily loaded workstation ( CT ), followed by the workload of the second most heavily loaded workstation, followed by the workload of the third most heavily loaded workstation, and so on. We present two mixed-integer linear programming (MILP) models designed to solve the LB-ALBP optimally, together with three heuristic procedures based on these MILPs.

Introduction

Assembly lines are components of many production systems, such as those used in the automotive and household appliance industries. The problem of designing and balancing assembly lines is very difficult to solve due to its combinatorial nature -it is NP-hard (see, e.g., Wee and Magazine, 1982)-and the large number of tasks and constraints that occur in real-life situations. The classic assembly line balancing problem (ALBP) basically consists of assigning a set of tasks (each of them characterized by its processing time) to an ordered sequence of workstations, in such a way that the precedence constraints between the tasks are maintained and a given efficiency measure is optimized. Regarding the conventional terminology (e.g., [START_REF] Baybars | A survey of exact algorithms for the simple assembly line balancing problem[END_REF], when the objective is to minimize the number of 2 workstations for a given upper bound on the cycle time, the problem is known as ALBP-1; if the objective is to minimize the cycle time given a number of workstations, then the problem is called ALBP-2.

The problem of designing and balancing assembly lines has been extensively examined in the literature. A number of synthesis studies has been published, including [START_REF] Baybars | A survey of exact algorithms for the simple assembly line balancing problem[END_REF], [START_REF] Ghosh | A comprehensive literature review and analysis of the design, balancing and scheduling of assembly systems[END_REF], [START_REF] Erel | A survey of the assembly line balancing procedures[END_REF], [START_REF] Scholl | Balancing and sequencing of assembly lines[END_REF], Rekiek et al. (2002b), [START_REF] Becker | A survey on problems and methods in generalized assembly line balancing[END_REF], [START_REF] Scholl | State-of-the-art exact and heuristic solution procedures for simple assembly line balancing[END_REF] and [START_REF] Boysen | A classification of assembly line balancing problems[END_REF][START_REF] Boysen | Assembly line balancing: Which model to use when?[END_REF]; however, most papers focus on the simple case. This problem has been approached using heuristic procedures -e.g., Talbot et al. (1986) and [START_REF] Ponnambalam | A comparative evaluation of assembly line balancing heuristics[END_REF]-, exact procedures based on binary linear programming -e.g., White (1961) and [START_REF] Pastor | An improved mathematical program to solve the simple assembly line balancing problem[END_REF]-, integer linear programming -e.g., Talbot and Patterson (1984)-, dynamic programming -e.g., [START_REF] Kao | On dynamic programming methods for assembly line balancing[END_REF]-, and branch and bound -e.g., FABLE by [START_REF] Johnson | Optimally balancing large assembly lines with Fable[END_REF], EUREKA by [START_REF] Hoffman | EUREKA: a hybrid system for assembly line balancing[END_REF] and SALOME by [START_REF] Scholl | SALOME: a bidirectional branch and bound procedure for assembly line balancing[END_REF]-. A significant variety of complex cases has been examined, including problems that consider lines with parallel workstations or parallel tasks; mixed or multi-models; multiple products; U-shaped, two-sided, buffered or parallel lines; incompatibility between tasks; stochastic processing times; and equipment selection -e.g., [START_REF] Park | A heuristic for an assembly line balancing problem with incompatibility, range, and partial precedence constraints[END_REF], [START_REF] Amen | Heuristic methods for cost-oriented assembly line balancing: A comparison on solution quality and computing time[END_REF][START_REF] Amen | Cost-oriented assembly line balancing: Model formulations, solution difficulty, upper and lower bounds[END_REF], [START_REF] Ağpak | Assembly line balancing: Two resource constrained cases[END_REF], [START_REF] Ding | Comparing two weighted approaches for sequencing mixed-model assembly lines with multiple objectives[END_REF], [START_REF] Gamberini | A new multi-objective heuristic algorithm for solving the stochastic assembly line re-balancing problem[END_REF], [START_REF] Gökçen | Balancing of parallel assembly lines[END_REF], [START_REF] Andrés | Balancing and scheduling tasks in assembly lines with sequence-dependent setup times[END_REF], [START_REF] Capacho | ASALBP: the Alternative Subgraphs Assembly Line Balancing Problem[END_REF], [START_REF] Corominas | Balancing assembly line with skilled and unskilled workers[END_REF], [START_REF] Capacho | An evaluation of constructive heuristic methods for solving the alternative subgraphs assembly line balancing problem[END_REF], [START_REF] Corominas | A note on "A comparative evaluation of assembly line balancing heuristics[END_REF], [START_REF] Cortés | Optimising and simulating the assembly line balancing problem in a motorcycle manufacturing company: a case study[END_REF], [START_REF] Martino | Heuristic procedures for solving the general assembly line balancing problem with setups[END_REF] and [START_REF] Pastor | Corrigendum to "Balancing and scheduling tasks in assembly lines with sequence-dependent setup[END_REF]-. As a result, generalized problems are becoming a widespread subject.

During the last years, several artificial intelligence techniques have been used, including genetic algorithms, as employed in [START_REF] Rubinovitz | Genetic algorithm for assembly line balancing[END_REF]; simulated annealing, as applied in Suresh and Sahu (1994); tabu search, as used in [START_REF] Pastor | Tabu search algorithms for an industrial multi-product and multi-objective assembly line balancing problem, with reduction of the tasks dispersion[END_REF]; ant colony, as employed in [START_REF] Baykasoglu | An ant colony based optimization algorithm for solving assembly line balancing problems[END_REF]; or the knowledge-based approach developed in [START_REF] Malakooti | A knowledge-based system for solving multi-objective assembly line balancing problems[END_REF].

The ALBP-2 is a problem with a min-max objective, since it tries to minimize the workload of the most heavily loaded workstation (the bottleneck). The optimal solution of problems with this type of objective guarantees that the maximum value is as small as possible; however, the remaining values are not considered, even though they may also be important. In ALBPs, it is important to consider the second-biggest, thirdbiggest, etc. workloads: the reliability of the line is improved; the workload is prone to be uniformly distributed among all of the workstations; and, moreover, as it is exposed in [START_REF] Boysen | A classification of assembly line balancing problems[END_REF], the quality defects caused by stations with disproportionately large station times are avoided.

The main objective of this paper is to present a new assembly line balancing problem: the Lexicographic Bottleneck Assembly Line Balancing Problem (LB-ALBP). The LB-ALBP hierarchically minimizes the workload of the most heavily loaded workstation, followed by the workload of the second most heavily loaded workstation, followed by the workload of the third most heavily loaded workstation, and so on. The LB-ALBP is presented and formalized, and two mixed-integer linear programming models are designed to solve it optimally, together with three heuristic procedures based on these mathematical programs. The remainder of the paper is organized as follows. Section 2 describes and characterizes the LB-ALBP. Section 3 presents two mixed-integer linear programming (MILP) models designed to solve the problem optimally. Section 4 describes three heuristic procedures based on these MILP models. Finally, Section 5 offers conclusions and ideas for further research.

The Lexicographic Bottleneck Assembly Line Balancing Problem (LB-ALBP)

The objective of the type 2 assembly line balancing problem (ALBP-2) is to minimize the workload of the most heavily loaded workstation (the bottleneck) and, therefore, it is a problem with a min-max objective. The scientific literature includes several problems with min-max objectives: location, production according to an ideal value, etc. The optimal solution of a problem with this kind of objective guarantees that the maximum value is as small as possible. However, the remaining values are not considered, and they can also be important because, even though they do not exceed the maximum value (the bottleneck), their distribution can be highly irregular and therefore inappropriate.

Indeed, in the ALBP, it is important to consider the second-largest workload, the thirdlargest workload, etc., because this allows us to reduce the criticalness of the workstations. That is, the smaller the difference between the processing time (workload) of a station and the cycle time, the more critical the workstation. By reducing criticalness, the reliability of the line is improved. Figure 1a shows that distributing a workload among six workstations as 10, 10, 10, 4, 3, 3 is not the same as distributing it as 10, 6, 6, 6, 6, 6. The cycle time value is the same, but the second distribution is beyond question more reliable than the first one because it reduces the criticalness of the workstations. It is normally assumed that the processing time of the tasks is known and constant; however, in industrial environments, these times often change from one cycle to the next one, especially in manual lines. Stochastic processing times increase the probability that the cycle time will be greater than a given value. For example, let ω be the probability that a workstation with a workload equal to the cycle time CT will be greater than CT . For the first workload distribution shown in Figure 1a, the probability of one workstation having a workload greater than CT is equal to

2 3 3 3 - + ω ω ω ( ) ( ) 3 1 1 --ω .
On the other hand, for the second distribution shown in Figure 1a, the probability of one workstation having a workload greater than CT is equal to just ω (only fully loaded stations have been considered to calculate the probability of station overloads, since the probability that a non fully loaded station has a workload greater than CT is very inferior to the probability that a fully loaded station has a workload greater than CT ).

Insert Figure 1

Another aspect to be considered could be the distribution of a line's most critical workstations. Figure 1b shows that a distribution of 10, 4, 10, 3, 10, 3 has the same criticalness as a distribution of 10, 10, 10, 4, 3, 3. However, according to the aforementioned definition of criticalness, the first distribution seems preferable to the We define and formalize a new assembly line balancing problem, referred to by the authors as the Lexicographic Bottleneck Assembly Line Balancing Problem (LB-ALBP). The LB-ALBP minimizes the workload of the most heavily loaded workstation (cycle time) and then goes on minimizing the workload of the second most heavily loaded workstation, followed by the workload of the third most heavily loaded workstation, and so on. It is therefore a multi-objective optimization problem with a hierarchical structure [START_REF] Krajewski | Disaggregation in manufacturing and service organizations: Survey of problems and research[END_REF], [START_REF] Starr | Perspectives on disaggregation[END_REF] and [START_REF] Cortés | Genetic algorithm for planning cable telecommunication networks[END_REF][START_REF] Cortés | Andalucía assesses the investment needed to deploy a fiber-optic network[END_REF]). In general, the term "lexicographic optimization" is applied when different objectives must be optimized, but there is also literature that applies this term when the same objective is being optimized (e.g. [START_REF] Pentico | Assignment problems: A golden anniversary survey[END_REF]. For more details about the lexicographic bottleneck objective, see, for example, [START_REF] Burkard | Lexicographic bottleneck problems[END_REF] and [START_REF] Sokkalingam | Lexicographic bottleneck combinatorial problems[END_REF].

Several papers have already dealt with multi-objective ALBPs, but the approach proposed here is different. For example, [START_REF] Miyazaki | An optimal solution of the assembly line balancing problem with the balancing index as a primary objective function[END_REF] optimally solve the line balancing problem in a way that minimizes the number of workstations and the cycle time. [START_REF] Malakooti | A knowledge-based system for solving multi-objective assembly line balancing problems[END_REF] use a multi-criteria decision-aid method for ALBPs where the objectives are the number of stations, the cycle time, the buffer size and the total cost of the operations. [START_REF] Kim | Genetic algorithms for the assembly line balancing with various objectives[END_REF] present genetic algorithms to solve ALBPs with various objectives: minimizing the number of workstations, minimizing cycle time, maximizing workload smoothness and maximizing work-relatedness. Rekiek et al. (2002a) also take multiple objectives into account: total cost, imbalance, reliability and congestion. In our comprehensive review of the literature on ALBPs, this type of problem has not previously been addressed.

On the other hand, the lexicographic bottleneck objective also tends to homogeneously distribute the workload among all workstations, which avoids large differences in the workers' workloads and, as it is exposed in [START_REF] Boysen | A classification of assembly line balancing problems[END_REF], prevents quality defects caused by stations with disproportionately large station times. Other objective functions also tend to homogenize the workload distribution, such as: the "smoothness index" [START_REF] Moodie | A heuristic method of assembly line balancing for assumptions of constant or variable work element times[END_REF], ( )

2 max 1 = = - ∑ m j j SI ts
ts , where m is the number of workstations, max ts is the maximum station time and j ts is the time of workstation j ; the "workload range", max min ts ts , where max ts and min ts are the maximum and minimum workstation times, respectively; and the imposition of a time interval on the workload at any workstation [START_REF] Pastor | Assembly line balancing with incompatibilities and bounded workstation loads[END_REF],

,   - +   ts ts σ σ
, where ts is the average workload of the stations and σ is the allowed tolerance. Note that the lexicographic bottleneck objective is different -as it has been exposed, for assignment problems, by Pentico (2007)-.

The following example proves that the optimal solution according to the lexicographic bottleneck objective, LB , may be different from the optimal solution according to, for example, the "smoothness index" objective, SI . Figure 2 shows the precedence graph for an instance with 10 tasks, with the processing time of each task over the vertex that represents the task. Table 1 shows the two optimal solutions with five workstations. For each optimal solution, the following information is given: the tasks assigned to each workstation (and, in parentheses, the total workload of the station),

x Sta , and the value of the solution according to the objectives LB and SI .

Insert Figure 2

Insert Table 1 3

. Mathematical programming models of the LB-ALBP

The LB-ALBP is a multi-objective optimization problem in which the order of the objectives is the main point and there is no interest in a continuous trade-off among the functions. As [START_REF] Pentico | Assignment problems: A golden anniversary survey[END_REF] shows, there are two basic methods to incorporate multiple criteria in decision models: (1) by combining them in a single criterion, and (2) by considering them separately and sequentially. To solve the LB-ALBP optimally, we have designed two mathematical programming models, one for each method: a) Combining multiple criteria in one criterion: The Global Hierarchical Model (GHM), which solves the problem in a way that minimizes a weighted sum of functions, with enough different weights to preserve the hierarchy of the proposed objectives.

b) Considering multiple criteria sequentially: The Successive Hierarchical Model (SHM), which carries out a preemptive goal programming. This method is an extension of linear programming that considers multiple objectives separately and sequentially. It observes and sequentially minimizes the objectives once the optimal values of the highest-priority objectives have been obtained.

Specifically, the ALBP that is modeled and solved as an LB-ALBP is the simplest case (the Simple Assembly Line Balancing Problem, SALBP), characterized as follows [START_REF] Baybars | A survey of exact algorithms for the simple assembly line balancing problem[END_REF]: serial (straight) assembly lines processing a single model of a single product are considered; all input parameters are known with certainty; the task processing times are independent of the workstation at which they are performed and of the preceding and following tasks; all workstations are equipped and manned to process any of the tasks, and any task can be processed at any workstation; a task cannot be split among two or more workstations; tasks cannot be processed in arbitrary sequences due to technological precedence requirements; all tasks must be processed; and no assignment restrictions apart from precedence constraints are considered. An initial preprocess stage is carried out: an upper bound on the cycle time is calculated and it is used to calculate the range of workstations to which any task i can be assigned.

Preprocess

The upper bound on the cycle time, CT , is calculated using the [START_REF] Helgeson | Assembly line balancing using Ranked Positional Weight Techniques[END_REF] heuristic to solve the SALBP-1 iteratively. The iterative process produces one-unit increases above a lower bound on the cycle time until a solution is obtained for the specific number of workstations. It starts with the maximum among, on the one hand, the duration of the longest task and, on the other hand, the minimum integer number equal to or greater than the value of the quotient of the total time of the tasks and the total number of workstations (see, e.g., [START_REF] Scholl | Balancing and sequencing of assembly lines[END_REF].

Once CT is evaluated, we use the well-known concept of earliest and latest station ( i E and i L , respectively) to which a task i can be assigned: before assigning a task we must assign the total time of the preceding tasks and, likewise, after assigning a task we need to assign the total time of the tasks that follow it. As a result, the range of workstations [ ]

,
i i E L to which task i can be assigned (see, e.g., [START_REF] Scholl | Balancing and sequencing of assembly lines[END_REF] is obtained.

Global Hierarchical Model (GHM)

The Global Hierarchical Model (GHM) solves the problem by minimizing a weighted sum of functions with enough different weights to preserve the hierarchy of the proposed objectives.

1,..., k m = . 1 k k + >> α α
guaranteeing that the hierarchy of the proposed objectives is preserved.

Variables: { } 0,1 ij x ∈ 1, if

Model:

[ ]

1 = = ⋅ ∑ m k k k MIN z T α (1) 1 i i L ij j E x = = ∑ i ∀ (2) [ ] , i i i ij j i j E L t x S ∀ ∈ ⋅ ≤ ∑ j ∀ (3) 1 1 m jk k y = = ∑ j ∀ (4) 1 1 m jk j y = = ∑ k ∀ (5) 1 1 k j k js s S T M y - = ≤ + ⋅ ∑ ; k j ∀ ∀ (6) p i i p L L ij pj j E j E j x j x = = ⋅ ≤ ⋅ ∑ ∑ ( ) , i p P ∀ ∈ (7) with ( ) ( ) 1 1 min , min , max 0, 1 n n i i i i i M t CT t CT t m CT = =     = - - --⋅         ∑ ∑
The objective function (1) minimizes a weighted sum of the workloads of the workstations; constraint set (2) implies that each task i is assigned to one and only one workstation; constraints (3) calculate the processing time (workload) assigned to each workstation; constraints (4) impose that each workstation is assigned to only one position in the list of workstations (ordered by workload); constraint set (5) imposes that each position of the workstation list, ordered by workload, is assigned to only one workstation; constraints (6) impose that if workstation j is the k -th most heavily loaded workstation, its workload will not be greater than the workload of the first k most heavily loaded workstations; and constraint set (7) imposes the technological precedence conditions.

When m is high, the model requires very high values of the parameters k α ; this situation can negatively affect numerical precision when the model is solved. It is known that the conversion of a multi-objective hierarchical problem in a scalar optimization problem leads to artificial cost functions and to a difficult tuning of the weight that the designer wishes to associate with each criterion (Rekiek et al., 2002a).

Successive Hierarchical Model (SHM)

The Successive Hierarchical Model (SHM) carries out a preemptive goal programming; i.e., it sequentially solves 1 m mixed-integer linear programming (MILP) models by observing and sequentially minimizing the objectives once the optimal values of the highest-priority objectives have been obtained.

Next, we show the first model to be solved, in which the workload of the most heavily loaded workstation, 1 T , is minimized. In this submodel, as in the following ones, constraints (2), ( 3) and ( 7) must be added.

[ ]

1 = MIN z T (8) 1 j S T ≤ j ∀ (9)
(8) minimizes the workload of the most heavily loaded workstation and ( 9) imposes that all workstations have assigned a workload that is not greater than the workload of the most heavily loaded workstation.

The result of this model is 1 T , which is fixed and becomes a datum. The second model to be solved, to minimize the workload of the second most heavily loaded workstation, 2 T , is shown below.

[ ]

2 = MIN z T (10) 1 1 1 m j j y = = ∑ (11) 1 j S T ≤ j ∀ ( 12
) ' 2 1 1 j j S T M y ≤ + ⋅ j ∀ (13) with 1 ' 1 1 1 1 n i i t T M T m = - = - - ∑ (
10) minimizes the workload of the second most heavily loaded workstation; (11) imposes that only one workstation is defined as the most heavily loaded; (12) implies that all workstations have assigned a workload that is not greater than the workload of the most heavily loaded station; and (13) imposes that all the workstations, except the workstation that has assigned the workload 1 T , have a workload smaller than or equal to the workload of the second most heavily loaded station. The result of this model is 2 T . Finally, we show the q -th model to be solved ( ) 3,..., 1 q m = -; i.e., the model to be solved once the workloads of the 1 q most heavily loaded stations, 1 T , …, 1 q T -, have been determined. This model minimizes the workload of the q -th most heavily loaded station, q T . In this case, 1 T ,…, 1 q Tare known parameters and k T is the variable that indicates the workload of the k -th most heavily loaded workstation ( )

F

,..., 1 k q m = -. [ ] = q MIN z T (14) 1 1 m jk j y = = ∑ 1,..., 1 k q = - ( 15
) 1 1 1 q jk k y - = ≤ ∑ j ∀ ( 16
) 2 2 1 1 1 1 q q j k jk q jk k k S T y T y - - - = =   ≤ ⋅ + ⋅ -     ∑ ∑ j ∀ (17) 1 ' 1 q j q k jk k S T M y - = ≤ + ⋅ ∑ j ∀ (18) with ( ) 1 ' 1 1 1 q n i s i s k k t T M T m q - = = - = --- ∑ ∑ (14
) minimizes the workload of the q -th most heavily loaded workstation; (15) imposes that only one station is defined as the k -th most heavily loaded workstation ( ) 1,..., 1 k q = -; (16) implies that a workstation can either be one of the 1 q most heavily loaded stations or not have a defined workload -and, thus, a defined position in the list of workstations (ordered by workload)-; (17) imposes that the workload of any station that is not one of the 1 q most heavily loaded stations may not be greater than 1 q Tand also imposes that the workload of the k -th most heavily loaded station ( )

1,..., 1 k q =
is k T ; and (18) imposes that the workload of a workstation that is not any of the 1 q most heavily loaded stations is smaller than or equal to the workload of the q -th most heavily loaded station. The result of this model is q T .

The value m T is forced when the other values k T ( )

1,..., 1 k m =
are known.

A measurement of solution quality

We have designed a parameter, δ , to quantitatively compare two solutions of an LB-ALBP instance. δ considers, between both solutions, the difference in workload of each pair of workstations according to the list in descending order of workload: ...

- - ∆ ⋅ + ∆ ⋅ + + ∆ ⋅ = ⋅ m m m m best CT β β β δ β
where j ∆ is the positive, null or negative workload difference in the j -th most heavily loaded station between the worst and best solutions which are compared (i.e., j ∆ is the workload, in the j -th most heavily loaded station, that the worst solution makes worse, or improves, with regard to the best one); m is the number of workstations;

best CT is the best cycle time of the two solutions compared; and β is a parameter whose value must guarantee the hierarchy of the objectives. In this paper, β has been set to 100, and we have checked that the hierarchy of the objectives is guaranteed.

For example, let us consider an instance with four workstations and the solutions

⋅ + ⋅ + ⋅ + -⋅ = = ⋅
The parameter δ allows us to make comparisons between solutions and with the optimum solution (if it is available); and the worse a solution is with regard to the reference solution, the larger the value of δ is.

δ also allows us to compare the obtained solutions with a lower bound of the optimum solution. A simple lower bound can be obtained taking into account n (number of tasks), m (number of workstations), i t (processing time of task i ), max t (maximum processing time) and a lower bound on the cycle time min max 1 max ; 20-19-19-19-19 time units, respectively, can be obtained.

n i i CT t t m =     =         ∑ .

Computational experiment

The effectiveness of the two proposed models (GHM and SHM) was evaluated by solving all of the 302 well-known SALBP-2 instances available on Scholl and Klein's homepage for assembly line balancing research (www.assembly-line-balancing.de). The MILP models were solved using the ILOG CPLEX 9.0 optimization software on a 3.00 GHz Pentium IV PC with 1 GB RAM; the relative MIP gap tolerance was set to 0.01. In order to compare the two MILP models designed to solve the LB-ALBP optimally, a huge calculation time would be necessary (the time that the optimization software needs to solve the mathematical models); thus, an artificial limit of 18,000 seconds was used and only the number of optimal solutions was considered.

The values of the parameters k α ( )

1,..., k m =
were defined as follows. Let ND be the number of digits of the value of the upper bound on the cycle time, CT ; let v be the integer part of 2 m ; thus,

( ) ( ) 1 10 ND v k k α ⋅ -- = ( ) 1,..., k m = .
Table 2 shows the results obtained for each model (GHM and SHM): the number of instances with a proved optimal solution ( )

º

Insert Table 2

Table 2 shows that SHM has a better behaviour, since it is able to optimally solve 25 more instances than GHM (57 and 32 instances, respectively). For the 27 instances that are optimally solved by both models, the average computing time ( ) t of GHM is slightly shorter than the average computing time of SHM.

It is noticed that GHM also labels a further 24 instances as optimal (although they are not). These incoherent solutions are due to the numerical precision problems that appear when the values of the artificial parameters k α are fixed. For 3 of these 24 instances, negative workloads are assigned to workstations. In the 21 remaining instances, although the optimization software guarantees the optimal solution, the GHM does not reach the optimum; i.e., the value δ , which is obtained by comparing the GHM solution with the SHM optimal solution, is greater than 0 (the average value of δ is 49.46, and the maximum value is 251.42).

For one instance of the SHM the optimization software guarantees the optimal solution, although this solution is not optimal (although it is feasible). In this case, the value of δ , which is obtained by comparing the SHM solution with the GHM solution, is 0.0033. This difference is due to the allowed relative MIP gap tolerance, since the cycle time in this instance is very high.

MILP-based heuristic procedures for solving the LB-ALBP

As shown above, the best of the two proposed MILP models can optimally solve only 57 of the 302 instances. Therefore, and although formidable progress has been made in recent years in terms of both computational power and computational technology, heuristic procedures must be proposed. Section 4 presents three heuristic procedures based on the two MILP models introduced in Section 3. These heuristics consist of running the mathematical programming models for a limited computing time.

Heuristic derived from the Global Hierarchical Model (H_GHM)

The heuristic derived from the Global Hierarchical Model (H_GHM) consists of running the GHM for 18,000 seconds and preserving the best solution obtained.

Heuristics derived from the Successive Hierarchical Model (Hx_SHM)

The heuristics derived from the Successive Hierarchical Model (Hx_SHM) consist of running SHM for 18,000 seconds and preserving the best solution obtained. In this case, we must specify how this computing time is distributed, since it is a preemptive goal programming method in which 1 m mixed-integer linear programming models are sequentially solved.

The heuristics H1_SHM and H2_SHM were designed according to two ways of distributing the 18,000 seconds among the various submodels to be solved. H1_SHM consists of assigning the available computing time to the submodel to be solved, once the previous submodels have been optimally solved. The first submodel is run with a computing time limit of 18,000 seconds; if any time remains available, the second submodel is run with a time limit equal to the remaining computing time; and so on.

H2_SHM consists of assigning half of the available computing time to the submodel to be solved. The first submodel is run with a computing time limit of 9,000 seconds; next, the second submodel is run for half of the available computing time, which is greater than 4,500 seconds if the first submodel has guaranteed the optimal solution in less than the assigned 9,000 seconds; and so on. The last submodel to be solved is run with all of the remaining time until the 18,000 seconds are spent.

Note that the submodels of the H2_SHM heuristic do not always guarantee optimal solutions. Therefore, when the submodel q is solved, it is possible to find a value j T ( ) < j q that is smaller than the value obtained by solving the submodel j (if this submodel j did not guarantee an optimal solution). This possibility is taken into account, and the values j T are updated when these values improve.

Computational experiment

We evaluated the effectiveness of the proposed heuristic procedures under the same conditions used in Section 3.5. 3 shows, for each heuristic (H_GHM, H1_SHM and H2_SHM), the number of instances ( ) º N Sol in which a feasible solution is obtained.

Insert Table 3

Whereas the heuristics derived from the SHM solve all 302 instances, the H_GHM heuristic solves only 195 instances. The high value of the parameters k α of the H_GHM heuristic may explain the optimization software's difficulty in finding a feasible solution.

Next, we present three analyses of the results. First, the results obtained for the 195 instances that are solved by all three heuristic procedures are briefly analyzed (Section 4.3.1). Then, the results obtained for the 302 instances that are solved by the H1_SHM and H2_SHM heuristics are analyzed (Section 4.3.2). Finally, the results obtained with a procedure for the minimization of the smoothness index are analyzed (Section 4.3.3).

It should be remembered that the worse a solution is with regard to the reference solution, the larger the value of δ is.

Comparison of H_GHM, H1_SHM and H2_SHM for 195 instances

This section briefly analyzes the results obtained for the 195 instances solved by all three heuristic procedures. For each heuristic, Table 4 shows the number of instances for which the heuristic obtains the best solution ( )

Insert Table 4

The H_GHM heuristic has the worst behavior. H_GHM only obtains a feasible solution for 195 of the 302 instances. Of these 195 instances, the best solution is obtained only 57 times. Moreover, when H_GHM does not obtain the best solution, its solution is very far from the best (note the high average value of the parameter δ , 20.24 = δ ). Furthermore, H_GHM obtains the greatest average computing times.

The H2_SHM heuristic gives slightly better results than the H1_SHM heuristic; in any event, these are partial results and an analysis of all 302 instances must be carried out.

Comparison of H1_SHM and H2_SHM for the 302 instances

This section analyzes the results obtained for the 302 instances solved by the heuristic procedures H1_SHM and H2_SHM. For each heuristic, Table 5 shows the number of instances for which the heuristic obtains the best solution ( )

º N Best ; the minimum

Insert Table 5

The H1_SHM heuristic obtains the best solution in 7 more instances than the H2_SHM heuristic. Specifically, in 161 instances, both heuristics obtain the same solution; in 74 instances, H1_SHM obtains the best solution; and in 67 instances, H2_SHM obtains the best solution.

H1_SHM has a better behavior than H2_SHM when the best solution is not obtained.

The 67 solutions obtained with H1_SHM are very close to the 67 better solutions obtained with H2_SHM, as the low average value of the parameter δ ( The average computing time of the H1_SHM heuristic is slightly larger than that of the H2_SHM heuristic (14,736 and 14,243 seconds, respectively).

Comparison with a procedure for the maximization of the smoothness index

As it is exposed, the LB-ALBP is a new problem and the lexicographic bottleneck objective, LB , is different from the objective of minimizing the smoothness index, SI , -as it has been introduced, for assignment problems, by [START_REF] Pentico | Assignment problems: A golden anniversary survey[END_REF]-. We can observe that both objectives are similar; thus we have also solved the 302 instances with a heuristic procedure taken from the literature designed for the maximization of the SI . We have used the "Hoffman precedence matrix" heuristic together with the "trade and transfer phase" of the Moodie and Young method, HPM_T&T, which is one of the heuristics that performs best for the SI criteria [START_REF] Ponnambalam | A comparative evaluation of assembly line balancing heuristics[END_REF].

The results obtained for the 302 instances solved with the heuristic procedures H1_SHM and HPM_T&T are analyzed below. For each heuristic, Table 6 shows the number of instances for which the heuristic obtains the best solution ( ) . Table 7 and 8 show the values of the previous parameters ( º N Best , δ , δ σ , t and t σ ) for the two set of instances, respectively.

Insert Table 7

Insert Table 8 When all instances are considered, the H1_SHM heuristic obtains the best solution for 62 more instances than the HPM_T&T heuristic; but HPM_T&T has a better global behavior than H1_SHM according to the average value of the parameter δ and the average computing time of the H1_SHM is larger than that of the HPM_T&T heuristic. Similar results are obtained when the 66 High-N instances are analyzed. Nevertheless, H1_SHM heuristic has a better behavior than HPM_T&T heuristic (according to the number of instances for which the heuristic obtains the best solution and the average value of the parameter δ ) when the 236 Low/Middle-N instances are analyzed.

Finally, we compare the results obtained with both procedures for the 62 instances that we know their optimal solution (which are obtained in Section 3.5). H1_SHM heuristic obtains the optimal solution for 61 instances, with an average value of the parameter δ equal to 0.00005, whereas HPM_T&T heuristic only obtains the optimal solution for 21 instances, with an average value of the parameter δ equal to 0.35.

Conclusions and future research

In the type 2 assembly line balancing problem (ALBP-2), the objective is to minimize the cycle time given a number of workstations; i.e., to minimize the workload of the most heavily loaded workstation (the bottleneck). However, considering the secondbiggest workload, the third-biggest workload, etc., can allow us to obtain a more reliable, better-balanced solution.

The main objective of this paper is to present, formalize and solve a new assembly line balancing problem: the Lexicographic Bottleneck Assembly Line Balancing Problem (LB-ALBP). The LB-ALBP hierarchically minimizes the workload of the most heavily loaded workstation, followed by the workloads of the second and third most heavily loaded workstations, and so on. Two mixed-integer linear programming (MILP) models (called GHM and SHM, respectively) are designed to optimally solve the LB-ALBP, but the number of instances that are solved optimally is not operative. Finally, taking advantage of the designed mathematical programs, we design and evaluate three heuristic procedures based on these MILPs.

Future research work may involve designing and analyzing different ad hoc heuristic and metaheuristic methods for solving the LB-ALBP. An idea to be explored consists of solving the LB-ALBP with a heuristic for the SALBP-2. Then, the tasks assigned to the most heavily loaded workstation are fixed. Next the two subproblems generated, one with the tasks assigned before the fixed workstation and the another with the tasks assigned after the fixed workstation, are independently solved with the same heuristic for SALBP-2; and so on.

The distribution of the most critical workstations of an assembly line is another area of future research.

F

α

  Parameters to weigh the components of the objective function ( )

  have workloads, in descending order, of50-48-46-44 and 50-47-46-45 time units, respectively. 2 Sol is better than 1 Sol because, although the cycle times ( ) Sol has a smaller workload in the second most heavily loaded station ( )

  parameter δ (which is calculated, for each instance, by comparing each solution with the best solution obtained using the three heuristic procedures); and the minimum ( )

  parameter δ (which is calculated, for each instance, by comparing each solution with the best solution obtained using the two heuristic procedures); and the minimum ( )

  the other hand, the 74 solutions obtained with H2_SHM are farther from the 74 best solutions obtained with H1_SHM, as the larger average value of the parameter δ ( 0.48 = δ ) shows. Moreover, the results obtained with H1_SHM have less dispersion than the results obtained with H2_SHM: the maximum values of the parameter δ ( ) max δ are 2.95 and 20.26, respectively.

  parameter δ (which is calculated, for each instance, by comparing each solution with the best solution obtained using the two heuristic procedures); and the average ( ) t computing times, in seconds, and the standard deviation of the computing times ( )

  The 302 SALBP-2 instances have been classified according to their size (number of tasks, N ): i) Low/Middle-N ( )

Figure 1 .Figure 2 .

 12 Figure 1. Possible workload distributions

  Earliest and latest workstations, respectively, to which task i can be assigned, given a value of CT .

	Data:
	, i p	Index of tasks.
	j	Index of workstations.
	n	Number of tasks (	i	=	1,...,	n	)	.
	m	Number of workstations (	j	=	1,...,	m	)	.
	i E ,L i
									, i p such that there is an immediate
		precedence relation between them.

Therefore, a single mixed-integer linear programming (MILP) model is solved. i t Processing time of task i . CT Upper bound on the cycle time. P Set of ordered pairs of tasks ( )

  and only if task i is assigned to workstation j ( ) Workload assigned to workstation j (i.e., the sum of the processing times of the tasks assigned to the workstation j ).

	k T		Workload of the k -th most heavily loaded workstation. 1 T is the
			workload of the most heavily loaded station ( 1 T is therefore the cycle
			time); 2 T is the workload of the second most heavily loaded station,
	jk y ∈	{ } 0,1	etc. 1, if and only if station j has the k -th highest workload, k T .
		F o r
			P
			e
			e r
			R
			e
			v i e
			w
			O n l
			y
			; i j E i ∀ =	,...,	i L	.

j S

Table 1 .

 1 Optimal solutions for each objective

	o r
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y

Table 2 .

 2 Results of the mathematical programming models

	Heuristic H_GHM H1_SHM H2_SHM
	º N Sol	195	302	302

Table 3 .

 3 Number of instances with obtained solution

	Heuristic	º N Best	δ	min	δ	δ	max	t	min	t	t	max
	H_GHM	57		0	20.24	256.64		0	13,273 18,000
	H1_SHM	144		0	0.06	2.54		0	13,038 18,000
	H2_SHM	162		0	0.11	5.32		0	12,271 18,000

Table 4 .

 4 Results of the heuristic procedures for 195 instances

	Heuristic	º N Best	δ	min	δ	δ	max	t	min	t	t	max
	H1_SHM	235		0	0.05	2.95		0	14,736 18,000
	H2_SHM	228		0	0.48	20.26		0	14,243 18,000
	F o r
		P
		e
			e r
					R
					e
					v i e
							w
							O n l
										y
												21

Table 5 .

 5 Results of the heuristic procedures for 302 instances

	Heuristic	º N Best	δ	σ	δ	t	σ	t
	H1_SHM	193	1.22	3.32	14,736	6,847
	HPM_T&T	131	0.55	1.29	3,864	11,979

Table 6 .

 6 Results of the heuristic procedures H1_SHM and HPM_T&T (302 instances)

	Heuristic	º N Best	δ	σ	δ	t	σ	t
	H1_SHM	184	0.43	1.64	14,052	7,346
	HPM_T&T	72	0.69	1.42	550	1,356

Table 7 .

 7 Results of the heuristic procedures H1_SHM and HPM_T&T (236 Low/Middle-N instances)

	Heuristic	º N Best	δ	σ	δ	t	σ	t
	H1_SHM	9	4.02	5.58	17,185	3,373
	HPM_T&T	59	0.04	0.17	15,716	21,803

Table 8 .

 8 Results of the heuristic procedures H1_SHM and HPM_T&T (66 High-N instances)

	FIGURE CAPTION
	F o r
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y
	22

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

Acknowledgments

The author is very grateful to Professor Albert Corominas and to Alberto García (Technical University of Catalonia) for their valuable comments which have helped to enhance this paper. The author wish to express his gratitude to the anonymous reviewers for their detailed and valuable comments, which have helped to improve the quality of this paper.

† Supported by the Spanish Ministry of Education and Science, projects DPI2004-03472 and DPI2007-61905, co-financed by FEDER.

Problems in

 Manufacturing and Service Organizations, Martinus Nijholff Publishing. Suresh, G., Sahu, S., 1994