Kai ; Cheng

Richard J Bateman
email: rjbateman@clara.co.uk

Extending the Product Portfolio with 'Devolved Manufacturing': Methodology and Case Studies

Keywords: E-MANUFACTURING, RAPID PROTOTYPING, RAPID MANUFACTURING, MASS e-Manufacture, rapid prototyping, rapid manufacturing, mass-customization, devolved manufacture

  L'archive ouverte pluridisciplinaire

Introduction

In the last decades of the twentieth century the development of computer numerically controlled (CNC) machinery and robotic manufacturing equipment has led to substantial increases in efficiency of manufacturing. At the same time, the evolution of new manufacturing methods, tools and systems (Figure 1) has led to changes in manufacturing philosophies from straightforward mass production methods to the latest in agile manufacturing [START_REF] Cheng | e-Manufacturing: Fundamentals and Applications[END_REF]. Although not always the case, key agents for slow change in manufacturing tend to be economic or socio-political factors whilst fast changes are usually driven by new technologies. Technology driven changes in manufacturing can arise from the development of entirely new technologies like say, lasers which enables some completely new manufacturing method or by the development of related systems (like IT) which allows the realisation of a manufacturing methodology which may have been around for years waiting for the technology to 'catch up'. If the new technology leads to significant changes in cost reduction or production efficiency then it will generally become the dominant method.

Periodically, the development and availability of some new technology(s) coincides with developments in other areas to give 'synergistic' opportunities to approach manufacturing in a novel and previously 'unrealizable' manner.

The evolution of the Internet and/or World Wide Web (WWW), the new manufacturing concepts in Mass Customization (MC) and current developments in Rapid Prototyping (RP) technologies have led to such an opportunity to integrate these three areas. (Figure 2)

Figure 2 -Key areas for integration

The authors have previously used the term devolved manufacture to describe an innovative 'factory-less' approach to e-manufacturing [START_REF] Bateman | Devolved manufacturing[END_REF]. This proposed approach would allow organisations to offer their customers the opportunity to more directly design items (in line with the principles of mass customization) using a web-based system and then have their design 'manufactured' at one of a network of local 'high street' rapid manufacturing (RM) facilities -which they can then go along to and pick up their 'creation'.

In this concept, the manufacturing is literally 'devolved' downstream to the customer, dispensing with the need for centralised manufacturing facilities and inherent distribution issues.

Literature Review

The Internet/WWW

The history and continuing development of the Internet from its beginnings in 1957 at the United States Department of Defence Advanced Research Projects Agency through to the present day is well documented in many places as is the later development of the World Wide Web (WWW) [START_REF] Berners-Lee | Weaving the Web: the Past, Present and Future of the World Wide Web by its Inventor[END_REF].

Rapid Manufacturing Technology

Movements to speed up the product development cycle have lead to the introduction of a series of technologies (e.g. CAD) aimed specifically at shortening the design phase of the development cycle. Now, a group of technologies collectively known as Rapid Manufacturing (RM) have been developed to shorten both the design and production phases, and promise to revolutionise many conventional manufacturing processes.

These technologies are developed from Rapid Prototyping (RP) technologies and are generally categorized into two types -additive and subtractive [START_REF] Kai | Rapid Prototyping Principles and Applications in Manufacturing[END_REF]. The subtractive type essentially begins with a lump of material and by some process (milling, spark erosion, laser, etc.) carefully removes small amounts until the end product is revealed. The additive type creates the item by carefully 'assembling' small amounts of material in layer-by-layer fashion into the whole product. The technologies used basically fall into three groups [Grover, 2002]: (i) liquid monomers which are cured (e.g. by laser) layer by layer into solid polymers, (ii) powdered materials that are bonded (e.g. by heat or adhesive) layer by layer, (iii) layers cut from sheet material laminated together to form the solid object.

The process has common key characteristics whichever method is used. -geometric modelling to create a computer model of the object and define its enclosed volume, followed by tessellation of the geometric model where the CAD model is converted into a format that approximates its surfaces by multiple facets (usually triangles or polygons) stored in an STL format file, then the slicing of the model in the STL file into closely spaced horizontal layers -The sliced model is then used by whichever technology to create the object in a layer by layer fashion.

Various methods exist including the sintering (melting together) of powered plastic or metal, solidifying liquid polymers by use of laser or ultra-violet light or adding small amounts of molten material which then solidifies. Various manufacturers like 3D systems, the Z-Corporation and Stratys, etc. produce systems with different materials, machine capacity and accuracies, allowing the creation of functional prototypes, concept models or moulds depending on the users requirements.

Most of these makers would undoubtedly argue that their machines should be regarded as mature technology (at least in the field of prototyping and model making) but the same cannot be said if one views the technologies as mainstream manufacturing technology. Much of the current research and development efforts of rapid prototyping system manufacturers is now focussed on the development of their technologies to create practical and economic rapid manufacturing machines.

Whilst the current generation of machines struggle to overcome problems of cost, speed and materials, the next generation may well tick all the boxes on the wish list of manufacturers the world over. However, in addition to being smarter/faster/cheaper replacements for existing manufacturing technologies, these new machines will provide opportunities for organising manufacturing activities in new, innovative and previously undreamt of ways.

Mass Customisation

Whilst the drivers for manufacturing processes to become leaner, more efficient and more agile may well be economic and competitive forces, such developments may also provide new opportunities. The mass customisation (MC) approach -first used by [START_REF] Davis | Future Perfect[END_REF][START_REF] Davis | Future Perfect[END_REF] and then expanded by Pine in his 1993 book [START_REF] Pine | Mass Customisation: The New Frontier in Business Competition[END_REF] and then further developed by others [START_REF] Anderson | Agile Product Development for Mass Customisation[END_REF]] -gives such an opportunity.

An exact definition of what Mass

Customization is (or is not) has yet to be agreed, with some researchers [START_REF] Duray | Approaches to Mass Customization: Configurations and Empirical Validation[END_REF] maintaining that "extant literature has not established good conceptual boundaries for mass customisation", but the definition proposed by Tseng and Jiao [START_REF] Tseng | Mass Customization[END_REF] of mass customization as " … the technologies and systems to deliver goods and services that meet individual customers needs with near mass production efficiency …" is often used.

At its simplest, mass customisation allows the customer to effectively 'design' their own product by selecting from a range of pre-defined sub-units which are then combined into the customised product. This approach effectively integrates the customer into the design process (in fact some writers on mass customisation sometimes call the customer the 'co-designer').

To be economically viable, the manufacturing systems used need to be configured to allow the greater range of possible outcomes to be produced as close in efficiency to dedicated mass production techniques and machinery.

Researchers like Davis and Pine prophesied the adoption of the mass customization approach into general manufacturing with the advent of new manufacturing technologies like CIM and flexible manufacturing systems, but to date the (successful) take-up has lagged behind these early predictions.

Research based on 250 'mass customizing' companies [Piller and Sotko, 2001] suggests that this time lag is due to the lack of appropriate technologies to handle the large amounts of information flows connected with mass customization, and that new Internet based technologies will go some way to enable the successful implementation of mass customization in more and more consumer markets.

From this research they generate two conclusions: (i) Every interaction between the customer and the supplier generates a high level of data (when compared to traditional mass production) making the value added directly related to this customer datatherefore mass customization should be seen as more closely related to e-business and the new possibilities connected with the Internet economy, (ii) Mass customization cannot be based solely on flexible manufacturing technologies, but must also include developments of material products and customized services into customized 'bundles'.

To support the identification of potential mass customization bundles, MacCarthy et al. [MacCarthy, 2002] distinguish between a number of types of customization including; dimensional fit/size, hardware functionality, software functionality, property of the whole product, quality grade, quality level, aesthetics and style, identification and personalisation, literature, packaging and service customization. They highlight the crucial need to identify product areas where customers really value choice and differentiation and thus where the mass customization approach is really appropriate by the use of Key Value Attributes (KVAs).

Although the undoubted benefits of cheap, fast two way communication via the Internet/WWW has revolutionised business by providing access to world wide markets previously inaccessible to all but the largest companies, it then brings with it problems of order fulfilment -i.e. however quickly the product can be manufactured, it still has to be delivered to the customer. Research by MIT [Crespo de Carvalho, 2000] and the University of Westminster [START_REF] Allen | Transport Studies Group A framework for considering policies to encourage sustainable urban freight traffic and goods/service flows[END_REF] suggests that despite the improvements in logistics systems, increases in congestion and associated transport costs could negate gains made in the design and production phases of manufacturing. In an attempt to overcome some of these problems, but still maintain gains from mass customization, Reichwald et al [START_REF] Reichwald | Economic Evaluation of Mini-Plants for Mass Customisation: a decentralised setting of customercentric production units[END_REF] have developed an innovative concept of 'mini-plants' (Figure 3).

The basic principle of this concept is that the manufacturers production facilities are split into a network of small, scalable production units which are geographically close to the customer, but contain all the necessary equipment, personnel, etc. to for 'manufacturing', sales, distribution and customer service.

Crucial features of this approach are that research and development activities take place within the network of mini-plants, rather than being centralised, and information is actively exchanged between the mini-plant 'nodes' within the network.

Methodology

Many researchers are currently working on many mass customization based projects in a wide range of manufacturing and service industries and mass customization is a growing area of research.

It is generally accepted that today's customers are 'smarter', more demanding and are seeking more individualized and personalized products [START_REF] Glazer | Winning in smart markets[END_REF]. Mass customization is one approach which may provide manufacturers with the 'tools' and methods to meet these changing consumer demands.

The authors concept of devolved manufacturing, in which manufacturing is literally 'devolved' downstream to the customer, dispenses with the need for centralised manufacturing facilities (and inherent distribution issues) or even 'mini-plants' -which although they will go some way to moderate distribution problems by being physically closer to the customer, still require the same personnel, premises, manufacturing and storage facilities 'in miniature'. Devolved manufacturing (Figure 4) should be thought of as a 'factory-less' approach to e-manufacturing, which at the moment is probably not feasible due to internet and rapid manufacturing technology limitations. However, the point of this research is to demonstrate that the concept is valid -despite needing to wait until the technology 'catches up'! The next section describes two case studies how the devolved manufacturing concept might be implemented either as (i) an 'internal' extension to an existing small company system, or (ii) as a web-based 'virtual organisation' allowing the customer almost total creative design control over the product.

