MD Maxime Jaubert

Christophe Jacquet

MD Charles Pioger

MD Abderahmane Sbihi

MD Martine Pithioux

PhD Marie Le Baron

PhD Akash Sharma

MBBS, FRCS Matthieu Ollivier
email: matthieu.ollivier@ap-hm.fr

A biomechanical in-vitro controlled study using graft from living donors Running title: Vancomycin Pre-soaking does not alter Hamstring Biomechanical Properties MD

Keywords: vancomycin, hamstring, ACL reconstruction, mechanical properties, tensile test, septic arthritis, pre-soaking

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Purpose:

The aim of this study was to compare the biomechanical properties of human semitendinosus graft pre-soaked with or without vancomycin under a load to failure tensile test.

Methods:

Thirty semitendinosus grafts harvested during ACL reconstruction were included. These were dissected equally into two halves and subsequently randomly allocated to a vancomycin group and to a control group. A digital caliper was used in order to precisely measure each samples thickness, length and width. For the vancomycin group; samples were pre-soaked in a solution of 5mg/ml of vancomycin for a duration of ten minutes and the control group samples were pre-soaked in a physiological serum equally for ten minutes.

Mechanical testing was performed on a universal testing machine (Instron 5566-A) after a pre-conditioning of 10 cycles of 1 mm extension and a progression of 10 mm/min to failure for each sample. The stress-strain curve was obtained to determine the elastic modulus (Young's modulus), the Ultimate Tensile Stress (UTS), the Ultimate Tensile Elongation (UTE) before failure and the elasticity limit.

Results:

For the control group, the average Young's modulus value was 4.8 ± 0.8, the average UTS 25.2 ± 5.2 Mpa, the average percentage of UTE 78 ± 17% and the average elasticity limit value 17.3 ± 5.3 Mpa. For the vancomycin group, the average young's modulus value was 4.7 ± 0.9, the average UTS 24.1 ± 6.1 Mpa, the average percentage of UTE 82 ± 14% and the average elasticity limit value 18.5 ± 5.9 Mpa. No significant difference was observed between the two groups for all investigated parameters.

INTRODUCTION

Septic arthritis following an anterior cruciate ligament (ACL) reconstruction is a serious complication, with the incidence rate ranging from 0.14 to 3.8% 1 4 . The treatment of this complication required in 33.3% of the cases a graft removal with adjuvant antibiotic (on average 35.4 days) with disastrous functional consequences for the patient [START_REF] Wang | Recommendations for the management of septic arthritis after ACL reconstruction[END_REF] .

Staphylococci are the most important causative agents in up to 90 % of cases with approximately half of those being identified as coagulase-negative staphylococci (CNS) 3,6 8 . Some authors relate this high rate of infections by CNS to skin microbial flora contamination during graft harvesting [START_REF] Sonnery-Cottet | Management of septic arthritis following anterior cruciate ligament reconstruction: a review of current practices and recommendations[END_REF] .

Recent studies advocate the pre-soaking of ligament autografts with vancomycin to prevent postoperative septic arthritis. These series discovered a significant reduction in the risk of infection in the group relying on this protocol (ten minutes of pre-soaking with 5mg/ml of vancomycin) [START_REF] Pérez-Prieto | Autograft soaking in vancomycin reduces the risk of infection after anterior cruciate ligament reconstruction[END_REF][START_REF] Phegan | No infections in 1300 anterior cruciate ligament reconstructions with vancomycin pre-soaking of hamstring grafts[END_REF] .

Vancomycin seems to be an ideal choice for prophylactic antibiosis when used topically. It demonstrates a low rate of bacterial resistance on gram positive bacteria [START_REF] Bruniera | The use of vancomycin with its therapeutic and adverse effects: a review[END_REF] and has low toxicity on local tissues [START_REF] Antoci | Antibiotics for local delivery systems cause skeletal cell toxicity in vitro[END_REF][START_REF] Edin | Effect of cefazolin and vancomycin on osteoblasts in vitro[END_REF] , Only one animal study in the literature has evaluated the impact of pre-soaking tendons with vancomycin and the possible consequences on their mechanical properties [START_REF] Schüttler | Biomechanical and microbiological effects of local vancomycin in anterior cruciate ligament (ACL) reconstruction: a porcine tendon model[END_REF] . The immediate impact on the biomechanical properties by pre-soaking human ligament autografts with vancomycin has not been not been studied thus far.

The aim of this present study was to compare the biomechanical properties of human semitendinosus graft pre-soaked with or without vancomycin under a load to failure tensile test. The hypothesis was that pre-soaking semitendinosus grafts with vancomycin did not alter their elastic modulus (Young's modulus), Ultimate Tensile Stress (UTS), Ultimate Tensile Elongation (UTE) before failure and elasticity limit.

Biomechanical testing was carried out with 30 semitendinosus tendon grafts harvested during ACL reconstruction surgery with a four stranded hamstring graft (semitendinosus + gracilis) between September 2017 and December 2018. All patients provided written consent, and the study was approved by our hospi .

After tunnel drilling and estimating the minimal length of the final graft, samples for testing were obtained by using distal portions of semitendinosus distal part (tibial insertion), if semitendinosus excess was longer than 6 cm. This allowed them to be equally split in two identical samples of at least 3cm which was the minimal length required to conduct mechanical testing.

The demographic characteristics (age, gender, height, weight, the sporting level evaluated by the University of California and Los Angeles (UCLA) score of the patients included are summarized in table 1.

The semitendinosus grafts deemed suitable for testing were stored at -20° for a maximum duration of 15 days before being prepared into samples to go through the mechanical test. It has been shown that this storage protocol does not alter the biomechanical properties of tendons [START_REF] Moon | The effects of refreezing on the viscoelastic and tensile properties of ligaments[END_REF] .

Preparation of the samples

After 8 hours thawing at ambient temperature (21°c) [START_REF] Vincent | The anterolateral ligament of the human knee: an anatomic and histologic study[END_REF] each semitendinosus was prepared into parallelepipeds and then cut in half to obtain two samples of equal length width and thickness. Subsequently each sample was randomly allocated to either a vancomycin group or a saline solution control group (30 samples in each group).

To minimize the bias in the preparation of the specimen, a digital caliper (Absolute Digimatic®, MitutoyoTM, Kanagawa,Japan) with a precision of U=0 .001mm was used in order to measure each samples thickness, length and width. These measurements allow section for each sample thus permitting stresses and strains estimation during load to failure tests. Each measurement was carried out by two different operators and the average of the two values was recorded.

The control group samples were pre-soaked in a physiological serum (NaCl 0.9%) for a duration of ten minutes.

Equally the vancomycin group samples were pre-soaked in a solution of 200ml of physiological serum and 1g of vancomycin for duration of ten minutes (5mg/ml concentration). This protocol has already proven it's efficacy in both clinical trials and in vitro studies [START_REF] Pérez-Prieto | Autograft soaking in vancomycin reduces the risk of infection after anterior cruciate ligament reconstruction[END_REF][START_REF] Phegan | No infections in 1300 anterior cruciate ligament reconstructions with vancomycin pre-soaking of hamstring grafts[END_REF][START_REF] Pérez-Prieto | Contamination occurs during ACL graft harvesting and manipulation, but it can be easily eradicated[END_REF] .

Tensile tests (figure 1)

Mechanical testing was performed on a universal testing machine (Instron 5566-A, Instron®, Norwood MA, USA) (Fig. 1). The ends of each specimen were placed in two jaws (1 cm from each end was placed in the two jaws) from previously published method [START_REF] Shi | A novel, inexpensive and easy to use tendon clamp for in vitro biomechanical testing[END_REF] . The mechanical properties were determined within the tissue between the two jaws again using a similarly validated process [START_REF] Massalou | Influence of loading speed on the mechanical properties of the colon[END_REF] . The length between the two jaws was measured using a digital caliper (Absolute Digimatic®, MitutoyoTM, Kanagawa,Japan). This length (L0) was used to determine the elongation during the test.

Specimens were pre-conditioned with 10 cycles of 1 mm extension. The interface of each specimen/jaw was marked with China ink to monitor potential sliding. All specimens were subjected to a tensile test with a progression of 10 mm/min to failure [START_REF] Ollivier | Ropivacaine alters the mechanical properties of hamstring tendons: In vitro controlled mechanical testing of tendons from living donors[END_REF] .

The elongation and the tensile force applied was measured using an acquisition software Bluehill 3 (Instron®, Norwood, MA, USA). The stress-strain curve was then calculated.

The following parameters were analysed to compare the samples:

-Young's modulus (Mpa)

-The Ultimate Tensile Stress before failure (Mpa)

-The Ultimate Tensile Elongation (UTE) before failure defined as the length variation from the initial length (L0) to failure, it was expressed as a percentage.

-The Elasticity Limit (Mpa) defined by the stress from which a sample stops deforming elastically and in essence demonstrates irreversible deformity.

-The level of the failure was also collected for each test : jaw-specimen interface or inside the specimen

Statistical analysis

The Kolmogorov-Smirnov's test was used to determine the data's normality distribution.

Parametrical tests were used to compare the normally distributed variable (demographical data's and mechanicals properties) between the groups. Non-parametrical tests were used to compare elongation at failure, since this data was not normally distributed.

Two-tailed tests were carried out using PASW Statistics version 20 (SPSS, IBM Inc., Chicago, Illinois). The significance threshold was set at P < 0.05. sample size calculations were based on results of the Ollivier et al study [START_REF] Ollivier | Ropivacaine alters the mechanical properties of hamstring tendons: In vitro controlled mechanical testing of tendons from living donors[END_REF] . These calculations showed that at least 25 samples were needed in each group to show a clinically significant difference of 5 Mpa in UTS value before failure between the groups ( ß= 0,8 for a mean UTS value before failure of 13± 7 Mpa 20 for the control group.). Consequently, we included 30 patients per group, which allowed for 5 specimens to be excluded if necessary.

RESULTS

No specimen slippage occurred and the calculations could be performed on all 60 sample tested. Four failures at the jaw-specimen interface for the control group and three for the vancomycin group (p=0.6) were observed. The other failure were observed inside the specimen.

The average Young's modulus value for the control group was 4.8 ± 0.8 and for the vancomycin group 4.5 ± 0.9.

The average Ultimate Tensile Stress value before failure for the group control was 21.2 ± 5.2

Mpa and for the vancomycin group 22.3 ± 6.1 Mpa.

The average percentage of Ultimate Tensile Elongation before failure for the control group was 78 ± 17% and for the vancomycin group 82 ± 14%. No significant difference was observed between the two groups for all three parameters (respectively p= 0.8, p=0.7, p=0.8.

(table 2)

Analysis of the stress-strain curves confirmed that the samples possessed a ductile behaviour demonstrating 2 distinct phases, a phase of linear elastic deformation and a phase of plastic deformation (figure 2). The average elasticity limit value for the control group was 18.3 ± 5.3 Mpa and for the vancomycin group 17.5 ± 5.9 Mpa. No significant difference was observed between the two groups (p=0.4)

DISCUSSION

The main finding of this study is that pre-soaking human semitendinosus grafts with vancomycin does not alter its biomechanical properties. The hypothesis was accepted as no between the vancomycin group and the control group.

Septic arthritis occurring after an ACL reconstruction is a serious complication, with a reported incidence rate of 0.14% to 1.8% 1 3 . Recent results of Sonnery-cottet et al [START_REF] Sonnery-Cottet | Professional Athletes Are at Higher Risk of Septic Arthritis After Anterior Cruciate Ligament Reconstruction: An Analysis of 4421 Consecutive Patients Including 265 Elite Athletes From the SANTI Study Group[END_REF] study demonstrated that this rate could reach 3.8% in a specific population of professional athletes.

In a recent meta-analysis, [START_REF] Wang | Recommendations for the management of septic arthritis after ACL reconstruction[END_REF] 86.9% of the population required a further surgical procedure for the treatment of septic arthritis post ACL reconstruction, and strikingly in 33.3% of the cases the graft required removal, furthermore adjuvant antibiotic therapy lasted on average 35.4 days.

Some in vitro studies have shown significant efficacy of vancomycin pre-soaking to eradicate bacteria in cases of septic arthritis post anterior cruciate ligament reconstruction [START_REF] Schüttler | Biomechanical and microbiological effects of local vancomycin in anterior cruciate ligament (ACL) reconstruction: a porcine tendon model[END_REF][START_REF] Pérez-Prieto | Contamination occurs during ACL graft harvesting and manipulation, but it can be easily eradicated[END_REF] .

In their animal study on staphylococcus epidermidis infected tendons, Schuttler et al [START_REF] Schüttler | Biomechanical and microbiological effects of local vancomycin in anterior cruciate ligament (ACL) reconstruction: a porcine tendon model[END_REF] demonstrated that pre-soaking for 20 minutes with high concentration vancomycin solution (5mg/ml) reduced bacterial growth after 7 days of culture from 85.7% to 0%.

In another study, Perez-prieto et al [START_REF] Pérez-Prieto | Contamination occurs during ACL graft harvesting and manipulation, but it can be easily eradicated[END_REF] showed that for samples contaminated after harvesting and manipulation/preparation, no bacteria was detected after 14 days in culture in a solution of vancomycin (5mg/ml).

The results of in vivo studies are also encouraging. In two controlled studies, Phegan et al [START_REF] Phegan | No infections in 1300 anterior cruciate ligament reconstructions with vancomycin pre-soaking of hamstring grafts[END_REF] and Péres-prieto et al [START_REF] Pérez-Prieto | Autograft soaking in vancomycin reduces the risk of infection after anterior cruciate ligament reconstruction[END_REF] have compared 285 and 810 patients respectively receiving intravenous antibiotic prophylaxis without topical graft pre-soaking to 1300 and 734 patients receiving the same antibiotic prophylaxis with pre-soaking the graft with vancomycin for 10 minutes (5mg/ml). The postoperative septic arthritis rate decreased from 1.4% to 0% and from 1.85% to 0% for the first and second study respectively. Furthermore, Phegan et al, included only hamstrings grafts whilst Péres-prieto et al included both hamstrings (84%) and patellar tendon (16%).

Formatted: English (United States)

The mechanical properties of ligaments and tendons are related to various morphological parameters (age, living donor vs cadaveric, preservation methods etc), and the method used to induce failure. These reasons would explain the important variability in the values obtained in mechanical testing from previously published series 20 23 . However, the results of the control group of this study are similar to those obtained by Ollivier et al [START_REF] Ollivier | Ropivacaine alters the mechanical properties of hamstring tendons: In vitro controlled mechanical testing of tendons from living donors[END_REF] who used an identical mechanical test protocol.

Only one animal study in the literature has evaluated the impact of pre-soaking tendons with vancomycin and the possible consequences on their mechanical properties [START_REF] Schüttler | Biomechanical and microbiological effects of local vancomycin in anterior cruciate ligament (ACL) reconstruction: a porcine tendon model[END_REF] . This study of porcine flexor tendons mirrors the finding of this study and shows no alterations were demonstrable in terms of their biomechanical properties after antibiotic soaking.

This study has some strengths that are important to highlight. It is one of the only study in the literature which investigates the impact of vancomycin on the mechanical properties of a human graft. Secondly the design of the study avoids the bias of inter-individual variability by using 2 groups with grafts from the same individual placed into each group. Lastly, donor grafts were used from living subjects, whilst in comparison previous published series report using either animal or cadaveric specimens [START_REF] Schüttler | Biomechanical and microbiological effects of local vancomycin in anterior cruciate ligament (ACL) reconstruction: a porcine tendon model[END_REF][START_REF] Pailhé | Biomechanical study of ACL reconstruction grafts[END_REF][START_REF] Chandrashekar | Sex-based differences in the tensile properties of the human anterior cruciate ligament[END_REF] .

Limitations Some limitations can be attributed to this study. Firstly, semitendinosus was the only graft to be evaluated, therefore these results cannot represent all grafts used in common practice for ACL reconstruction.

Secondly, the tensile test was performed on frozen grafts, but it is important to note that it has been shown that the mechanical properties of tendons are not affected by freezing if less than 3 cycles of freezing thawing are performed 25 27 .

ThirdlyFinally, the fixation can influence the results of these tensile tests [START_REF] Butler | Effects of structure and strain measurement technique on the material properties of young human tendons and fascia[END_REF] . Jaws made from resin or cryoclamps are difficult to use and their use has not been validated [START_REF] Riemersa | The cryo-jaw, a clamp designed for in vitro rheology studies of horse digital flexor tendons[END_REF][START_REF] Cheung | A serrated jaw clamp for tendon gripping[END_REF] . Shi and al.

other type of jaws. It is this type of jaw that that has been used in this study.

Despite these limitations, this study demonstrates that vancomycin pre-soaking does not affect immediate biomechanical properties of semitendinosus tendonFinally, s. tThis in-vitro time zero analysis on nonthe ligamentization process and therefore these results must be completed by further histological studies to confirm the safe use of vancomycin pre-soaking at mid and long term time points.

CONCLUSION

Pre-soaking of human semitendinosus graft with vancomycin does not alter its biomechanical properties

Figure 1

 1 Figure 1 Tensile testing machine

Figure 2 :

 2 Figure 2: Examples of stress-strain curves for a vancomycin sample group (A) and a control sample group (B). The red line corresponds to the elastic limit and the green line to the ultimate tensile stres

Figure 1 Figure 1

 11 Figure 1 Tensile testing machine

Table 1 :

 1 Demographic characteristics of patients included

Table 2 :

 2 Mean difference for the four analysed parameters between the control group and

	the vancomycin group

validated the use of serrated jaws for ligament autograft fixation after comparing them to Formatted: English (United States)


Alexandre Dolgui
email: alexandre.dolgui@imt-atlantique.fr

Genrikh Levin
email: levin@newman.bas-net.by

Boris Rozin
email: rozin@newman.bas-net.by

OPTIMIZATION OF THE AGGREGATION AND EXECUTION RATES FOR INTERSECTING OPERATION SETS: AN EXEMPLE OF MACHINING PROCESS DESIGN

Keywords: Transfer lines, Batch processing, Aggregation of operations, Operation rate, Operation costs and times, Optimization

published or not. The documents may come

Optimisation of the aggregation and execution rates for

intersecting operation sets: an example of machining process design

Introduction

In last decades, significant attention was paid to the process planning for complexes of interrelated operations in various engineering, organizational and production systems (see, for example, [START_REF] Szadkowski | An approach to machining process optimization[END_REF][START_REF] Alting | Computer Aided Process Planning: the state-of-the-art survey[END_REF]Boysen, Fliedner and Scholl 2007;[START_REF] Bukchin | A weighted approach for assembly line design with station paralleling and equipment selection[END_REF][START_REF] Halevi | Process and Operation Planning[END_REF][START_REF] Battaïa | A taxonomy of line balancing problems and their solution approaches[END_REF]. The development of models and methods for joint optimization of the structure of these complexes and execution rates of their operations is of considerable scientific and practical interest.

In this paper, one of the possible approaches to solve such problems is developed. It is illustrated with an example of optimization of transfer line structure and parameters for multi-product batch machining. A multi-position single-flow transfer line of conveyor type is considered (see, in particular, [START_REF] Dolgui | Cost optimization for series-parallel execution of a collection of intersecting operation sets[END_REF][START_REF] Battaïa | Decision support for design of reconfigurable rotary machining systems for family part production[END_REF].

It is assumed that input sequence of parts is composed of identical sub-sequences of parts (batches). A set of all operations which must be executed at the line for each part as well as an assignment of the operations to the line positions (stations) are given. The term "operation" refers to a set of interrelated machining steps (e.g., milling, drilling, reaming etc.) that is considered as an indivisible action executed at one position (station) by a common drive unit.

The working stroke and range of possible values of the feed per minute used to process a specific part by a drive unit dealing with an operation are given for all parts and operations.

For the sake of terminological generality with other possible application areas, the working stroke will be considered as the volume of operation and will be given for each pair "operation-part".

Similarly, the feed per minute employed for an operation will be considered as the operation rate and also defined for each pair "operation-part". It is assumed that, with a sufficient accuracy for the considered stage of the manufacturing process design, selected operation rates determine all other machining conditions of operations (cutting speeds, feeds per revolution, etc. for all their machining steps) taking into account the corresponding machining technologies (see, for example, [START_REF] Levin | Optimization of machining modes for multi-head machines under group replacement of tools[END_REF].

Parts are machined successively one by one at each working position in the order of their arrival and in the order of location of the positions in the transfer line. At each time point only one part is disposed at each position. Sets of operations executed at a position for different parts can intersect.

At the stage of the machining process planning some operations can be aggregated into blocks.

All operations of the same block are executed simultaneously by using the same drive unit with a common operation rate (for example, by using a common multi-spindle head). The volume of each block of operations is the maximum of volumes of its operations.

The aggregation of operations into blocks reduces investment and maintenance costs but excludes the possibility of individual selection and optimization of operation rates for aggregated operations. The latter can lead, in particular, to an increase of operation durations, operating costs, the cost and time related to the consumption of tools and their replacement. Feasibility of an aggregation depends on both the mutual disposal of the machined features of the parts and the capabilities of the available equipment.

The set of potentially feasible blocks is assumed to be specified.

The paper deals with the case when all operations of the same potential block can be performed either completely aggregated (in the block) or completely disaggregated (individually). It is impossible to execute a part of block in the aggregated manner and the rest individually, otherwise the corresponding part of block is considered as a block.

The selected option of aggregation of operations and their rates largely determine the structure and parameters of the machining process, the layout of the line as well as the characteristics of the line equipment. Therefore, this decision significantly affects the output of the line, the line investment cost, operational cost, tool consumption and, consequently, the total cost of batch machining.

The objective is to select aggregation options and rates for all operations minimizing the total cost of batch machining while providing a required output of the line.

The rest of the paper is organized as follows. A brief review of literature related to the considered problem is reported in Section 2. The problem statement and its mathematical model are presented in Section 3. The solution techniques based on two-level decomposition scheme are described in Section 4. Section 5 is devoted to industrial example illustrating the proposed approach.

Finally, Section 6 includes conclusion remarks. The appendix contains a table of notations used in the paper.

Breaf review of literature

One of the first papers on optimization of execution of operation sets in machining systems with a graph approach was published by [START_REF] Szadkowski | An approach to machining process optimization[END_REF]. Several aspects of the structural and parametric optimization of machining processes in a transfer line of conveyor-type composed of aggregate machines were studied by [START_REF] Levin | Decomposition methods for optimizing design solutions[END_REF]. Comprehensive surveys of machining process planning articles are presented by [START_REF] Alting | Computer Aided Process Planning: the state-of-the-art survey[END_REF][START_REF] Alting | Computer Aided Process Planning: the state-of-the-art survey[END_REF][START_REF] Halevi | Process and Operation Planning[END_REF]. A number of articles, e.g. [START_REF] Bennett | A decomposition approach for an equipment selection and multiple product routing problem incorporating environmental factors[END_REF], [START_REF] Singh | Feature-based design for process planning of machining processes with optimization using genetic algorithms[END_REF], and [START_REF] Gupta | Development of an integrated model for process planning and parameter selection for machining processes[END_REF], were devoted to problems of complex process planning including equipment selection. [START_REF] Singh | Feature-based design for process planning of machining processes with optimization using genetic algorithms[END_REF] used feature-based environment and operation-based feature mapping to design the set of operations for machining a given part. Then they applied genetic algorithm to find an optimal (for the selected objective function) sequence of operations, machines and cutting tools with respect to a given factory environment. [START_REF] Gupta | Development of an integrated model for process planning and parameter selection for machining processes[END_REF] developed an integrated model to find an optimal sequence of operations for a given set of machines, tools and machining conditions minimizing the cost of machining cylindrical parts. [START_REF] Bennett | A decomposition approach for an equipment selection and multiple product routing problem incorporating environmental factors[END_REF] developed models for selection of equipment in multi-product production systems taking into account capacity consumption, product routing, and impact on the environment.

Joint problems of process planning and scheduling were considered by [START_REF] Mohapatra | Integration of process planning and scheduling through adaptive setup planning: a multi-objective approach[END_REF]. In [START_REF] Koren | Choosing the system configuration for high-volume manufacturing[END_REF] the impact of configuration of production system for high-volume manufacturing on the enterprise long-term profitability considering investment cost, throughput, responsiveness to market changes and product quality, was analyzed.

A number of process planning studies have been devoted to the problems of machining conditions optimization, e.g. [START_REF] Arezoo | Selection of cutting tools and conditions of machining operations using an expert system[END_REF], [START_REF] Cakir | Optimization of machining conditions for multi-tool milling operations[END_REF]. [START_REF] Arezoo | Selection of cutting tools and conditions of machining operations using an expert system[END_REF] addressed the problems of selection of cutting tools and conditions of machining operations using an expert system. [START_REF] Cakir | Optimization of machining conditions for multi-tool milling operations[END_REF] suggested a procedure to calculate machining conditions of multi-tool multi-pass milling operations to minimize the production cost.

Among other related problems studied in the literature should be mentioned machining and assembly line balancing problems, that consider allocation of operations to working stations, e.g. Boysen, Fliedner and Scholl (2007), [START_REF] Bukchin | Design of flexible assembly line to minimize equipment cost[END_REF], [START_REF] Bukchin | A weighted approach for assembly line design with station paralleling and equipment selection[END_REF], [START_REF] Dolgui | Graph approach for optimal design of transfer machine with rotary table[END_REF], [START_REF] Kara | Balancing straight and U-shaped assembly lines with resource dependent task times[END_REF], [START_REF] Battaïa | A taxonomy of line balancing problems and their solution approaches[END_REF], [START_REF] Battaïa | Decision support for design of reconfigurable rotary machining systems for family part production[END_REF].

The problem considered here is novel and more complex. The nearest problems to it with common elements are those of structural parametric optimization of machining processes in a transfer line of conveyor-type composed of machine tools reported by [START_REF] Levin | Decomposition methods for optimizing design solutions[END_REF] and the line balancing problems with equipment selection considered in [START_REF] Bukchin | Design of flexible assembly line to minimize equipment cost[END_REF][START_REF] Bukchin | A weighted approach for assembly line design with station paralleling and equipment selection[END_REF]. [START_REF] Levin | Decomposition methods for optimizing design solutions[END_REF] studied the same type (as in this work) of transfer lines, but they considered processing only homogeneous parts. Also, the selection of an optimal aggregation from a set of feasible aggregation options was not considered in that work. [START_REF] Bukchin | Design of flexible assembly line to minimize equipment cost[END_REF], [START_REF] Bukchin | A weighted approach for assembly line design with station paralleling and equipment selection[END_REF] considered only the case where the intensities of operations execution were uniquely determined by the equipment option selected from a finite set, the possibility of the intersection of sets of operations was not studied. In this paper, the problem consists in selection of an optimal option of aggregation and rates of all operations minimizing the total batch processing cost while ensuring the required line productivity.

There are also our recent papers [START_REF] Levin | Optimization of Multi-tool Cutting Modes for Batch Manufacturing in Large Series Machining Environment[END_REF][START_REF] Levin | Linear approximation of the problem of optimization of intensities of series-parallel execution of intersecting operation sets[END_REF][START_REF] Dolgui | Cost optimization for series-parallel execution of a collection of intersecting operation sets[END_REF][START_REF] Levin | Optimization of the Structure and Execution Modes of Intersecting Operation Sets[END_REF], where some models and methods for solving problems related to the optimization of execution rates of a collection of intersecting operation sets have already been proposed. But, in that studies the selection of the structure of a collection of intersecting operations and of respective pieces of equipment for their execution were not considered. Note that each of the problems considered in [START_REF] Levin | Optimization of Multi-tool Cutting Modes for Batch Manufacturing in Large Series Machining Environment[END_REF][START_REF] Levin | Linear approximation of the problem of optimization of intensities of series-parallel execution of intersecting operation sets[END_REF][START_REF] Dolgui | Cost optimization for series-parallel execution of a collection of intersecting operation sets[END_REF][START_REF] Levin | Optimization of the Structure and Execution Modes of Intersecting Operation Sets[END_REF]) is a special case of the problem studied in this paper.

To summarize, some aspects of the considered problem were already studied in the above mentioned publications, but no one of these articles has addressed the problem as a whole.

Statement of the problem and its mathematical model

Outline of a machining process and a transfer line

A process of machining multiple parts at a multi-position single-flow transfer line with linearly ordered (working) positions is considered. The input sequence of machined parts is composed of cyclically repeated identical subsequences (batches) } ,...,

{ 1 n    
, including all parts of a given list M; some parts dM in the batch  can be repeated, i.e. n|M|. Parts are machined successively one by one at each working position in the order of their arrival and location of the positions in the transfer line. At each position for each part a given set of machining operations are executed in parallel (simultaneously).

The sets executed at the same position for different parts can intersect. It is assumed that the same operation for different parts is executed by the same tools, but some of its parameters (in particular, the working stroke, cutting lengths, etc.) for different parts can differ.

The process consists of takts of simultaneous machining all parts located at respective positions.

At each time point only one part is disposed at each position. After completing the current takt, all processed parts are moved simultaneously to their next respective working position. The part from the terminal position leaves the line and the next one of the input sequence is loaded to the first position. Then the following takt is executed. The subsequence of n takts that result in the production of one batch constitute the cycle of the batch processing. Without loss of generality, we assume that in takt 1 part 1 of subsequence  is located at position 1. Then in the takt i=1,…,n in position k=1,2,…

the part dik= (i,k) is processed, where (i,k)= ) )), , mod( mod(( 1 n n k i n   
is the index of this part in the batch .

Subsequently, J is the given set of all operations executed at all line positions for all parts and Ji is the subset of the operations from J executed in takt iI={1,...,i,...,n}. ,2,3,3,4) to the positions of a 6-position transfer line in different takts of one cycle of machining (index of the part in the sequence /its type).

In general, identical operations may be executed at different positions and the set I of takts of the cycle may include identical takts. However, to simplify the presentation, here all takts in a cycle and operations of different positions are considered as different, i.e. each operation jJ is executed at its own position k(j). In this case, the takt iI and the operation jJi determine the part dij machined by this operation in this takt. This makes it possible to exclude subsequently from consideration the position indices in the variables. In this paper, the case when the feed per minute of an operation is the same for all parts processed is considered.

1 loading position Parts  2  n-2 Spindle heads 2 3 4 5 working positions  n-1  n-4  n  1  3  n-3
The following notations are introduced (see in the Appendix the table with all notations):

-Ljd is the given (minimal required) working stroke of the respective drive unit for operation jJ when machining part dM, Ljd = 0 if operation j is not executed for d;

-Sj = [Sj1, Sj2]
is the given range of feed per minute Sj for operation jJ considering that this operation is executed for different parts (value Sj is to be determined).

At the design stage of a machining process and transfer line, some operations can be aggregated in blocks. All operations of a block are executed in parallel by the same drive unit (in particular with the use of a single multi-spindle head) with common feed per minute and working stroke. We study the case when (i) the possibilities of aggregation of operations jJ into blocks are specified by a family W of non-unit nonintersecting subsets w of operations from J, (ii) each subset wW can be executed either completely aggregated (i.e. as one block) or completely disaggregated (i.e. as |w| individual operations), (iii) any combination of aggregation/disaggregation option of potential blocks is possible.

Let qw=0 if all operations from w are executed in aggregate manner and qw=1 otherwise. The requirement of a common feed per minute for all operations of the block excludes the possibility of selecting the best machining conditions for each of its operations individually. It is assumed that for wW the common working stroke (for qw=0) of all operations jw when machining part d is

Lwd = max{Ljd|jw} and     w j j

S

because otherwise operations from w cannot be executed in one block. Further, q=(qw| wW) and Q is the set of possible options of vector q to be selected, |Q|2 |W| .

The case when the selected aggregation option and the feed per minute for all operations remain invariable during the line functioning is considered.

An example of execution of two operations from a subset wW for part dM is shown in Figure 2a) for their disaggregated execution and in Figure 2b) for their aggregated option.

In the first case the working strokes

j 2 j 1 j 2 w={j 1 , j 2 }
It is assumed that operations of one position can be aggregated into several blocks and each block can comprise operations executed for different parts processed at respective position in different takts.

As was above mentioned, it is assumed that with an accuracy sufficient for considered stage of the manufacturing process design, the selected feed per minute of each operation allows to determine (for the accepted aggregation option) other components of its machining conditions. In turn, that makes it possible to estimate for each tool its average life time and consumption, for machining a single batch.

Decisions on how operations are aggregated into blocks as well as decisions on feeds per minute for each block are made at the line design stage and remain invariable (at least during a large period of its operating time). Therefore, the choice of the most rational joint decisions regarding these important characteristics of the structure and the parameters of the manufacturing process are crucial.

In the next subsection, the dependences of the components of productivity and the cost of the manufacturing process on the selected decisions are considered.

In the future, for the convenience of presentation of the proposed mathematical model of the considered problem and the methods for solving it, parameter Sj of operation j is substituted for parameter uj=1/Sj which we will call "operation rate". It is obvious that ujUj=

[uj1,uj2]=[1/Sj2,1/Sj1]. As operation jJ in takt iI is executed for part dij, value Lij= ij jd
L will be considered as the "volume" of this operation in this takt. Operation rate means the time spent for execution of a unit of volume of this operation.

Since all operations j from block wW should have the same operation rate uj then ujUw= [U1w=max{u1j|jw}, U2w=min{u2j|jw}]  . For fixed qQ the sought vector u=(uj|jJ) must be selected from the set U(q)={uU|

j j u u    
Uw for any j, jw and wW if qw=0}, where U=  J j j U .

The following additional assumptions are used in this study:

1. Operations performed at different working positions of the line, as well as all takts of the cycle for processing a batch of parts, are considered as different.

2. The sets of operations of potential blocks do not intersect.

3. All operations of each of the potential blocks can be performed either completely aggregated (in the block) or completely disaggregated (individually), no possibility to aggregate only a part of block.

4. All operations aggregated in one block are performed with the same intensity.

It should be noted that the proposed methods do not need assumption 1 and can be applied without it, but the presentation of the mathematical model will be much complicated. The generalization of the rest of these assumptions requires additional research.

Cost and time of batch  machining

In the considered problem statement, the components of the total cost and total time for machining one batch  for the fixed values of vectors qQ and uU can be defined as follows.

Let 1(q,u)=11(q,u)+12(q,u) and 2(q,u)=21(q,u)+22(q,u) be the dependences of the total cost and the total time of one cycle of machining the batch  on values of vectors q and u (which are decision variables).

The term 11(q,u) takes into account salary, depreciation of equipment, its maintenance cost, overheads, etc. The term 21(q,u) takes into account besides the operating time also the time for tools replacement, maintenance time, etc. In turn, the terms 12(q,u) and 22(q,u) take into account the cost and time related to the consumption of tools per one cycle of machining the batch , respectively.

The terms 11(q,u) and 21(q,u) are considered usually as linearly dependent on the net duration of the cycle of machining the batch :

p1(q,u) = ) } | (max{ ) ( ) ( 1 0 bi I i i j ij p p t J j u L G G      q q
, p=1,2.

(1)

Here and below the p=1 refers to the cost and p=2 to the time.

In (1), Lijuj is the duration of operation j in takt i; max{Lijuj | jJi}+tbi is the net duration of takt i;

) } | (max{ bi I i i j ij t J j u L    
is the net duration of the cycle, where tbi is the auxiliary time (e.g. the duration of idle movements); Gp0(q) are components of cost and time related to a single cycle of machining  that do not depend on the cycle net duration.

Components G11(q) and G21(q) are values of respective cost and time per unit of the cycle net duration. Coefficients Gpl(q) depend on the accepted option q of aggregation and are assumed to be given for all possible q, p=1,2, l=0,1. Coefficients Gp0(q) allow to take into account in particular the situation when the production line is designed for a fixed output.

In many real-life situations, with a sufficient accuracy, the following form of these functions can be used:

Gpl(q)=Epl+  W w ( Eplw(1-qw)+eplwqw),
where Epl0 takes into account the piece of the cost (or time) that does not depend on aggregation of operations, Eplw0 and eplw0 take into account the piece of the cost (or time) related to aggregated or disaggregated executing the operations of wW, respectively. Further it is assumed that Eplw<eplw for all p=1,2, l=0,1, and wW.

Let consider in more detail the terms 12(q,u) and 22(q,u). Note, that these terms depend mainly on rates u, but the range U(q) of possible values of vector u is determined by the selected values for q. In this paper, when selecting uU(q), it is assumed that tools are replaced independently from each other as they wear. Note that an approach to optimize machining conditions under group replacement of tools was considered in [START_REF] Levin | Optimization of machining modes for multi-head machines under group replacement of tools[END_REF].

Let Rj be the set of tools executing operation jJ and Nijr(uj) be the estimated number of parts dij machined by this tool during its life time , if tool rRj does not machine part dij.

Under individual replacement of worn tools, the average number of cycles of batch  machining between replacements of tool rRj is equal to

Njr(uj)=  I i j ijr u N )) ( / 1 ( / 1 .
To evaluating the dependence of tool life on the operation rate, we will introduce the following assumptions:

a) The feed per revolution sjr for tool rRj of operation j is the same for all parts dM it processes. This feed is usually maximized in the possible range (determined by the processing conditions of all the parts), taking into account its possible relations with the feeds of other tools for this operation. Therefore, to simplify it is assumed that the feeds sjr are known in advance for each tool rRj of each operation jJ. Thus, the selected rate uj of operation j determines the cutting speed vjrd when processing part d by tool r: vjrd = jrd/uj, where jrd is a given constant depending on the diameter of machining.

b) As in [START_REF] Levin | Decomposition methods for optimizing design solutions[END_REF], the dependence of the expected tool life on feed and cutting speed can be presented by the following modification of the well-known Taylor function:

         rd rd rd v s C v s T rd rd ,..., 1 min ) , (
, where rd  ,  rd C >0, и   rd >rd  >1 are known constants for the specific processing conditions (material of the part, cutting depth, tool material, etc.), rRj, dM, =1,…, rd μ . This modification describes the considered dependence as a concave (in logarithmic scale) function that is in good agreement with the majority of real life situations for a wide range of feed and cutting speed changes.

In accordance with above mentioned, we obtain the following dependence of the tool life for tool r when processing part dij with operation rate uj (for the simplicity indexes ij for the part dij are omitted):

rdμ rd j rdμ μ μ j rd u C u T    min ) ( ,..., 1 , (2)
where

rdμ rdμ s C C rdμ rdμ     ~>0.
Hence, cost and time of operation j in takt i (i.e. when machining the part dij) related to the consumption of tools per one cycle of machining the batch  for a fixed ujUj are equal to:

fpij(uj)= ) ( / j ijr R r pjr u N g j   = ) / ( max ,..., 1     j ijrμ rd R r j pijrμ μ μ u C , p=1,2, iI, jJi, ( 3
)
where gpjr is a given cost (p=1) or a given time (p=2) spent on one replacement of tool rRj,

μ rd rd pjr pijrμ ij ij C l g C /  , 1     μ rd ijrμ ij .
It is obvious that functions fpij(uj), p=1,2 are positive nonincreasing convex functions of operation rate ujUj. According to above mentioned, fpij(uj)=0 if operation j is not executed in takt i.

Thereby for fixed values of vectors qQ and uU(q) the cost 12(q,u) and the time 22(q,u) are defined by the following relations:

     I i J j j pij p i u f Φ ) ( ) , ( 2 u q , p=1, 2. ( 4
)
Thus, the total cost and total time for machining one batch  of parts are defined by the expressions:

p(q,u)= ) } | (max{ ) ( ) ( 1 0 bi i j jd I i p p t J j u L G G ij      q q      I i J j j pij i u f ) ( , p=1,2.
(5)

Mathematical model of the problem

The considered problem is to determine an aggregation option qQ for operations from wW and operation rates u=(uj|jJ)U(q) to minimize the total cost 1(q,u) of one cycle of batch  machining, provided that the total time 2(q,u) of the cycle (including the time spent on equipment maintenance and worn tools replacement) does not exceed the specified value T 0 determined on the basis of the required line throughput. Taking into account the proposed assumptions, this problem is reduced to the following mixed integer nonlinear programming problem:

Minimize            I i i J j j ij I i bi i j ij u f t J j u L G G Φ ) ( ) } | (max{ ) ( ) ( ) , ( 1 11 10 1 q q u q , (6) s.t. 0 2 21 20 2 ) ( ) } | (max{ ) ( ) ( ) , ( T u f t J j u L G G Φ I i i J j j ij I i bi i j ij             q q u q , ( 7
)
qQ, (8)

uU(q), ( 9
)
where q=(qw| wW), u=(uj|jJ) are decision variables.

In the next section, a special method to solve the problem ( 6) -( 9), called further as Problem A, is proposed.

Solution technique

The considered approach to solve Problem A is based on the following its properties:

i) the variables of the problem are divided into two heterogeneous groups: |W|-dimensional binary vector q=(qw|wW)Q and |J|-dimensional vector u=(uj|jJ)U with continuous components ujUj;

ii) functions 1(q,u) and 2(q,u) have identical structure;