Example Application Cases

Case Study One -Clutch Ability Limited (CAL)

Case Study One describes the extension of an 'in-house' system for an existing small (semi-fictitious) company Clutch Ability Limited (CAL) which specialises in the development and provision of specialist high performance clutches for race and rally cars. The range of clutches offered by the company is defined by the size of the market and only those models which fit engine/gearbox combinations commonly used in the race/rally arena are economically viable for sale since these items are relatively highvalue (£300-750) and therefore represent a large investment for stockholding for such a small company.

The function of an automotive clutch is to allow the transfer of the rotation developed by the crankshaft of the engine through to the gearbox input shaft. The clutch allows a smooth engagement of a spinning engine to a non-spinning transmission by controlling the slippage between them. A typical racing clutch is an assembly of several distinct parts (Figure 5) each with a specific function and can have between one and four friction plates. The key factor in determining whether the clutch assembly will fit any particular engine/gearbox configuration is 'shape of the central hole' (Figure 6) where the splined end of the main input shaft of the gearbox runs through the hub of the friction plate(s). This is the key interface between the gearbox and the clutch. Splines are essentially integral keys spaced uniformly around the outside of the shaft and the inside of the hub and are used in cases where there would be too much torque for single key to handle. Splines may be either straight sided or involute. Straight sided splines should conform to the Society of Automotive Engineers (SAE) standard for straight tooth splines and involute spline dimensions and tolerances have been standardised with American National Standards Institute (ANSI) standards ANSI B92.1-1970 (R1982) for involute splines and ANSI B92.2-1980 for metric module involute splines. Different manufacturers use different spline arrangements but almost all modern gearbox input shafts have involute splines since they are typically stronger, more self-centering and are easier to cut and fit. The teeth have a profile similar to standard gear teeth with around 50% of the depth.

Whilst the use of a modern Computer Aided Design (CAD) system allows design of the different spline patterns with 'relative' ease, the operation of such a system requires a fair bit of expertise and a small company which deals primarily with the selection and supply of pre-manufactured solutions could not justify the employment of a CAD specialist for the small number of customers who need a solution different from those normally stocked by the company.

However the standardisation of the shape and positioning of the required spline pattern means that relatively straightforward algorithms can be developed to manipulate the central features of a standardised CAD model of the friction plate hub. Only a few key dimensions are required to correctly create an 'appropriate shaped hole' (Figure 7) in the existing CAD model -since all other dimensions relating to how the hub fits to a standard friction plate (external diameter, thickness, rivet hole size and number, 'level of fit' of splines, etc.) remain fixed -to ensure the hub can be assembled into the final product. Use of appropriate modification algorithms mean that these few dimensions could be input to via a simple data entry screen and used to drive a specially written computer programme which will modify a base CAD model of the friction plate hub changing only the centre spline pattern to create a new CAD model of the required hub. This can then be inspected using a simple 3D browser and if fit for use sent off electronically to be manufactured. This scenario has two advantages for the company -first it does not suffer the relatively high costs (for a small company) of CAD programmes and second requires no specialist CAD knowledge of the normal staff at the company.

Manufacturing Issues

The usual method of manufacture for a component like the friction plate hub with internal splines is by 'broaching'. This is a well-known method of machining using a specialist broaching machine which moves a stepped multiple tooth cutting tool in a linear motion relative to the part. The tool is passed repeatedly through the centre hole when more and more material is removed until the splines become sufficiently well defined. This process produces good surface finish and close tolerances but has the disadvantage that for each different spline pattern a different (and generally very expensive to manufacture) broach is required. This means that manufacture of individual items or small batches is prohibitively expensive.

The Sequence of Events in the System.

The standard part of the Clutch Ability Limited (CAL) system is an access based database system used to facilitate the day-to-day running of the company and contains the type of functions one would expect of this type of system -e.g. storage and searching of product, stock and customer details, business transactions and invoice creation and printing, stores and re-order management, etc. as well as the usual housekeeping backup and data security functions.

The additional 'customization' part of the system is designed to allow salespeople to input the few necessary parameters into a simple data entry screen. This then triggers a computer programme which modifies a standardised base CAD model of a friction plate hub with the appropriate dimensions of the required internal spline pattern. The model can then be viewed by the operator using a 3D browser. When the operator is satisfied that the model is correct, it can be emailed directly to the chosen local 'rapid manufacturing' company for manufacture. Once made, the hub is freighted back to CAL for attachment (riveting) to the friction plate. The entire assembly can then be delivered to the customer.

Figure 8 shows the sequence of events in the Clutch Ability Limited (CAL) system which is followed to create a customized friction plate hub unit in accordance with customer requirements.

Evaluation of the CAL system

Evaluation of a system is normally performed in two different ways. First is the process of functional testing where the system is tested against a formal test plan and the second part of system evaluation usually takes the form of user testing. The CAL system was subjected to both these testing regimes with many different sets of spline dimensions being input and the resulting CAD model being examined for 'correctness'. As a final test, a small sample of the resulting output CAD files were used to create a physical part. For reasons of cost and convenience the CAD models were processed using the facilities available at the School of Technology at Leeds Metropolitan University. In the case of a real manufacturing outlet, this would now be sent back to Clutch Ability Limited for final assembly onto the friction plate and subsequent dispatch to the customer.

Discussion

The 'customization' function of the system has some validation processes built into the programmes which modify the initial blank CAD model into the required CAD model for the specific customer requirements. However, the final inspection and validation of the CAD model created requires the eye of an experienced operator who would make the final decision on whether model is fit to be sent to manufacturing facility. This process is rather more difficult to test than the normal data handling functions of the simpler parts of the system. The only really effective testing process for the creation of effective parts by a particular rapid manufacturing technology is to use the system to design and then have fully manufactured a representative range of parts which are then inspected and measured and tested for fit on the relevant gearbox input shaft.

The viability of this scenario assumes the presence of appropriate rapid manufacturing machinery, therefore the types of manufacturing issues which might arise will be those which are inherent in conventional manufacturing processes (human error, poor materials, etc.) and the solutions will be the same. One particularly problematic area would be the accurate measurement of the dimensions of the splines -this would probably be best left to staff at the company, rather than allowing customers to provide their own! The overall benefits of this approach to a small company would be to effectively increase the range of products that the company can offer without the attendant increases in manufacturing and stock holding costs normally associated with increase in product range and also without the need for specialist CAD skills amongst staff.

At the time of writing, (realistically speaking) none of the Rapid Prototyping / Rapid Manufacturing processes available have the capability to directly create a finished part with the necessary dimensional accuracy or physical properties (strength, etc.) without at least some post-manufacture 'attention'. However, the continuing development of the capabilities of the various technologies means that this will not always be the case.

Case Study Two -WYDIWYG.CO.UK

Case Study Two describes an implementation of a devolved manufacturing virtual organisation and is centred on web-based company WYDIWYG.co.uk (What You Design Is What You Get!).

The purpose of the wydiwyg.co.uk web site is to allow online customers to access a free simple downloadable CAD type design programme and to use this programme to create their own designs from scratch. Once customers have created their finished design, they decide if they wish to have the object made and if so pay (via credit/debit card) to have the object made at a location chosen from a list of rapid manufacturing outlets available on the site. Alternatively customers may choose a 'blank' model from a number available on the site and then modify this to their own requirements.

Using this web based system allows the customer to create completely original objects without having to buy any expensive third party CAD software package and importantly, to have that object directly manufactured and then be able to collect the finished object from close to where they live -not having to wait to have the object delivered. This aspect of wydiwyg.co.uk may be thought of as its unique selling point (USP) -i.e. the reason why customers would choose this method of getting their objects created over any other method. This method of working may be regarded as a win-win scenario for all parties concerned:

• the customer gets the capability to design and create objects (in their own time and at their own pace) that they might find it difficult to have made by other methods, • the manufacturer makes only to order, and then only when payment has been made (so no capital is tied up in stock and warehousing, etc.) • society in general benefits by zero waste and little or no environmental concerns over transport and delivery.

Technical Issues

As outlined earlier, this case study is developed along the lines of a virtual organisation, so following this path, responsibility for any functions which can be performed (in an economically viable manner) by an appropriate third party organisation will be 'distributed' accordingly. Figure 10 shows the required 'components' needed for the wydiwyg web site. Whilst the selection of an ISP host and the gaining of the appropriate domain name are relatively simple tasks, the method used for payment along with all the possible security problems is a critical choice. Since wydiwyg.co.uk is an unknown trust levels by the customers would understandable be low at the beginning of the service. In keeping with the principles of a virtual organisation, the payment system of the services of the third party PayPal online payment service organisation provides an ideal solution.

The revenue model for the wydiwyg web site is the so-called 'click-through' model.

The basic principle of this model is that revenue is generated indirectly from levying a small charge on each transaction -rather like the charge for the use of directory inquiries -between the customer and the manufacturing outlet. Additional revenue can also be generated by advertising or 'sponsored links'.

4.2.3

The Sequence of Events in the wydiwyg.co.uk System.

The are essentially three parts to the wydiwyg.co.uk sequence (i) the initial logon to the home page and downloading of the mini-CAD programme, (ii) the use of the mini-CAD programme (offline) to design the customers desired object, and (iii) logging back onto wydiwyg.co.uk to upload the design file, choose a manufacturing 'outlet' in the customers locale, pay for the manufacture, and confirm. Once this third step has been taken, the uploaded CAD file is sent to the chosen outlet for rapid manufacture with a confirmation email being sent when the object is ready for collection. Figure 11 shows the logic flow for the wydiwyg process, and Table 1 the steps through the wydiwyg 'system' screens.

Evaluation of the wydiwyg.co.uk system

The evaluation process for wydiwyg.co.uk system was the same split of functional and user testing used for case study one. Functional testing for the web components included web page type issues like the correct positioning and display of images, text, the correct functioning of hyperlinks, etc. and the download and upload mechanisms for associated files. The mini-CAD programme was tested for self-installation, CAD functions and creation of appropriate files. As a final test (as with case one) a small subset of CAD files were used to create physical objects using the same test facilities.

Figure 12 shows a pair of moulds created using the wydiwyg.co.uk system.

Figure 12 -Pair of moulds created via wydiwyg.co.uk

Discussion

The rationale for the wydiwyg web site service was to demonstrate that such service could operate as a virtual organisation. There are of course, a number of missing parts to the jigsaw which would need to exist for the service to be implemented in the real world.

The wydiwyg web system developed for this project demonstrates that the first part of the process of devolved manufacturing could be made live without too many problems. The pages of the web site (whilst clearly in need of further development and enhancement) contain the minimum functionality to allow users to download a mini-CAD program from the site and then to use this to create CAD files of their own designs. Subsequent uploading of these files and online payment are already functions widely used by online services. The one necessary function for the completion of the wydiwyg concept which does not currently exist (in an appropriate form) is that of rapid manufacturing. Improvements necessary to this area to make the wydiwyg type of service commercially viable include: (i) the development of current generation rapid prototyping machines into real manufacturing machines -by increasing the speed and range of materials available but also by enhancing the usability of the machines themselves to require less operator intervention and (ii) a substantial increase in the number and locations of companies using these technologies (to give the kind of national coverage needed).

Until these developments occur, the wydiwyg type of service will remain too limited an offering to attract sufficient customers to make it economically viable. This does not however detract from the value of the concept, but probably means that it should be considered more as an idea 'awaiting its time'.

Conclusions

Faced with the possibility of implementing some form of devolved manufacturing system, any individual or organisation must always ask the question "Under what circumstances does it make (commercial) sense to do this?" There must be sound economic reasons behind any decisions to start a new business or to move an existing business into a new area and there are many issues to be fully considered.

To fully consider implementing some form of devolved manufacturing many issues need to be considered and major questions answered including:

• how is the implementation to be financed?

• what kind of organisation is most appropriate?

• is the technology available (and sufficiently mature)?

• which strategy is best?

• what are the implications for the design process?

• what are the ethical and legal issues?

The correct strategy, organisation and modus operandi for a new devolved manufacturing implementation is must be determined by the point from which the business is starting. The manner in which a large multi-national organisation would choose to implement a DM approach will almost certainly be different from a brandnew start-up and the capital requirements and available resources will be reflected in this.

There are advantages and disadvantages to adopting a new technology and adopters of technology can generally be categorised as one of five types [START_REF] Rogers | Diffusion of innovations[END_REF]: (i) Innovators -who are willing to take the high risks and high capital investment associated with bringing the idea in; (ii)

Early adopters -who are generally industry leaders and changers of opinion and can serve as role models; (iii) Early majority -not leaders but move when they think the evidence looks like it may be overwhelming (and may be driven by financial imperatives); (iv) Late majority -who where and may still be sceptics, and (v)

Laggards -characterised by traditional ideas and wanting to stick to 'the devil you know'. Some commentators on rapid prototyping technologies [START_REF] Kaempher | Lighting the way for true rapid manufacturing[END_REF][START_REF] Oakham | Rapid Moves[END_REF] suggest that the speedy pace of development in the past few years indicates that the breakthrough point is imminent -however if rapid 'manufacture' technology is to be truly devolved into the High Street, work on the level of automation of current generation rapid prototyping/manufacturing machines will be required to allow either unattended operation or operation by unskilled operator.

The two case studies of this project support the devolved manufacturing concept as 'realizable' -i.e. given the appropriate development in the rapid manufacturing technologies and careful selection of target market place it should be possible to create and implement some form of devolved manufacturing operation.

However, there are numerous strategic, legal and technical issues which must be resolved to ensure a successful outcome. Given the abundance of different possible starting points and subsequent directions for development, each venture will need to proceed on an individual basis to ensure the requisite expertise is found and appropriate questions answered

The high number of strategic, legal and technical issues to be resolved (as outlined in the previous chapter) and the relatively immature nature of current rapid prototyping or rapid manufacturing technologies suggests the difficulty of implementing a successful devolved manufacturing venture at present will be considerable. Step One Entry to the system is through the Main Menu.

Step Two Customer part is searched for on the part database. If it exists ordinary sales proceeds, if not 'customized service' is offered/explained.

Step Four Dimensions are entered into the hub parameter input screen and validated. If OK, then 3D model is viewed

Step Five 3D CAD model of clutch hub is displayed for viewing and visual inspection (using browser).

Step Six If model and dimensions are valid, then outlet (manufacturer) is selected and details and CAD model e-mailed out.

Step Three Requisite dimensions requested and received either direct from customer or by staff measurement of gearbox input shaft. Step Two New users are directed to information on the WYDIWYG concept and given option of downloading mini-CAD program. Existing users can log-in to system directly

Step Three New users download the WYDIWYG mini-CAD design program. At this point they go off-line and begin to design.

Step Four User designs their object using the mini-CAD program. Inbuilt training scheme can be used by completely new users.

Step Five Mini-CAD model of users design is displayed for viewing and inspection using 3D viewer facility.

Step Seven Entry to the web site is through the WYDIWYG.CO.UK home page. Existing users can log-in directly using the 'sign-in' facility.

Step Eight New users register themselves by entering their contact details. These details are then stored in the wydiwyg database and an email confirming registration sent.

Step Nine The user then finds an appropriate outlet -either by searching the clickable map or closest to postcode dialog box.

Step Ten Next the user uploads their CAD model and the order is constructed. Payment is requested (via Pay Pal services).

Step Eleven The user confirms the order details and on clicking 'OK' the data and CAD model is sent to the chosen outlet which emails to confirm.

Final Step

The user is given an acknowledgement of the order with a unique identifier number and asked to print for future reference

Figure 1 -

 1 Figure 1 -Developments in Manufacturing

Figure 3 -

 3 Figure 3 -Customer integration in the creation of product / service bundles

Figure 4 -

 4 Figure 4 -Devolved Manufacturing in the Agile Manufacturing Spectrum

Figure 5 -

 5 Figure 5 -Component Parts of a Typical Competition Clutch

Figure 6 -

 6 Figure 6 -Example Splines at Centre of Friction Plate Hub

Figure 7 -

 7 Figure 7 -Key dimensions for friction plate hub (straight splined only shown)

Figure 8 -

 8 Figure 8 -Using the customization function of the CAL system

Figure 9 -

 9 Figure 9 -Pre-processing of CAD model -calculating machining path

Figure 10 -

 10 Figure 10 -Components required for the wydiwyg.co.uk web site

Figure 11 -

 11 Figure 11 -The wydiwyg.co.uk Process

Figure 3 -Figure 5 -Figure 8 -

 358 FIGURES

Figure 9 -Figure 12 -

 912 Figure 9 -Pre-processing of CAD model -calculating machining path

Table 1

 1 Stepping Through Wydiwyg.Co.Uk System Screens

Table 1 -

 1 Stepping Through Wydiwyg.Co.Uk System Screens

WORD COUNT = 5,975 Page 21 of 21 http://mc.manuscriptcentral.com/tprs Email: ijpr@lboro.ac.uk International Journal of Production Research

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

Agile Manufacturing

Manufacturing

Processes Capability Technology etc.

IT

Integrated Approach

Technology Devolved Manufacturing


Alexandre ; Dolgui
email: dolgui@emse.fr

Brigitte Finel
email: finel@enim.fr

Olga Battaïa

Nikolay Guschinsky

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

Francois B Vernadat
email: vernadat@enim.fr

O Guschinskaya
email: guschinskaya@emse.fr

Balancing large-scale

Keywords: Machining lines, Line balancing, Optimization, Decomposition, Heuristics

published or not. The documents may come

Introduction

Machining lines are widely used in industry [START_REF] Groover | Automation, Production Systems and Computer Integrated Manufacturing[END_REF][START_REF] Askin | A survey of exact algorithms for the simple assembly line balancing[END_REF][START_REF] Hitomi | Manufacturing Systems Engineering[END_REF][START_REF] Dashchenko | Manufacturing Technologies for Machines of the Future 21st Century Technologies[END_REF]. Usually, the design of this type of production systems involves the following three interconnected steps: (1) the selection of necessary operations to be executed at the line; (2) the logical synthesis of the manufacturing process, which consists in grouping the operations into blocks and the blocks into stations (logical layout); and (3) the physical layout and design of equipment (tools, spindle-heads, etc.) depending on the logical layout contained.

This paper concentrates on the logical layout design stage. At this stage, all machining operations as well as essential constraints of physical layout are known. It is necessary to define a partition of all the operations into subsets in order to minimize the number of workstations and spindle heads (pieces of equipment). Such spindle heads and workstations represent a significant investment cost and are used for a long exploitation period. Thus finding a good (and if possible the best) logical layout design decision minimizing their number is a crucial problem.

To minimize the number of workstations and spindle heads as well as the occupied area for the considered line, the operations are grouped into blocks. All operations of the same block are executed simultaneously by one spindle head. All blocks (spindle heads) of the same station are executed (activated) sequentially; all stations are linearly ordered. There are no buffers between stations. The assignment of blocks to a station defines at the same time the order of their activation on the station.

The processing time of each spindle head depends on the parameters (working stroke length and feed rate) of operations assigned to the corresponding block. The station processing time is equal to the sum of block times (for all blocks assigned to this station). The bottleneck station defines the machining line cycle time.