iii) if q,qQ are such that qq and qwqw for all wW then U(q)U(q) and p(q,u)< p(q,u) for all uU(q), p=1,2; iv) under the previous conditions iii), if Gpl(q) = Gpl(q) for all p=1,2, l=0,1, then p(q,u * (q))  p(q,u * (q)), p=1,2, where u  (q) is the solution of Problem A for a fixed q.

Two-level decomposition scheme

The two-level decomposition scheme proposed to solve Problem A is depicted in Figure 3.

At the lower level, for a fixed vector qQ, the corresponding sub-problem В(q) is solved. A subproblem В(q) consists in determining the value u  (q) of vector uU(q) minimizing the function

1(q,u)=          I i i J j j ij bi i j ij I i u f t J j u L G ) ( ) } | max{ ( ) ( 1 11 q
subject to the condition:

2(q,u)=          I i i J j j ij bi i j ij I i u f t J j u L G ) ( ) } | max{ ( ) ( 2 21 q  0 T - ) ( 20 q G .
At the upper level, sub-problem C to define the vector q * minimizing the function  * (q)+G10(q) is solved, where  * (q)=1(q,u  (q)) and  * (q)= if sub-problem В(q) is unsolvable.

Figure 3. Decomposition scheme to solve Problem A C:  * (q) + G10(q)min, qQ. q  * (q) B(q): 1(q, u) min (= * (q)), 2(q, u)  T 0 -G20(q) , uU(q), q = const.

Since q * and u  (q) are solutions of sub-problems С and В(q) respectively, then (q * ,u  )=(q * ,u  (q * ))

is a solution of Problem A. If q * and u  (q * ) are approximate solutions of corresponding sub-problems, then vector (q * , u  ) is an approximate solution of Problem A.

Below some of possible approaches to solve the obtained sub-problems are presented. For a more detailed consideration of sub-problems В(q) of the lower level, it is necessary to consider if the corresponding operations (and variables associated with them) are executed in the aggregate or disaggregate manner. Since for aggregated execution of some block w, operation rates uj for all operations jw are the same, then the number of variables of sub-problem В(q) can be reduced. For this, the following additional notations are introduced:

W 0 (q) = {wW| qw=0} is a subset of operation blocks from W executed in the aggregate manner for a fixed qQ; 0 i W (q) ={wW 0 (q)|wJi} is a subset of operation blocks from W 0 (q) that comprise operations executed in takt iI; J 1 (q)={jJ|jwW 0 (q)} is a subset of operations from J that are executed for a fixed q in the disaggregate manner (i.e. with individual rates); u(q) = (uj|jJ 1 (q)) and u(q) = (uw|wW 0 (q)) are vectors of operation rates to be determined for operations j from J 1 (q) and for operations j from wW 0 (q) respectively; iw = max{Lij|jJiw} is the volume of potential operation block wW executed in iI;

  I i j pij j pj u f u f ) ( ) ( ~ and    w j w pj w pw u f u f ) ( ) ( ˆ
are the functions of cumulative cost (p=1) and of cumulative time (p=2) for operation jJ and for operation block wW, respectively, on their rates in a single execution of one cycle of batch machining;

p E ~(q)=       ) ( \ 1 ) ( 1 1 0 0 q q W W w w p W w w p p e E E
is the cost (p=1) or the time (p=2) of maintenance of equipment and its depreciation per unit of cycle duration.

Then, for a fixed vector qQ, sub-problem В(q) of the lower level is reduced to the following nonlinear programming problem:

Minimize      I i bi i w iw i j ij t W w u Λ J j u L E Θ ) )}} ( | max{ )}, ( | (max{max{ ) ( )) ( ), ( ( ~0 1 1 1 q q q q u q u       ) ( 1 ) ( 1 0 1 ) ( ) ( ~q q W w w w J j j j u f u f (10) s.t.      I i bi i w iw i j ij t W w u Λ J j u L E Θ ) )}} ( | max{ )}, ( | (max{max{ ) ( )) ( ), ( ( ~0 1 2 2 q q q q u q u 0 ) ( 2 ) ( 2 0 1 ) ( ) ( ~T u f u f W w w w J j j j        q q , ( 11
)
ujUj, jJ 1 (q), ( 12) uwUw, wW 0 (q), ( 13)

where uj, jJ 1 (q), uw, wW 0 (q) are decision variables for the fixed vector q.

According to the mentioned above property iii) of Problem A, the vector u * (q) can be used as an initial point in solving sub-problem В(q) if q q. Possible approaches to solve sub-problem В(q)

is largely dependent on the properties of its components. In [START_REF] Dolgui | Cost optimization for series-parallel execution of a collection of intersecting operation sets[END_REF], a special case of Problem A is studied when: (i) volumes Lij for any operation jJ are the same for all iIj, where Ij is the set of takts from I in which operation j is executed, (ii) values iw for each operation block wW are identical for all takts iI(w)={iI |wJi}. In this case, the duration of operation jJ as well as the duration of operation block wW are also the same for all takts iIj and iI(w), respectively. The proposed approach to this problem is based on a combination of Lagrangian relaxation and Dynamic programming.

Below we will describe the approach to solve В(q) for more frequent case in practice when these volumes can be different.

Sub-problem В(q)

As above mentioned, in sub-problem В(q) functions ) ( ~j pj u f and ) ( ˆw pw u f are non-increasing positive and convex on segments Uj and Uw respectively for all jJ, wW. Therefore, the wellknown methods of convex programming are applicable to solve this sub-problem. Furthermore, the last two terms in the functions

)) ( ), ( ( ~1 q u q u Θ и )) ( ), ( ( ~2 q u q u Θ
are separable. Thus, to solve В(q) it is possible to use, in particular, an approach analogous to the one proposed in [START_REF] Rozin | Optimization of Multi-tool Cutting Modes in Multiitem Batch Manufacturing System[END_REF][START_REF] Levin | Linear approximation of the problem of optimization of intensities of series-parallel execution of intersecting operation sets[END_REF]) which proved to be effective for a similar problem. This approach is based on approximation of sub-problem В(q) by a linear programming problem.

To describe this approach let us introduce the following piecewise linear approximations of functions ) ( ~j pj u f and ) ( ˆw pw u f on the segments Uj and Uw , respectively:

) ( ~j pj u f max{apjk uj + bpjk | k=1,…,k1pj}, p=1,2, jJ, ( 14
) ) ( ˆw pw u f max{cpwk uw + dpwk | k=1,…, k2pw }, p=1,2, wW, ( 15
)
where apjk, bpjk, cpwk, dpwk, k1pj and k2pw are parameters of this approximation. Note that these parameters do not depend on the value of vector q. Thus these approximations can be constructed in advance before the solution of Problem A and can be used to solve problems В(q) for different values of vector q.

Then the approximate solution of problem В(q) for a fixed qQ can be obtained by solving the following linear programming problem:

Minimize         ) ( ) ( 1 1 1 1 0 ) ( ~q q q J j W w w j i I i z y t E , ( 16
) 0 ) ( ) ( 2 2 2 1 0 ) ( ~T z y t E J j W w w j i I i          q q q , ( 17
) ti -Lij uj ≥ 0, iI, j 1 i J (q), ( 18
)
ti -iwuw ≥ 0, iI, w 0 i W (q), ( 19)

ypj -apjk uj ≥ bpjk, p=1,2, jJ 1 (q), k=1,…, k1pj, ( 20
)
zpwcpwk uw ≥ dpwk, p=1,2, wW 0 (q), k=1,…, k2pw, (21) ujUj, jJ 1 (q), ( 22) uwUw, wW 0 (q). ( 23)

In this problem, vectors t=(ti | iI), y(q) =(ypj| p=1,2, jJ 1 (q) ), z(q) =(zpw| p=1,2,wW 0 (q)), u(q) and u(q) are to be defined. If (t  ,y  (q),z * (q),u * (q) ,u * (q)) is its solution then vector u=(uj|jJ) with the components uj=

) ( * q j u
for jJ 1 (q) and uj= ) ( * q w u for jwW 0 (q) can be accepted as an approximate solution u  (q) of problem В(q). The discrepancy between the minimum values of the objective functions of problem В(q) and its approximation ( 16)-( 23) is determined by the accuracy of the approximation ( 14)-( 15) of functions ) ( ~j pj u f and ) ( ˆw pw u f in the vicinity of solution of problem В(q).

To solve the approximate problem ( 16)-( 23) for fixed values qQ, the existing software tools such as CPLEX or LPSolve can be used. The performance of the proposed approach when solving a subproblem В(q) using computer Intel Xeon CPU E5320 with parameters 1.86 GHz and 8GB of RAM and the software LPSolve is reported in [START_REF] Levin | Optimization of the Structure and Execution Modes of Intersecting Operation Sets[END_REF].

Sub-problem C

In sub-problem C, the number of possible values of vector q in the set Q may be up to 2 |W| , so full enumeration of set Q with solving of sub-problem В(q) for each qQ requires a significant time even for relatively small values of |W| and practically impossible for a large |W|. In such a situation, it seems promising to use methods based on the ideas of random search, heuristics and metaheuristics in combination with the proposed below a special version of the method of sequential fixing of variables (MSFV).

The algorithm MSFV starts with initial value q 0 of vector q obtained using some heuristic approach. This algorithm forms a sequence of vectors from Q, such that each subsequent vector differs from the previous vector by exactly one of its components. The components which values have been changed are considered as fixed and are not altered subsequently. The selection of the next vector of the sequence at the current iteration is performed as follows. For the current vector q c , the subset Q(q c )Q of vectors that differ from q c by one of its non-fixed components is constructed. For each vector qQ(q c ), sub-problem В(q) is solved. As the next vector of the sequence, the vector qQ(q c ) that corresponds to the minimal value of the function H(q)= * (q) +G10(q) in these subproblems is selected. The component by which vectors q and q c differ is considered as fixed. The number of vectors in subsets Q(q c ) from iteration to iteration decreases from |W| to 1. Accordingly, the number of sub-problems В(q) to be solved is also reduced. At each iteration we get (in general) a new improved vector qQ. The algorithm terminates when either the value of H(q c ) is not decreased, or the subset Q(q c )=. The obtained value of q c is taken as the solution of problem C. The total number of sub-problems В(q) to be solved for calculation of function H(q) for different q does not exceed 0.5(|W| 2 +|W|).

Below the scheme of the algorithm MSFV is presented, where:

- is a set of wW with fixed values of component qw for current vector q c ; q (q,w) is a vector from Q that differs from vector qQ only by the component qw.

Algorithm MSFV:

Step 0. Assign q c  q 0 , Y c  H(q 0 ), .

Step 1. If =W then q c is a new solution of problem С. Else

Step 2. Find w * =argmin{H( q (q,w))|wW\}. If Y c Y * = H( q (q,w * )) then assign =W and go to Step 1. Else assign q c = q (q,w * ), Y c =Y * , ={w * } and Step 2 is repeated.

The algorithm MSFV can be repeated with a new initial value q 0 . As such a value, in particular, the current solution obtained earlier can be used. The described algorithm MSFV can be evolved by means of selection at each iteration simultaneously several perspective components of current vector q for their fixing accordingly to the values of function H(q) obtained.

A real life example of the design Problem A is considered in Section 5.

Industrial example

Input data

As an illustrative example, we present here a fragment of machining process for a family M={1,2,3,4}

of parts processed at a 6-position rotary transfer machine which is a part of a transfer line. This fragment considers the features (faces and holes) of parts from M located at one side of each of these items. The family M of parts and their features to be machined at this machine are depicted in Figure 4. The dimensions of these features are given in Table 2. The material of all parts is gray cast iron with HB=190.

The parts are machined one by one by sequentially repeated identical subsequences (batches).

A batch =(1,1,2,3,3,4) is composed of 6 parts: two items of part 1, one item of part 2, two items of part 3 and one item of part 4. The machining the considered features of the parts includes: rough and finish milling for faces 1 and 2, drilling and core drilling for holes 3-7, and spotfacing for all holes with the exception of holes 6. case the cycle of machining one batch  consists of 6 takts and therefore the fixture of each part can be assigned to its own position of the rotary table. The allocation of parts to working positions in each takt of the cycle is presented in Table 1. The time tbi of table movements (idle time) in each takt is equal to 0.2 min.

The parts are installed on the positions so that the maximum number of machining steps for different parts could be carried out by the same tool. Machining steps are combined in operations (in terms of Section 3) so that each operation is executed by one spindle head. Since the material of all parts is the same we accept that the feed per revolution sjr, the range ] , [ [u1j, u2j] of possible values of rates uj of operations. Thus, in the relations (3) values ijr are the same for all rRj and equal to ij:

ij j pij j pij u C u f     ) ( , ( 24
)
where

    j R r pijr pij C С .
Input data for machining process design are given in Table 2. These data include: operations executed at each position for each part; tools and their parameters; parameters of relation ( 2) for respective machining steps; cost and time spent for replacement of each tool. In Table 2, the following notation are used:

-Ljrd, ljrd, tjrd, Bjrd are the working stroke, the cutting length, the depth of cut and the machining width for tool r in operation j when machining part d, respectively;

-Djr , zjr and sjr are the diameter, the number of teeth (for cutter) and the feed per revolution of tool r in operation j, respectively;

-u1j, u2j are the lower and upper bounds of the range for the rate of operation j;

-v1jr, v2jr are the lower and upper bounds of the range of cutting speed for tool r in operation j; So in each of positions 4, 5 and 6 two operations (i.e. pairs of operations {3,4}, {5,6} and {7,8} respectively) are executed. Each such a pair of operations can be aggregated into the respective operation block. Thus (see Section 3), the operation set is J={1,2,…,8}, and the family of potential operation blocks is W={w1={3,4}, w2={5,6}, w3={7,8}}, hence possible options of aggregation of operations are presented by the vector q =(q1, q2, q3)Q and |Q|=8.

Each operation block wW is to be executed by one multi-spindle head with common driver, while the disaggregated execution of the respective operations should be performed by two individual spindle heads with their own drivers.

The parameters Gpl(q) in the relations (1) for the four different options O1, O2, O3, O4 of annual (batch production) plan and for all feasible qQ are given in Table 3. In this table T 0 is a maximal feasible value of cycle duration for the respective annual plan. It is assumed that values of parameters G11(q) and G21(q) do not depend on annual plan.

Table 3. Parameters Gpl(q) of functions 11(q,u) and 21(q,u)

Ok/T 0 q (0,0,0) (0,0,1) (0,1,0) (0,1,1) (1,0,0) (1,0,1) (1,1,0) (1,1,1) 10000/ 20.33 G10(q) ($) G20(q) (min) 36400/ 5.58 G10(q) ($) 1.36 1.4 1.4 1.452 1.4 1.452 1.452 1.497 G20(q) (min) 0.26 0.273 0.273 0.28 0.273 0.28 0.28 0.289 38900/ 5.22 G10(q) ($) 1.274 1.316 1.316 1.358 1.316 1.358 1.358 1.4 G20(q) (min) 0.25 0.263 0.263 0.27 0.263 0.27 0.27 0.278 39500/ 5.15 G10(q) ($) 1.255 1.296 1.296 1.3378 1.296 1.3378 1.3378 1.3794 G20(q) (min) 0.24 0.252 0.252 0.259 0.252 0.259 0.259 0.266 Ok, k=1,2,3,4 G11(q)($/min) 0.7 0.711 0.711 0.722 0.711 0.722 0.722 0.733 G21(q) 1.1 1.103 1.103 1.106 1.103 1.106 1.106 1.109

Table 3 was obtained under the following assumptions. The service life of the transfer machine is 7 years. The number of machine operators is 1 and his labour rate is 7 $/hour. The number of working hours per year is 3987 for 2 shifts per working day. The availability coefficient of the transfer machine is 0.85. The overhead rate is 3.3 (taking into account other staff, general running costs and others items). The average utilization rate of the total engine power of the transfer machine is equal to 0.75. Investment costs Z1(q) of the rotary machine for different aggregation options qQ, the cost Z2(q) and time Z3(q) for maintenance of the rotary machine per unit of operating time, the total engine power Z4(q) of the rotary machine and the energy cost Z5(q) per unit of operating time are given in Table 4. Annual cost of depreciation of the production area and other similar items is equal to 6 700 $ for all aggregation options of the rotary machine.

Table 4 Initial data for determining parameters Gpl(q) q=(q 1 ,q 2 ,q 3 ) (0,0,0) (0,0,1) (0,1,0) (0,1,1) (1,0,0) (1,0,1) (1,1,0) (1,1,1) Z1(q) ($) 300 000 311 500 311 500 323 000 311 500 323 000 323 000 334 500

Z2(q) ($/

Optimization results and discussion

In Table 6, the results of sub-problem B(q) solution for different options of qQ and plans O1, O2, O3 and O4 are presented. As can be seen, the optimal value of the objective function Ф1(q,u) for the plan O1 is achieved for the aggregation option q=(0,0,0); for the plans O2, O3 and O4 the optimal aggregation option is q=(1,0,0). For the plan O4, the gain when selecting the aggregation option q=(1,0,0) is more than 6.8% compared to q=(0,0,0).

The optimal values ) ( * * q j u and ) ( * * q j S of operation rates uj and feeds per minute Sj=1/uj, jJ, for the optimal aggregation options q * (Ok) for different plans Ok are presented in Table 7.

The optimal values )) ( , ( * * * * q q j jr u v of cutting speed vjr for all tools rRj for the optimal values q * (Ok) and operation rates * j u (q * ) are presented in Table 8.

Table 6. The results for different annual output and aggregation options q (0,0,0) (0,0,1) (0,1,0) (0,1,1) (1,0,0) (1,0,1) (1,1,0) (1,1,1) O1 Ф1(q,u * (q)) 9.2874 9.486 9.4923 9.69 9.3191 9.51 9.524 9.715 Ф2(q,u * (q)) 20. 33 20.376 20.376 20.414 20.376 20.414 20.414 20.444 O2 Ф1(q,u * (q)) 5.6917 5.766 5.7723 5.8587 5.5991 5.6772 5.692 5.7635 Ф2(q,u * (q)) 5.58 5.5966 5.5966 5.607 5.5966 5.607 5.607 5.612 O3 Ф1(q,u * (q)) 5.736 5.784 5.834 5.879 5.5181 5.5836 5.6025 5.6675 Ф2(q,u * (q)) 5.22 5.2366 5.2366 5.2472 5.2366 5.2472 5.2472 5.2588 O4 Ф1(q,u * (q)) 5.8862 5.8804 6.0202 5.9893 5.5096 5.57 5.5958 5.6552 Ф2(q,u * (q)) 5.15 5.1656 5.1656 5.1762 5.1656 5.1762 5.1762 5.1868 The models and methods proposed in this work determine optimal design solutions for each specific production system and situation (data).

The results obtained using the proposed models and methods for this use case (and other test cases studied by the authors) lead to the following observations:

1. The optimality of the options for aggregating operations depends on the required annual plan. With its increasing, the positive effect of aggregated execution of some potential operation block is reduced, since the decrease in the unit investment cost is overlapped by the increase in unit operating costs due to common rate for all operations of this block (i.e. non-optimal operation rates for each operation separately).

2. A given annual plan limits the ability of aggregated execution of some blocks due to narrowing the ranges of the possible common operation rates for the operations of these block.

For the considered case study, the maximal productivity 41300 batches/year (i.e. the lowest possible value of the total cycle time T 0 =4.92 min) is achieved for the completely disaggregated option q=(1,1,1). The maximal productivity for the completely aggregated option q=(0,0,0) is only 39570 batches/year (T 0 =5.139 min).

3. The effect of aggregation of operations the less, the more the number of different features to be machined by the potential operation block and the greater the difference in parameters (in particular, diameters and lengths) of these features.

4. For an aggregation option that is optimal for some annual plans, a range of annual plans for which this option remains optimal can be defined. In particular, when the plan is less than a certain "boundary" one, the aggregated option for all potential blocks becomes preferable.

These observations are in good agreement with the properties of rational design solutions for this class of production systems.

Conclusion

A lot of processes in different application fields (not only manufacturing systems) can be described as sequential execution of a collection of some intersecting operation sets. In this paper, such a class of problems is considered on an example of a problem of structuralparametric optimization of the manufacturing processes of multi-product batch machining on multi-position transfer lines composed of rotary machines is considered. A mathematical model and a method for solving a rather wide class of problems of joint optimization of aggregation of operations of a given collection and the rates of operation execution is proposed. The proposed mathematical model and method can be used for such problems in other applications.

The model is formed in terms of mixed integer nonlinear programming and a two-level decomposition scheme to solve it is developed. The upper level sub-problem of the proposed decomposition scheme consists in selecting an aggregation option of operations into blocks.

The lower level sub-problem is to determine the execution rates of all operations for fixed aggregation option. The method of approximate solution of the first sub-problem is based on the combination of heuristic methods and a special version of the method of sequential fixing of variables. A widespread in practice special case of the lower level sub-problem is when the cost and the time spent for each of operations are convex functions of their rates. The method proposed for its solution is based on approximation of this problem by a linear programming problem.

The problem statement and its mathematical model are illustrated with one real life design problem for spindle head aggregation/disaggregation options in machining environment for the design of a rotary machine. The experiments have confirmed very good performance of the proposed methods. This is a general approach which can be applied to different problems of this type in different real life application domains. Similar problems may arise for example at the design stage for various production systems (in particular, assembly/disassembly lines, lines for testing/repairing complex equipment, etc.) as well as for organizations and service systems.

The promising areas of further research include the following:

 studying a wider class of problems when:

-a partial aggregation of operations in blocks is allowed (in particular, potential blocks of one position can intersect);

-the opportunities for aggregation and disaggregation of operations at positions are limited by certain additional conditions (in particular, there are restrictions on the number of blocks of operations at some positions);

 developing effective methods for exact and approximate solution of the original problem with non-convex functions of cost and time of operations on their execution rates;

 developing an iterative scheme for solving the original problem, involving sequential approximation refinement relations according to the previously obtained solutions;

 developing methods to determine the stability region of solutions;3  show the applicability of the approach in many other real life industrial domains.

Disclosure statement

No potential conflict of interest was reported by the authors.

Figure 1 .

 1 Figure 1. An example of part allocation in the first takt for the first 5 positions

S

  for operations j1 and j2 are individual. In the second case, these operations have common working stroke Lwd = max{Ljd|jw}= Figure 2. Disaggregated (a) and aggregated (b) execution of operations j1 and j2

  tool r machines only the part dij. The value Nijr(uj)= given machining length of machining part dij by tool rRj, and 0  ij jrd l

Figure 4 .

 4 Figure 4. The family of parts to be machined

  cutting speed vjr as well as parameters of life time in the relation (2) for each tool r are the same for all machined parts. For simplicity, we assume that 1

  parameters in the relation (2) for tool r when machining part d;

Table 1 .

 1 Allocation of parts to positions in takts of a machining cycle

				Positions
	Takts	1	2	3	4	5	6
	1	1/1 6/4	5/3	4/3	3/2	2/1
	2	2/1 1/1	6/4	5/3	4/3	3/2
	3	3/2 2/1	1/1	6/4	5/3	4/3
	4	4/3 3/2	2/1	1/1	6/4	5/3
	5	5/3 4/3	3/2	2/1	1/1	6/4
	6	6/4 5/3	4/3	3/2	2/1	1/1

Table 5 .

 5 Parameters ij С 1  and ij С 2  (coefficient 10 -10 common for all values is omitted)

	hour)	4	4.15	4.15	4.3	4.15	4.3	4.3	4.45
	Z3(q) (hour)	0.1	0.103 0.103	0.106	0.103	0.106	0.106	0.109
	Z4(q) (KWh)	76	80	80	84	80	84	84	88
	Z5(q) ($/hour)	7.8	8.2	8.2	8.6	8.2	8.6	8.6	9
	Parameters pij С in the relations (24) for p =1,2, iI, jJi are given in Table 5.
	i		1				2
	1 С 1  82.7 129.9 3.62 5.049.2127.6 1.3 1.57116.5 100.8 3.62 5.04 4.61 27.6 1.3 1.57 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 j ij
	ij С 2  5.51 8.66 1.81 2.52 4.6 13.8 0.65 0.79 7.77 6.72 1.81 2.52 2.3 13.8 0.65 0.79
	i		3				4
	j С 1  116.5 141.9 3.62 3.4 4.6127.6 0.65 1.57116.5 141.9 7.24 5.04 4.61 27.6 0.65 1.57 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 ij
	ij С 2  7.77 9.46 1.81 1.7 2.3 13.80.3240.79 7.77 9.46 3.62 2.52 2.3 13.8 0.3240.79
	i		5				6
	j С 1  97.0 141.9 7.24 5.049.2127.6 0.65 1.08 97.0 129.9 7.24 5.04 9.21 27.6 1.3 1.57 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 ij
	ij С 2  6.47 9.46 3.62 2.524.6113.80.3240.79 6.47 9.46 3.62 2.52 4.61 13.8 0.65 0.79

Table 7

 7

	. The optimal values	u	( * * q j	)	and	S	( * * q j	)	of operation rates uj and feeds per minute Sj
	Output j	1	2			3			4	5	6	7	8
	O1, q * (O1)	* j u 0.0020051 0.0023865 0.0095468 0.0095468 0.0267252 0.026725 2 * j S 498.7231 419.0264 104.7468 104.7468 37.4178 37.4178 101.0058 101.0058 0.0099004 0.0099004
	O2, q * (O2)	* j u 0.0020051 0.0023865 0.0089628 0.0128697 0.0267252 0.026725 2 * j S 498.7231 419.0264 111.5719 77.7019 37.4178 37.4178 107.5872 107.5872 0.0092948 0.0092948
	O3, q * (O3)	* j u 0.0020051 0.0023865 0.0086972 0.0124882 0.0267252 0.026725 2 * j S 498.7231 419.0264 114.9802 80.0755 37.4178 37.4178 110.8737 110.8737 0.0090193 0.0090193
	O4, q * (O4)	* j u 0.0020051 0.0023865 0.0084355 0.0121125 0.0267252 0.026725 2 * j S 498.7231 419.0264 118.5468 82.5594 37.4178 37.4178 114.313 0.0087479 0.0087479 114.313
		Table 8. The optimal values	v	* jr	(	, q j * * u	(	q	*	))	of cutting speed vjr
	Position	2		3						4	5	6
	j	1		2				3			4	5	6	7	8
	r	1	2	1	2 1,2,3,4 1,2,5,6 3,4 1,2,3,4 1,2,5,6 1,2,3,4 1,2,5,6 3,4
	O1	54.4 69.63 82.28 105.3 24.68 24.68 25.11 11.755	15.588	17.246	20.966 20.94
	O2	54.4 69.63 82.28 105.3 26.288 18.308 18.63 11.755	15.588	18.369	22.33 22.31
	O3	54.4 69.63 82.28 105.3 27.09 18.867 19.2 11.755	15.588	18.93	23.01 22.99
	O4	54.4 69.63 82.28 105.3 27.932 19.453 19.794 11.755	15.588	19.518	23.728 23.702

Acknowledgments

The authors thank E.Tsvirko who performed numerical experiments to verify the proposed methods. This work was partially supported by the region Pays de la Loire (Program "Strategical Recrutment"), France.

the set of possible vectors uU for fixed option q of operations jw aggregation, for all wW Gp0(q) the components of cost (p=1) and time (p=2) related to a single cycle of machining  that do not depend on the cycle net duration Gp1 (q) the values of cost (p=1) and time (p=2) per unit of the cycle net duration Epl the components of Gpl(q) that do not depend on aggregation of operations Eplw, eplw the piece of the cost (or time) related to aggregated or disaggregated executing the operations of w respectively p E ~(q) the cost (p=1) or the time (p=2) of maintenance of equipment and its depreciation per unit of cycle duration execution for fixed q tbi the auxiliary time (e.g. duration of idle movements) in takt i T 0 the upper bound of the cycle time of the batch  processing Rj the set of tools executing the operation jJ Ljrd, ljrd, tjrd, Bjrd the working stroke, the cutting length, the depth of cut and the machining width respectively for the tool r in the operation j when machining the part d Djr , zjr , sjr the diameter, the number of teeth (for cutter) and the feed per revolution respectively of the tool r in the operation j u1j, u2j

the lower and upper bounds of the range of operation j rate v1jr, v2jr the lower and upper bounds of the range of cutting speed for the tool r in the operation j the rate of the block w of operations (qw=0) qw the variable indicating the manner of execution of all operations from subset w: qw=0 if they are executed in aggregate manner and qw=1 otherwise q the vector (qw|wW) of the components qw, wW u the vector (uj|jJ) of rates uj of operations jJ J 1 (q) the subset of operations executed in disaggregate manner for fixed qQ W 0 (q) the subset of operation blocks from W executed in aggregate manner for fixed qQ

the subset of operation blocks that include operations executed in takt i u(q) the vector (uj|jJ 1 (q)) of rates of operations jJ 1 (q) u(q) the vector (uw|wW 0 (q)) of rates of operation blocks wW 0 (q) iw the volume of potential operation block wW executed in takt iI;

the optimal rate of the operation j for fixed q

the optimal feed per minute of the operation j for fixed q q * (Ok) the optimal vector qQ for given production plan Ok

)) ( , ( * * q q j jr u v the optimal value of cutting speed vjr for fixed q q 0 the initial value of vector q from which the algorithm MSFV starts q c the current value of vector q in the algorithm MSFV Q(q c ) the sequence of vectors from Q that differ from q c by one of its non-fixed components  the set of wW with fixed values of component qw for current vector q c q (q,w) the vector from Q that differs from vector qQ only by the component qw B(q), C

the sub-problems in the decomposition scheme of the problem A Functions fpij (uj) the cost (p=1) and time (p=2) of operation j in takt i (i.e. when machining the part dij) related to the consumption of tools per one cycle of machining the batch  for fixed ujUj 1(q,u) the total cost for machining one batch  of parts 2(q,u) the total time for machining one batch  of parts 1(q,u) the total cost for machining one batch  of parts minus G10(q) 2(q,u) the total time for machining one batch  of parts minus G20(q) ) ( ~j pj u f the functions of the cumulative cost (p=1) and of the cumulative time (p=2) respectively for operation jJ on its rate uj in single execution of one cycle of batch  machining ) ( ˆw pw u f the functions of the cumulative cost (p=1) and of the cumulative time (p=2) respectively for operation block wW on its rate uw in single execution of one cycle of batch  machining )) ( ), ( ( ~1 q u q u Θ the objective function 1(q, u) in the subproblem В(q) in terms of u(q), u(q)

)) ( ), ( ( ~2 q u q u Θ the left side function 2(q,u) of the constraint in the sub-problem В(q) in terms of u(q), u(q) ) ( j rd u T ij the tool r life time under assumption that it machines only the parts dij at operation rate uj Nijr (uj) the estimated number of parts dij machined by the tool r during its life time at operation rate uj H(q) the value  * (q) +G10(q), where  * (q) is the optimal value in the sub-problem В(q) for given q