In this paper, the objective function is as follows: The problem considered in this paper extends the well-known Simple Assembly Line Balancing Problem (SALBP). Techniques used to solve SALBP can be found in literature, e.g. (Baybars 1986[START_REF] Ghosh | A comprehensive literature review and analysis of the design, balancing and scheduling of assembly lines[END_REF][START_REF] Erel | A survey of the assembly line balancing procedures[END_REF][START_REF] Scholl | Balancing assembly lines effectively: a computational comparison[END_REF][START_REF] Sprecher | A competitive branch-and-bound algorithm for the simple assembly line balancing problem[END_REF][START_REF] Gadinov | A cutting plane approach for single-product assembly system design problem[END_REF][START_REF] Rekiek | State of the art of assembly lines design optimisation[END_REF].

For the investigated problem, which cannot be directly solved by SALBP methods due to some specificities (groups of operations are executed simultaneously, operations times are not known in advance, criterion include the number of blocks and stations, etc.), two exact optimization methods based on Mixed Integer Programming (MIP) and graph approaches, respectively, were suggested in [START_REF] Dolgui | On Problem of Optimal Design of Transfer Lines with Parallel and Sequential Operations[END_REF], Dolgui et al. 2000, Dolgui et al. 2006a[START_REF] Dolgui | MIP approach to balancing transfer lines with blocks of parallel operations[END_REF]. These methods can be used only for small size problems. For large-scale problems, two heuristic algorithms RAP and FSIC were developed in [START_REF] Dolgui | A Heuristic Approach for Transfer Lines Balancing[END_REF], these algorithms are based on generalizations of the COMSOAL method [START_REF] Arcus | COMSOAL: A computer method of sequencing operations for assembly lines[END_REF].

In this paper, a new heuristic procedure is suggested for large-scale problems. It is based on decomposition of the whole set of operations into several subsets. On the basis of these subsets MIP models are formulated and then solved by a MIP solver. Two ways of MIP models formulation are investigated. One of them treats the obtained subsets independently. The second one aggregates the solution of the previous sub-problems. The experimental results are reported.

The paper is organized as follows. Section 2 introduces some notations and the problem. In Section 3, the decomposition procedure is suggested. In Section 4, experimental results are reported. Conclusion remarks are given in Section 5.

Objective and constraints

An illustration of the type of lines studied in this paper is given in Figure 1. The parts are moved from station to station. On each station there is at least one multiple spindle head with different tools. The time spends on a multi-spindle head depends on the common parameters of their operations (tools). The following parameters of the operations are given before optimization: the working stroke length and the feed rate. The spindle heads of the same station are activated sequentially.

[Insert Fig. 1 about here] The objective of this paper is to investigate a new method for optimal design of logical layout for such lines (several hundreds of operations), i.e. to assign the operations of a given set to subsets corresponding to stations (machines) and to blocks (spindle heads) in such a way that:

• The objective function (1) is as small as possible;

• The specified line cycle time is not exceeded (i.e., the obtained line cycle time is not greater than the specified one);

• All the constraints for machining operations are satisfied.

The following precedence and compatibility constraints are taken into account:

• A partial order relation on the set of all operations to be machined. This defines a set of possible operation sequences (precedence constraints). In this problem when an operation i precedes an operation j, the operation i can be executed before the operation j, or in the same block with j, but the operation j cannot be executed before the operation i.

• Inclusion constraints for blocks and stations, which oblige to perform some groups of operations in the same block or at the same station (e.g., because of a required machining tolerance); • Exclusion constraints for blocks and stations, which forbid execution of some groups of operations within one block or at the same station (e.g., due to design rules or because of manufacturing incompatibility of operations).

Notations

The following notations will be used throughout this paper:

N

given set of operations to be machined; q index of the block, e.g., q=(k-1)n 0 +l for the block l of the station k; q 0 maximal possible value of q, q 0 =m 0 n 0 ;

T

S(k)

set of block indices for the station k; n k number of blocks at the station k;

C(k) cost of the station k with all its blocks, i.e. C(k) = W 1 + k n W 2 ; B q
set of operations of the block q; Q(j) interval of indices q (blocks) where operation j can be potentially assigned (Q(j)=[q -(j),

q + (j)]); K(j) interval of indices k (stations)
where operation j can be potentially assigned

(K(j)=[k -(j), k + (j)]);
e set of operations, element of collection EB, ES , ES or EB ;

X jq a binary decision variable (1 if operation j is assigned to block q and 0 otherwise);

F q an auxiliary variable for determining the time of block q (F q ≥ 0);

Y q an auxiliary variable that indicates if the block q exists or not (Y q ∈{0,1}).

The time t b (N) of a block N ⊆N is determined by the working stroke length L(N) of the corresponding spindle head, and by its feed per minute S(N) and is equal to

t b (N)=L(N)/S(N)+τ b
where L(N)=max{l j |j∈N} and S(N)=min{s j |j∈N}. The time of block N can be also calculated as the maximal value among t ij for all pairs of operations from N (Dolgui et al. 2000):

t b (N)= N j i ∈ , max {t ij } where t ij =max{l i , l j } / min{s i , s j }+τ b . F o r P e e r R e v i e w O n l y The time t s (N k ) of station k is equal to t s (N k )= ∑ = k n l kl b N t 1 ) ( +τ s .

MIP model

Taking into account that station k exists if at least one operation is assigned to block q = (k-1) n 0 +1, the considered problem can be formulated as the following Mixed Integer Program (MIP) and solved using a MIP solver (ILOG Cplex, Xpress MP, …): where i,j∈N.

Min q q q m k n k Y W Y W ∑ + ∑ = = + - 0 0 0 1 2 1 1 * ) 1 ( 1 (2) Subject to: 1 ) ( = ∑ ∈ jq j Q q X (3) ( ) , ) ( ) ( , ' ' ∑ ∑ ∈ ∈ ′ ≤ ≥ j Pred i i Q q q q jq iq j Pred X X q∈Q(j) (4) , q i jq X X = e∈EB, i,j∈e, q∈Q(j) (5) ∑ ∑ ∈ ∩ ∈ = I ) ( ) ( ) ( ) ( , j Q k S q i Q k S q iq jq X X e∈ES, i,j∈e, k∈K(j) (6) , 1 - ≤ ∑ ∈ e X e j jq e∈ EB , q∈ I e j j Q ∈ ) ( (7) , 1 ) ( ) ( - ≤ ∑ ∑ ∈ ∈ e X e j j Q k S q jq I e∈ ES , k∈ I e j j K ∈ ) ( (8) F q ≥ t j X jq , q∈Q(j) (9) F q ≥ t ij (X iq +X jq -1), i<j, q∈Q(i)∩Q(j) (10) ≤ ∑ + ∈ ) (k S q q s F τ T 0 , k=1, 2,…, m 0 (11) Y q ≥X jq , q∈Q(j) (12) 0 1 ≥ - - q q Y Y , q∈S(k)\{(k-1)n 0 +1}, k= 1, 2,…, m 0 (13) 0 1 * 1 * ) 1 ( 0 0 ≥ - + + - n k n k Y Y , k=2, 3,…, m 0 (14)
According to equation (3), each operation of N is assigned to one block only. Inequalities (4) provide that all the predecessors of operation j are assigned either before operation j or in the same block with operation j. Equations ( 5) and ( 6) enforce assignment of any pair of operations i and j of set e∈EB (e∈ES) to the same block (station), respectively. In accordance with equation ( 7), at most 1 e operations of set e∈ EB may be assigned to the same block. Expressions (8) represent the exclusion constraints for assignment of operations to stations. Equations ( 9) and (10) provide that F q is not less than the time of execution of all the operations assigned to the block q. Inequalities (11) provide the desired productivity level, i.e., for each workstation of the line, the station time

∑ + ∈ ) (k S q q s F τ
does not exceed the line cycle time T 0 . In accordance with equation ( 12), the block q does not exist in the line if no operations are assigned to it. Equations ( 13) prevent creation of block q for station k if block q-1 does not exist for this station. Equations ( 14) provide that station k can be created only if station k-1 exists in the line. This model is an improvement of the models suggested in (Dolgui et al. 2000[START_REF] Dolgui | MIP approach to balancing transfer lines with blocks of parallel operations[END_REF]). To calculate q -(j), q + (j), k -(j), and k + (j), a pre-processing procedure has developed in (Dolgui et al. 2000[START_REF] Dolgui | MIP approach to balancing transfer lines with blocks of parallel operations[END_REF].

An industrial example

The problem can be illustrated by the following industrial example.

The part to be machined is shown in Figure 2. It is necessary to machine a plane surface (F) and 8 holes (H1 -H8). The set N consists of 30 operations. The operation parameters are given in Table 1. The precedence graph is given in Figure 3. The desired line cycle time is T 0 = 2.8 min, τ b = 0.2, τ s = 0.4 min, the maximum number of stations on the line is m 0 = 5 and the maximum number of spindle-heads at a station is n 0 = 4.

[Insert Fig. 2 An optimal solution for the assignment of the set N to blocks and stations (12 blocks and 4 workstations) is shown in Table 2. In Table 3 an optimal solution is given for T 0 =2.4, which consists of 6 workstations and 12 blocks. This solution remains optimal until T 0 ≥2.02.

[Insert Table 2 about here] [Insert Table 3 about here]

Decomposition procedure

When (2)-( 14) is a large-scale problem (i.e. more than 70 operations), it is impossible to use MIP solvers directly. A possible solution is to use a decomposition technique that divides the initial set N of operations into several (w) disjoint subsets (Dolgui et al. 2000[START_REF] Dolgui | MIP approach to balancing transfer lines with blocks of parallel operations[END_REF]) and then apply MIP solver in sequential order following the decomposition N 1 , N 2 , …, N w . The global result for the initial problem is obtained at the end of the algorithm after w MIP problems have been solved.

The subset N u is chosen in such a way that all the constraints are not violated. To respect all the precedence constraints, all the predecessors of the operations of the subset N u treated by MIP have to be in this subset or already assigned (during a treatment of an anterior subset): operations of e are in N u ; otherwise, the constraint is not taken into account for N u .

Pred(j)⊆ U u
For the decomposition, the partitioning of the set N is done by a cut of the precedence graph.

First a desired size of each subset (while analyzing the behavior of the MIP model for this kind of problem) is fixed. This choice depends on the initial problem size and on the available time.

The smaller are the subsets, the easier it is to get a reasonable computation time, but more chances exist to reach a solution far from the global optimum.

Two ways are possible to form sub-problems in accordance with the partition N 1 , N 2 , …, N w :

1) Form MIP model for each set N u separately;

2) Aggregate in MIP model for each set N u the solutions obtained by MIP solver for the previous problems.

The implementation of the first approach is relatively simple: all the constraints are adjusted with regard to the subset N u , i.e., a set e is removed from the collections EB, ES, ES and EB if it includes an operation i∉N u ; operations from N\N u are deleted from each set Pred(j), j∈N u . The solution of the initial problem is obtained then by grouping together all the stations and blocks constructed during all the stages.

For the second approach, the same procedure is applied to the subset U u q * (j)/n 0 ] where q * (j) is the optimal assignment of the operation j in the solution and s is the smallest integer value greater than or equal to s. In this case, only assignment of operations from N u is allowable.

Obviously, if the problem ( 2)-( 14) has a feasible solution then there is a partition N 1 , N 2 , …, N w such that both approaches can produce an optimal solution. In most cases the first approach allows finding a feasible solution quickly than the second, since in the first case the dimension of solved sub-problems is smaller. On the other hand, the second approach may produce a solution of higher quality.

The idea of the proposed decomposition algorithm is based on the decomposition of [START_REF] Kilbridge | A heuristic method of assembly line balancing[END_REF], but taking into account the specificity of the problem treated and on the objectives of the decomposition. The decomposition procedure uses parameters MinOp and MaxOp that are the minimum number and the maximum number of operations authorized in a subset (the number of operations must be between MinOp and MaxOp).

First, each operation range is computed based on in the precedence graph. The range of the operations which have no direct predecessor is equal to 1. The range operation i is equal to: Rang(i)= max ( Rang(j), j∈Pred(i) ) + 1, where Pred(i) is the set of direct predecessors of the operation i. Then, the operations of each range are analyzed one by one beginning from the smaller range and they are added to N 1 .

For each added operation the inclusion constraints must be respected. If some of them are not respected, the corresponding operations and the non assigned predecessors are added even if their range is different. When all the operations of a range are treated, the following range is studied. As long as the number of operations in N 1 is less than MinOp the procedure is continued. When the decomposition procedure is stopped, the subset N 1 is reduced taking into account the parameter The performance of the MIP model depends on the parameter m 0 and intervals Q(j). They can be modified in the following way. A lower bound on the objective function of the problem (2)-( 14) 2)-( 14) is known and UB is the corresponding value of the objective function, then m 0 can be refined as m 0 =(UB -W 2 n)/W 1 , where s is the greatest integer value less than or equal to s. As a consequence, intervals Q(j) and K(j) may be tighten.

is equal to W 1 m +W 2 n,
The decomposition procedure can be applied several times and the best solution is kept.

In this algorithm, the FSIC heuristic [START_REF] Dolgui | A Heuristic Approach for Transfer Lines Balancing[END_REF] based on a generalization of the COMSOAL method is used to search a feasible initial solution.

The following notations are used: TR tot the current number of trials;

TR nimp the number of trials that do not improve the current best solution;

C min the cost of the best obtained solution;

C cur the cost of the current solution;

T heur the total available time for solving a sub-problem by a heuristics;

T MIP the total available time for solving a sub-problem by MIP solver;

Algorithm:

Step1. Set C min = ∝, TR tot = 0, TR nimp = 0. Step 2. Set w=1.

Step 3. Generate subset N w and form problem (2)-( 14) for the subset N w in accordance with the parameters MinOp and MaxOp.

Step 4. Run the FSIC heuristics with the available time T heur . If a feasible solution is found then modify m 0 , Q(j) and K(j).

Step 5. Run MIP model. If MIP does not give any solution after T MIP then MIP is stopped. The current MIP solution is compared with the heuristic solution and the best is kept.

Step 6. If there are still some non assigned operations then set w=w+1 and go to Step 3.

Step 7. If C cur < C min then set C min = C cur , TR nimp = 0. Otherwise set TR nimp = TR nimp + 1.

Step 8. Set TR tot = TR tot + 1.

Step 9. Stop if one of the following conditions holds:

a given solution time is exceeded;

TR tot is greater than the maximum number of iterations authorized;

TR nimp is greater than a given value;

C min is lower than a given cost value.

Otherwise go to Step 3.

Tests and comparisons

In order to study the performance of the decomposition procedures described above, 8 data sets were created, each of which contains 10 machining line balancing problems (i.e. 80 problems were tested). The data sets differ by two parameters: the number of operations |N| and the order strength OS of the precedence graph.

Note: the order strength OS is defined as the density of the transitive closure of the precedence graph [START_REF] Scholl | Balancing assembly lines effectively: a computational comparison[END_REF].

Each unique problem was generated at random. The operation times are derived from the uniform distribution (a=10, b=20). The precedence graph is generated at random by adding arcs between randomly chosen vertexes until getting desired order strength. All data sets were solved by Experiments were carried out on Pentium IV, 3GHZ. The obtained results are reported in Table 4. For the presentation, the following notations are used: NO -number of obtained optimums; max ∆ , av ∆ , min ∆ -maximal, average and minimal deviation of the criterion obtained by a method from the best value, respectively; T com -computational time in seconds.

[Insert Table 4 about here]

For the problems with 200 operations, IS method found only some solutions (< 3). So, only the results obtained by AS method are reported in Table 4 for this data set. For all data sets, the decomposition method with independent solving was surpassed by the method with aggregate solving. In the same time, it is impossible to conclude that one of the sets of parameters for aggregate decomposition (AS1 or AS2) is better from the quality of the obtained results. The experiments show that the method performance depends on the characteristics of the problem.

Conclusion

A line balancing problem in machining environment has been discussed. It concerns the machining lines with multi-spindle heads. Each multi-spindle head executes simultaneously a block of operations. In comparison with the standard assembly line balancing problems, the problem addressed has many additional properties and constraints. In this paper, an industrial example of this problem is given.

For small problem of this type, there are in literature exact optimization models based on Mixed Integer Programming (MIP) and graph theory, but these models are time consuming.

  number of stations (multiple spindle machine-tools), n is the total number of blocks (spindle heads), W 1 and W 2 are the weights (relative costs) of one station and of one spindle head in a design decision, respectively.

[

  Insert Fig.3about here] The compatibility constraints are the following. Operations 1 and 2 are not compatible in one position with any other operation from N since they should be executed by a milling machine. All operations for machining H1 are not compatible with operations for H7 due to constraints on minimal center distances. The same type of constraints exists between operations for H2 and H7,H3 and H8, and H4 and H8. Operations 22, 23, 29 and 30 cannot be grouped in one block with any operation since the minimal center distance for these operations is 125 mm. Operations 13 and 16 as well as 18 and 25 have to be executed in one block due to tolerance requirements. Operations 13, 16, 23 and 30 should be executed in the station since they are finishing operations. All the constraints are represented by: EB={{13, 16}, {18, 25}}, ES={{13, 16, 18, 25, 23, 30}}, ES ={{2, 3}, {2, 5}, {2, 7}, {2, 9}, {2, 11}, {2, 14}, {2 17}, {2 24}}, and EB ={{2, 1}, {3, 2}, {4, 3}, {5, 2}, {6, 5}, {7, 2}, {8, 7}, {9, 2}, {10, 9}, {11, 2}, {12, 11}, {13, 12}, {14, 2}, {15, 14}, {16, 15}, {17, 2}, {18, 20}, {19, 17}, {20, 22}, {21, 4}, {21, 6}, {21, 8}, {21, 10}, {21, 13}, {21, 16}, {21, 23}, {21, 30}, {22, 19}, {23, 18}, {24, 2}, {25, 27}, {26, 24}, {27, 29}, {28, 4}, {28, 6}, {28, 8}, {28, 10}, {28, 13}, {28, 16}, {28, 23}, {28, 30}, {29, 26}, {30, 25}, {11, 4}, {11, 8}, {12, 4}, {12, 8}, {13, 4}, {13, 8}, {14, 6}, {14, 10}, {15, 6}, {15, 10}, {16, 6}, {16, 10}, {17, 4}, {17, 6}, {18, 4}, {18, 6}, {19, 4}, {19, 6}, {19, 17}, {19, 18}, {20, 3}, {20, 4}, {20, 5}, {20, 6}, {20, 17}, {20, 18}, {21, 3}, {21, 4}, {21, 5}, {21, 6}, {21, 11}, {21, 12}, {21, 13}, {21, 14}, {21, 15}, {21, 16}, {21, 17}, {21, 18}, {22, 3}, {22, 4}, {22, 5}, {22, 6}, {22, 7}, {22, 8}, {22, 9}, {22, 10}, {22, 11}, {22, 12}, {22, 13}, {22, 14}, {22, 15}, {22, 16}, {22, 17}, {22, 18}, {22, 19}, {22, 20}, {22, 21}, {23, 3}, {23, 4}, {23, 5}, {23, 6}, {23, 11}, {23, 12}, {23, 13}, {23, 14}, {23, 15}, {23, 16}, {23, 17}, {23, 18}, {23, 19}, {23, 20}, {23, 21}, {24, 8}, {24, 10}, {24, 22}, {25, 8}, {25, 10}, {25, 22}, {26, 8}, {26, 10}, {26, 22}, {26, 24}, {26, 25}, {27, 7}, , {27, 9}, {27, 10}, {27, 22}, {27, 24}, {27, 25}, {28, 7}, {28, 8}, {28, 9}, {28, 10}, {28, 11}, {28, 12}, {28, 13}, {28, 14}, {28, 15}, {28, 16}, {28, 22}, {28, 24}, {28, 25}, {29, 3}, {29, 4}, {29, 5}, {29, 6}, {29, 7}, {29, 8}, {29, 9}, {29, 10}, {29, 11}, {29, 12}, {29, 13}, {29, 14}, {29, 15}, {29, 16}, {29, 17}, {29, 18}, {29, 19}, {29, 20}, {29, 21}, {29, 22}, {29, 23}, {29, 24}, {29, 25}, {29, 26}, {29, 27}, {29, 28}, {30, 7}, {30, 8}, {30, 9}, {30, 10}, {30, 11}, {30, 12}, {30, 13}, {30, 14}, {30, 15}, {30, 16}, {30, 22}, {30, 24}, {30, 25}, {30, 26}, {30, 27}, {30, 28}}.

r r 1 =

 1 N for any j∈N u . of N u is also in a subset e∈ES or in e∈EB, then all the operations of e have to be in N u , i.e.: e∩N u =∅ or e⊆N u for any e∈ES and any e∈EB. An exclusion constraint represented by a subset e EB ∈ (or e ES ∈ ) is maintained only if all the

r r 1 =

 1 N and the solution at the last stage is the solution of the problem (2)-(14). To aggregate the solution of the previous problems, additional sets with operations constituting obtained blocks are included into the collection EB. In such a situation a reassignment of old blocks to other stations is possible. Another

  first subset N 1 , and so on for N 2 , …, N w . To add randomness to the decomposition procedure, values MinOpCur and MaxOpCur can be used instead MinOp and MaxOp for generation a subset N u , which are randomly chosen within[MinOp, MaxOp].

  where m and n are lower bounds on m and ∑ bound m can be calculated as max{ k -(j) | j∈N } and the bound n can be determined as max{ k -′ (j) | j∈N } when values k -′ (j) are obtained in the same manner as k -(j) but using n 0 =1 and without inclusion constraints ES. If a feasible solution of the problem (

  , independent solving with MinOp = 10 and MaxOp= 20 ; 2) IS2, independent solving with MinOp = 15 and MaxOp = 25; 3) AS1, aggregate solving with MinOp = 10 and MaxOp = 20; 4) AS2, aggregate solving with MinOp = 15 and MaxOp = 25.

Figure

  Figure 1. A machining line with multi-spindle heads

  about here]

	[Insert Table 1 about here]
	F o r
	P
	e
	e r
	R
	e
	v i e
	w
	O n l
	y

  In this paper, an approach for solving this problem has been tested. This approach is based on an improved MIP model and a new heuristic of its decomposition. Using this algorithm, the initial problem is decomposed into several sub-problems and solving them by means ILOG Cplex solver.Two algorithms of decomposition are tested for randomly generated series of examples from 50 operations to 200 operations. The results are promising. Future research will concern development of heuristics to find "good" partitions in order to decrease the calculation time. A possible way is the use of the COMSOAL based heuristics as FSIC or RAP for a not deterministic decomposition. Another direction is the development of a preprocessing procedure for the aggregation of operations into macro-operations before optimization.

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

Therefore, the generation of "good" design decision for large-scale machining lines (one or several hundred of operations) needs the development of efficient heuristic algorithms.

Table 1 .

 1 Operations and their parameters

	Machined elements	Operation name	Operation number	Working stroke length, mm	Feed rate, mm/min	Execution time, min
	Plane P	Mill roughly Mill completely	1 2	155 155	167.5 146.5	0.93 1.06
	Hole H1	Drill ∅12.5 Spotface ∅20	3 4	35.8 20	52.6 127.6	0.68 0.16
	Hole H2	Drill ∅12.5 Spotface ∅20	5 6	35.8 20	52.6 127.6	0.68 0.16
	Hole H3	Drill ∅12.5 Spotface ∅20	7 8	35.8 20	52.6 127.6	0.68 0.16
	Hole H4	Drill ∅12.5 Spotface ∅20	9 10	35.8 20	52.6 127.6	0.68 0.16
		Drill ∅9.8	11	29.9	57.4	0.52
	Hole H5	Drill out facet ∅12	12	8	68.4	0.12
		Ream a hole ∅10	13	24.1	139.3	0.17
		Drill ∅9.8	14	29.9	57.4	0.52
	Hole H6	Drill out facet ∅12	15	8	68.4	0.12
		Ream a hole ∅10	16	24.1	139.3	0.17
		Drill ∅10	17	57.7	57.4	1
		Enlarge a hole ∅18	18	53.3	68.4	0.78
		Drill out ∅17	19	44.1	68.4	0.64
	Hole H7	Drill out facet ∅22	20	6	68.4	0.09
		Tap a hole	21	24	143.6	0.17
		Bore out roughly ∅29.5	22	24	259.5	0.09
		Bore out completely ∅30	23	12.5	106.3	0.12
		Drill ∅10	24	57.7	57.4	1
		Enlarge a hole ∅18	25	53.3	68.4	0.78
		Drill out ∅17	26	44.1	68.4	0.64
	Hole H8	Drill out facet ∅22	27	6	68.4	0.09
		Tap a hole	28	24	143.6	0.17
		Bore out roughly ∅29.5	29	24	259.5	0.09
		Bore out completely ∅30	30	12.5	106.3	0.12

Table 2 .

 2 An optimal solution for T 0 =2.8

	Station number k	1		2			3				4
	Block number l	1	2	1	2	1	2	3	4	1	2	3	4
	Operations i∈N kl	1	2	17,24 19,26	22	29	11,14,	4,6,	20,27,	18,25,13,	23,30 21,28
							3,5,7, 9	8,10	12,15	16
	L(N kl )	155	155	57.7	44.1	24	24	35.8	20	8	53.3	12.5	24
	S(N kl )	167.5 146.5	57.4	68.4	259.5	259.5	52.6	127.6	68.4	68.4	106.3 143.6
	Block time t b (N kl )	1.13	1.26	1.21	0.84	0.29	0.29	0.88	0.36	0.32	0.98	0.32	0.38
	Station time t s (N k )	2.79		2.45			2.22			2.40

Table 3 .

 3 An optimal solution for T 0 =2.4

	Station number k	1	2	3		4			5			6
	Block number l	1	1	1	1	2	3	1	2	3	1	2	3
	Operations i∈N kl	1	2	17,24 19,26,11,	22	29	20,27,	18,25,13,16 23,30 3,5,7, 9 4,6,8,10 21,28
					14			12,15
	L(N kl )	155	155	57.7	44.1	24	24	8	53.3	12.5	35.8	20	24
	S(N kl )	167.5	146.5	57.4	57.4	259.5 259.5	68.4	68.4	106.3	52.6	127.6	143.6
	Block time t b (N kl )	1.13	1.26	1.21	0.97	0.29	0.29	0.32	0.98	0.32	0.88	0.36	0.38
	Station time t s (N k )	1.53 1.66	1.61		1.96			2.02			2.02

Table 4 .

 4 Results of tests

	Page 21 of 21
	Method	|N|, OS, T com	NO	min % ∆	av % ∆	∆	max %	|N|, OS, T com	NO	min % ∆	av % ∆	∆	max %
	IS1 IS2 AS1 AS2	50, 25, 60	0 0 6 7	2.6 7.5 0 0	23.1 20.7 2.5 1.5	35.3 35.3 12.8 9.5	50, 45, 60	1 1 6 5	0 0 0 0	22.2 16.1 1.2 3.7	72.7 36.4 4.8 17.1
	IS1 IS2 AS1 AS2	75, 25, 120	0 0 7 5	3 8 0 0	31.2 24.7 2.6 2.6	49.1 42.1 11.4 10.5	75, 45, 120	0 0 6 10	7.6 1.3 0 0	22.3 19.3 2 0	49 47.1 8.2 0
	IS1 IS2 AS1 AS2	100, 25, 300	0 0 8 10	2.6 5.1 0 0	22.3 18.7 0.5 0	35.3 35.3 2.5 0	100, 45, 300	1 1 6 6	0 0 0 0	22.2 16.9 1.3 1	72.7 36.4 4.9 2.6
	IS1 IS2 AS1 AS2	150, 45, 600	0 0 4 7	11.9 6.25 0 0	19.9 15.7 2.5 1.6	35 28.5 9.4 9	200, 45, 600	--5 6	--0 0	--1.7 2.1	--4.5 10.3

http://mc.manuscriptcentral.com/tprs Email: ijpr@lboro.ac.

uk International Journal of Production Research

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

Acknowledgements

This work is partially supported by ISTC project B-986, INTAS project 03-51-5501 and European coordination action CODESNET.


Del Rio-Cidoncha

Keywords: Slicing-trees, Architecture and Industry architecture and industry, layout optimization, slicing trees, expert system, routing

The aim of this work is to develop and implement a model for facility layout design. The first step will be to study the traditional process of positioning, locating or distributing the different facilities, which will be done with the help of slicing trees. Afterwards, the connections between the facilities will be handled, looking for the shortest path that communicates them all, by the means of an expert system. Finally, the orientation of the original surface will be treated, using rules from Feng Shui. These three aspects and their different techniques will be integrated into a single application, joining as well the knowledge and experience from architects and engineers.

The space distribution algorithm of the application itself provides excellent results. Apart from that, the application considers the routing problem, especially important in Architecture (not so important in industrial plan design, when there are no walls between facilities). The application also considers the orientation of the surface, which contributes to improve the comfortability of the building and power saving. The main advantage of the application is that, while being a good tool for solving the facility layout problem, it also considers the routing and orientation of the building.

State of the art in floorplan design

The general design process is explained in first place in this section. Afterwards, the different approaches to the floorplan problem by engineers and architects are reviewed. Finally, the different methodologies for floorplan generation and solution optimization techniques are also reviewed. The goal of the design process is to get a description of a product or service satisfying certain needs and wishes. Independently of the way in which the process is characterized and the type of product or service, the stages depicted in figure 1 In the engineering field, different strategies to solve the implantation problem have arisen along time. The most important ones are, in chronological order: Inmer (1950) [START_REF] Immer | Layout planning techniques[END_REF], [START_REF] Buffa | Secuence analysis for functional layouts[END_REF] [START_REF] Buffa | Secuence analysis for functional layouts[END_REF], Muther [START_REF] Muther | Systematic Layout Planning[END_REF] and [START_REF] Reed | Plant Layout: Factors, Principles and Techniques[END_REF] [4], [START_REF] Nadler | What systems really are[END_REF] [5] and [START_REF] Apple | Plant layout and material handling[END_REF] [START_REF] Apple | Plant layout and material handling[END_REF]. The most famous one is Muther, the author of SLP (Systematic Layout Planning), which has been the most widely used method until today. SLP is a common choice for solving facility layout problems, independently of their nature: industrial plants, hospitals, offices, shopping malls, etc.

In Architecture, architectonic composition is defined as the search of physical layouts or organizations that reach certain goals while keeping some restrictions (Coyne 1988 [7]). In figure 2, the architectonic conception processes from the last decade are compared with the traditional methodology. As it can be noticed, the structure of the process remains the same, although all the stages are nowadays computer-assisted. A comparison of the solutions to the composition problem, starting from the different visions engineers and architects have from it, is performed here. In Architecture, the design process has been a traditionally debated matter. Several different theories and thinking ways coexist. In Engineering, on the other hand, there has been a methodological discussion about the implantation problem and from there on a general acceptation of the SLP method. Both disciplines differ clearly in the goals to achieve and in the number of solutions, too. As a common factor, it can be stated that the three design stages in the architectonic composition process are the same as in the traditionally considered in industrial design (figure 3). The aim of layout generation methods (LGM) is not only to exhaustively list all the solutions that accomplish the requirements, but also to act as an initial filter. There are three different classifications. First of all, depending on the the cost function. Multicriteria techniques, being unanimously accepted nowadays, are the most important ones, but with several different formulations depending on the author. Second of all, depending on the way of generating the solution: starting from a previous one (improvement methods) or creating a new possible one (construction methods). The third criterion that has been utilized in order to classify the methods is the way of locating the activities, an aspect that is closely related to the mathematical description of the problem. There are three different categories: methods based on discrete techniques, methods that use an analytic formulation of the problem, and methods based on partitioning an initial domain through slicing algorithms. The numerous techniques that are currently utilized for selecting solutions are presented in figure 4

Techniques in the proposed methodology

Everything that is required to implement the proposed methodology is described in this section. In first place, slicing trees and their applications on floorplan design will be explained, as well as their applications to very large scale integration circuits (VLSI) and, in particular, to an advanced PLAYOUT [9] system. Such a system has worked as a reference for the method proposed in this work. Afterwards, Feng Shui (an oriental discipline for adequation and harmonization of the environment) and its applications to architectonic design will be explained. In third place, as an intrinsic application of artificial intelligence, the known methods for looking for the trajectories that interconnect two points will be enunciated.

Slicing trees

Trees are a method of representing the arrangement of facilities on a certain floor. There are two different types of trees that are utilized: cut trees and slicing trees. Cut trees are an older technique in which the initial surface is not considered until the final separation is made. When using slicing trees, one starts from the initial geometry and recursively divides the surface with cuts in perpendicular directions. They admit a code for the cut operations, as shown in figure 5. Slicing trees constitute structures from which layout families can be generated. This tree-shaped structures are organized in internal nodes, which characterize the partitioning cuts, and external nodes, which represent the layout spaces. The structure of a slicing tree must be designed in such a way that it shows the proximity requirements between related activities, clustering those ones between which there is a large flow of materials. The hierarchic grouping process is represented in a diagram called dendrogram (figure 6).

VLSI circuit design with Playout

An integrated circuit is constituted by a board made out of silicon which is divided into smaller regions that, thanks to special chemical processes, have different conducting properties. In the case of VLSI technology, the component density is huge, with millions of combinations between conducting, commuting and dielectric cells in a small integrated-circuit wafer. The integrated circuit design problem includes the following variables: the elements to be integrated on the board, their areas and the required connectivity between them. Two restrictions are considered: minimizing the total board area and keeping adequate response times between elements.

In floorplan design, the matter is how to distribute certain facilities, each one with a certain surface, on a given floor, knowing that there is a need for some spaces to be close to other ones. Possible restrictions on areas and distances between them must also be considered. If both problems are analyzed, a clear analogy can be observed. The electronic components are equivalent to the facilities. The board is analogue to the available floor. The connectivity requirements between circuit components are equivalent to the proximity requirements between rooms or departments. This similarity makes it possible to utilize integrated circuit techniques to solve the floorplan problem. In this work, a procedure whose initial purpose was to design VLSI layouts is used. This design system, which is computer assisted, is called PLAYOUT [9], and was created at University of Kaiserlautern (Germany) in the Computer Science Department by professor Zimmerman's group in 1995. It is a hierarchic system with a top-down methodology. PLAYOUT consists of: the MIMOLA software system (MMS), the schematic input, the distrutor, the shape function generator (SFG), the chip planner, the cell synthesizer and the chip synthesizer.

The chip planner is the central tool. It carries out two independent tasks: locating and wiring. Wiring is the calculation of the minimum layout between the cells. Locating is the topology determination, which is calculated with slicing trees. Its goals are to minimize the net length and to avoid cell stretching. The locating is divided into three stages:

• Partitioning: separating different groups of activities in the tree. Different algorithms can be used: cluster, mincut, ratio-cut and inplace.

• Orienting: deciding if the separation is made by an horizontal or vertical line.

• Ordering: decide whether to place to the left or to the right, if the cut is vertical, or up or down, if it is horizontal.

Feng Shui as an architectonic design tool

Feng shui is the taoist science and art of living in harmony with the environment. The Earth is seen as a permanent source of energies, that must flow acted upon by basic principles. In order to find them, an orderer work sequence must be followed. This sequence starts with analyzing the shape of the floor and the contour of the building, and then studying the orientation and distribution of the modules in each floor.

Shape analysis

Shape analysis is the most important aspect in residential Feng Shui studies. It is necessary that the floor and its contour are proportioned to the building. The election of a contour shape for a flat or house depends on three factors: stability, balance and uniformity. Stability is created when, in a building, no floor is much bigger than the other ones. A floor is balanced when its shape is not irregular. Uniformity is defined as the lack of ridges and hard structures.

Floor orientation and distribution

In order to study the layout and orientation of modules on the floor of a house, the geomantic chart is utilized. It provides a distribution in harmony with the environment, and that harmony is transmitted to the inhabitants, contributing to their well-being. The process starts from the building year in the Chinese calendar. Depending on it, one of the Nine Cycles charts is picked. Numbers are then obtained for every box in the chart, and an orientation is finally provided by the geomantic compass. Feng Shui finishes here. It is now the architect's task to apply his knowledge to the information provided by Feng Shui to design different floorplans for the studied house or flat.

Route search as a problem within Artificial Intelligence

Finding the shortest way between two points in a network [10] is the purpose of methods that look for the best route. If the shortest way beginning from a certain point S and finishing in another one G is to be found, the most obvious strategy is to consider all the possible trajectories. If they are represented, a search tree is obtained. Every leaf in the tree represents a route, and the branches connect routes to single-step route extensions. Figure 8 shows a search tree that represents the possible paths from the initial leaf in figure 7. A disadvantage with search trees is that their size grows exponentially. There are search methods that try to minimize the amount of checked paths (Breadth-first search, Depth-first search, etc). But there are also shortest path search methods, which try to solve the problem of finding the shortest path between two points. There are several proposed methods:

• British Museum: all the possible paths are found and the best one selected. It is a good method when the tree is small. • Branch-and-bound search: partial trajectories are studied and the shortest one chosen. This path is extended in all the possible ways and is studied again. This is useful when the tree is large.

• Subestimation incorporation: hypothesis about the remaining distance to the destination are made.

• Dynamic programming: improves branch-and-bound, suppressing redundant partial trajectories.

• A*: combines dynamic programming and subestimation incorporation.

Development of a method for solving the floorplan design problem

There are three necessary steps to make a floorplan design. In the first one, the relationships between different modules, their distribution or location, are established. In a second step, the corridors that communicate the facilities with each other in the most simple and fast way are found. This task is known as routing. In the last step, the spaces are geographically oriented.

For the locating problem, slicing trees were used, extending a technique for VLSI circuits to the floorplan design problem. For the routing problem, an expert system based on rules for production was chosen as the most appropriate for the functional requirements. For the orientation problem, a computer assisted numerical method was used for handling the recommendations provided by Feng Shui. This three modules are synthesized in the proposed CEF methodology, where CEF stands for Cut-Expert-Feng Shui.

Floorplan distribution or locating

It is important to bear in mind that floorplan design consists of "ordering in the most efficient way certain spaces between which certain interactions exist: flow of materials, resources or information" [START_REF] Tompkins | Facilities Planning[END_REF]. Some criteria must be set in order to evaluate which alternative is the best one. These criteria aim at maximizing habitability and beauty in Architecture and at maximizing efficiency and minimizing costs in Engineering.

Problem statement

In general, the starting point of the floorplan design problem consists of:

• A domain floor D with a given geometry and area, D(A).

• The spaces or activities to distribute, with area a i and geometry D i (a i ).

• Proximity requirements between certain spaces or activities, know as relational intensities w ij .

The goal is to minimize the total relational cost the system: while keeping the area under the limits of the original floor:

= m i i A a 1
The distance d ij is the one between the centres of gravity of the activities $i$ and $j$. Moreover, the following constraints must also be satisfied:

max , min , i i i q q q max , 0 i i o o m j i ,..., 2 , 1 , =
where q i is the aspect ratio of activity i: length divided by width. Setting a limit for this value [8] prevents the algorithm from generating too elongated spaces, which are especially inappropriate in Architecture. On the other hand, o i is the dead area ratio of activity i. This parameter indicates the existence of occupied areas in the initial domain floor D and the distortion this fact causes on the shape of the solution.

Utilized methodology

The proposed CEF methodology divides the process into three steps: partitioning, orienting and ordering, which were described in section 2.1. For partitioning the initial rectangle, as CEF can handle just this type of geometry, the ratio-cut algorithm was used because it gives a large importance to balancing the areas to both sides of the cut. Figure 9, in which A i and B i are the subgroups of rooms or activities created by the cut, shows that the design parameter for this algorithm is the ratio between the weight of a cut and the product of the sizes of the sub-trees. The heuristic of the algorithm is to minimize that parameter. When the value of the parameter is equal for two distributions, the one with a bigger denominator or the one with more similar area is chosen.

For orienting, the Lather method [12] was used (figure 10). It proposes orienting the cut so that it is parallel to the shortest side of the partitioned surface. It requires a continuous analysis of the shape of the partitioned surface, so that all the resulting shapes are under control. For ordering, the purpose of the CEF program is to minimize the function that represents the transport cost between spaces, figure 11. All the possible distributions are calculated, and the one that provides the minimum cost function value is spared.

Routing

Once the locating problem is solved, the next step is to find the smallest net that interconnects all the departments or modules. A method for solving this problem has been searched. The algorithm for looking for the tree that provides a minimum laying was adapted, analyzing at the same time the connection between square spaces with equal size and the best way of joining sub-trees that interconnect groups of modules. Synthesizing these three analysis, an algorithm that reaches a local minimum in a reasonable time was obtained. The algorithm will be translated to production rules, so that an expert system for module connection is available.

According to the terms defined in figure 12, the method operates in the following way: • Mark the nodes which are not desired to be part of any corridor as forbidden. Mark the input node as compulsory.

• Mark the branches that lead to forbidden nodes also as forbidden.

• Look for the nodes that are marked as compulsory or have been configured like that in the process of forbidding nodes or branches. This way there will not be isolated modules.

• Check the different alternatives for sub-corridors and, in the case of any of them having just one alternative, make that node and the branch that communicates it part of the sub-corridor.

• When no more branches can be added, the longest non-forbidden branch is eliminated. Once a branch is discarded, the process continues until all the sub-corridors are merged into one, that connects all the spaces. In this point, a solution has been reached, but it has to be revised in order to look for local improvements (for example, branches that form loops).

Orientation in floorplan design

The third and last stage of the methodology stage is the orientation. The empirical rules depicted in figure 13, which depend on the type of space and are related to the cardinal points, were obtained from Feng Shui. In order to put together the Feng Shui recommendations on relationships between spaces, a diamond-tipped relational diagram (figure 14) has been used. Capital letters represent the relationships that are directly derived from previously drawn conclusions. Lower-case letters represent the relationships that are introduced from the PAKUA anagram. The A, U and X categories are used in the first case. The rest are used for the inducted categories. When these recommendations are analyzed, their parallelism with the occidental house conception can be appreciated.

Description and analysis of the results

The purpose of this section is to validate the CEF method that has been proposed as a solution to the floorplan design problem, both for industry and architecture, by applying it to different problems that have already been studied by other authors. As the CEF method consists of three modules (locating, routing and orienting) that work independently, their efficiency will be initially tested one by one. A later experiment will test how the system works on the whole.

Locating module in engineering.

In order to develop the experimental part of the locating module in engineering, the problem posed by Francis and White in 1974 [13] is used. For validating the proposed method, the results will be compared to those from other authors that have studied the same floorplan design problem. The selected methods are • Francis and White method.

• Kar Yan Tam (KYT) method [14].

• ARBOGEN method [15].

The Francis and White method, based on a CRAFT [16] improvement method, requires an initial solution as starting point. KYT is an hybrid method, based on genetic algorithms and slicing trees. It utilizes clustering techniques to generate a dendrogram that represents the structure of the tree. ARBOGEN is also an hybrid method based on genetic algorithms and slicing trees. As opposed to KYT, it also admits different slicing The results are compared according to the following criteria:

• Resulting geometric shapes: the comparison with the Francis and White solution is not possible, as its geometry is not rectangular. The other represented solutions use slicing trees and have rectangular geometries. In these cases it is interesting to calculate the length-width ratio for the spaces, setting certain limits for acceptable values. This ratio indicates the quadrature of the spaces. The mean values are shown in table 1.

• Transport costs: to make a quantitative comparison, they were calculated by multiplying each flow by the corresponding transport cost and by the distance between each pair of activities. The sums of all the partial costs are shown in table 2 It can be appreciated in table 2 that the distribution obtained with the method proposed in application 1 achieves a transport cost 17.7% and 41.3% less than KYT and ARBOGEN, respectively. Application 2 achieves an even lower cost, showing the importance of utilizing integer relational intensities in the design program, as the approximation to the real problem is larger.

Locating module in architecture

It is important to emphasize in first place the impossibility of quantizing aesthetic and composition factors, such as habitability, balance and beauty, which are important goals of an architectonic distribution. Moreover, as opposed to what happens in engineering, there are several strategies to approach the floorplan design problem. This review, that is the design process itself, shows the composing procedure (the main discussion point) and its formalization and conceptualization (most of the researchers' aim).

There are two differentiating aspects between the different models: the number of solutions that are obtained and kind of goal function (figure 16). Most of the architecture-specific applications provide all the possible solutions, leaving the definitive choice in the professional's hands. It is in the goal function where more diversity between methods can be found, even if many researches focus on optimizing dimensional aspects (such as wall lengths, areas...), summed up in different parameters. Fewer try to maximize the proximity between spaces with related needs, single goal for every industrial procedure.

Routing module

The problem of connecting a set of spaces, where each one can be connected to the net by any point of its perimeter, is a rather particular problem, and there are not many studies or resolution algorithms about it, as its most important application is floorplan design. That is why programs outside floorplan design had to be searched in order to compare the routing module application. Another field in which trees that interconnect

Complete method

All the abilities of the application will now be used at the same time: locating the spaces, orientating the floor and obtaining the corridor that communicates all the modules with minimum length. In order to evaluate the results, the floor of an already built house is compared to the solution from the CEF program. The construction of the studied house was finished in 1994. It was designed by the architect Jaime López de Asiaín y Martín. Its floor is shown in figure 17. The solution provided by the CEF method is shown in figure 18. The similarity with the real floor is large. Considering the locations of the rooms, only the kitchen -dining-room cut, which is done by a vertical wall, is different to the separations on the real floor. This is due to the weak relationship established between the kitchen and the other rooms by Feng Shui, which makes the separation between the kitchen and the other rooms the first cut to be performed.

The routing module of the application was employed to establish the path that communicates all the rooms. The result is shown in figure 19. Even when an implantation can be oriented without performing its routing, the best disposition (related to the cardinal points) among those ones that are possible is chosen according to Feng Shui rules. As it can be appreciated in figure 20, the program shows the geographic north direction and reports the amount of degrees that the floor should be rotated with respect to the one shown on the screen.

Conclusions and future work

The proposed CEF methodology tackles in an integrated way the three aspects that determine the configuration of a floorplan: location, routing and orientation. The handling is the same for industrial and architectonic floors: a single application with common inputs and a single output is used. The modular configuration that was chosen for the application contributes especially to this fact.

Reviewing the conclusions for each module, it must be emphasized that, for the locating module, advantage was taken of the similarity with integrated circuit design. A procedure with slicing trees was utilized, leading to a heuristic that looks for the optimal solution for the distribution with computer-assisted techniques. The methodology allows to easily formulate a multi-criteria goal function. The main disadvantage with the employed slicing tree techniques is that they lead to elongated spaces, but the ratio-cut algorithm in cut selection contributes to the geometric control of the solutions. As a consequence of the two previous aspects, the obtained layouts have a modular configuration. Finally, it can be concluded that this module provides better solutions than the other known locating methods.

Concerning routing, the system provides high quality solutions, even if they are approximations, as it has been shown in the experiments. The main characteristic of the module is its flexibility: the capacity of adapting to different requirements. This is derived from two aspects: the utilized production rules and the division of the module into three parts that work independently from each other. Finally, regarding orientation, it has been shown how Feng Shui principles, taken out from bibliography, can be used through a routine written in C++.

CEF is currently being successfully used by the "Miguel Ángel López y Asociados" architecture studio in Seville (Spain). It is also utilized by "Ayesa", a powerful Spanish company that designs and builds industrial plants. It is even used experimentally by professor Laura Roa at University of Seville in order to develop a teleassistance system for nephrology ("NEFROTEL").

Regarding the future work, it is important to mention that only rectangular floors have been studied in this article. The software could be updated so that it could handle irregular shapes. It could also be extended to design distributions along different floors, including the necessary spaces for stairs and elevators. Finally, it would also be desirable to be able to define a relational intensity matrix that represents asymmetric flows of materials. This would be especially important in industrial plants, where the flow of materials from room A to room B can be very different from the flow from room B to room A.

  for floorplan designGloria del Río-Cidoncha 1 , Juan Martínez-Palacios 1 and J.Eugenio Iglesias2

  are always present.

Figure 1 :

 1 Figure 1: Stages in the design process

Figure 2 :

 2 Figure 2: Strategies of architectonic composition, from [8].

Figure 3 :

 3 Figure 3: Comparison of composition processes.

  . The different origins and authors that used them first for floorplan design are shown in the same figure.

Figure 4 :

 4 Figure 4: Techniques for optimizing solutions, from [8].

Figure 5 :

 5 Figure 5: Character array: idal24b6i53.

Figure 6 :

 6 Figure 6: Activity clustering.

Figure 7 :

 7 Figure 7: Basic search problem.

Figure 8 :

 8 Figure 8: Search tree from the problem in figure 7.

Figure 9 :

 9 Figure 9: Ratio-cut algorithm.

Figure 10 :

 10 Figure 10: Lather method: spaces with elongated shapes are avoided.

Figure 11 :

 11 Figure 11: Minimization of the goal function, that is, the sum of distances between the centers of gravity of the related spaces or activities.

Figure 12 :

 12 Figure 12: Definition of terms used in the heuristic.

Figure 13 :

 13 Figure 13: Orientations recommended by Feng Shui.

Figure 14 :

 14 Figure 14: Diamond-tipped relational diagram.

  structures, applying the genetic algorithms in a double level in order to look for the most adapted species. The different results are presented in figure15.

Figure 15 :

 15 Figure 15: Obtained results.

Figure 16 :

 16 Figure 16: Different approaches depending on the number of solutions and the kind of cost function.

Figure 17 :

 17 Figure 17: The floor of the studied house.

Figure 18 :

 18 Figure 18: Solution with CEF.

Figure 19 :

 19 Figure 19: Routing.

Figure 20 :

 20 Figure 20: Solution from figure 19 oriented.

Table 1 :

 1 . CEF 1 is exactly the same as CEF but with binary relational intensities. Mean quadrature ratio.

	Method		KYT	ARBOGEN		CEF
	Mean ratio		3.39	2.04		1.75
	Method	CRAFT	KYT	ARBOGEN	CEF-1	CEF-2
	Cost	4521.5	6324.2	7470.5	4379.6	4246.2

Table 2 :

 2 Transport costs.

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

  points are searched is microelectronics. In this context, the ORCAD-PCB program is presented. It is a commonly used program for printed circuit wiring. Comparing both solutions, it is observed that search times are in average 62% longer in CEF than in ORCAD-PCB. On the other hand, CEF takes advantage of this extra time to obtain a shorter solution (4.5% of the length of the net in average).

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

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