资源描述
资料来源：文章名：一种基于分枝定界算法的注塑模架基工艺规划系统书刊名：Advanced Manufacturing Technology作 者： P. Y. Gan, K. S. Lee and Y. F. Zhang出版社：Department of Mechanical Engineering, National University of Singapore, Singapore章 节：A Branch and Bound Algorithm Based Process-Planning System for Plastic Injection Mould Bases页 码：10.1007/s0017001一种基于分枝定界算法的注塑模架基工艺规划系统 70022 文 章 译 名： A Branch and Bound Algorithm Based Process-Planning System for Plastic Injection Mould BasesP. Y. Gan, K. S. Lee and Y. F. ZhangDepartment of Mechanical Engineering, National University of Singapore, SingaporeThis paper describes the use of artificial intelligence in the process planning of plastic injection mould bases. The com- puter-aided process-planning system, developed for IMOLD will extract and identify the operations required for machining. These operations are considered together with their precedence constraints and the available machines before the process plan for the mould base plate is generated. The process plan is optimised by a branch and bound based algorithm. Overall machining time has been proposed as the objective function for optimisation. The ability of this algorithm to search intelli- gently for a feasible optimised solution is illustrated by an industrial case study. A brief comparison with a genetic algor- ithm based process planning system is also made. The result of this development will allow users to optimise process plans easily for any given mould base, with options to suit dynamic changes on the manufacturing shop floor.Keywords: Branch and bound algorithm; Computer-aided process-planning (CAPP); Optimisation; Plastic injection mould base1. IntroductionComputer-aided process planning (CAPP) has received much attention in recent years. It has long been identified as the bridge between computer-aided design (CAD) and computer- aided manufacturing (CAM) systems to achieve a fully auto- mated factory. Despite the need, insufficient CAPP systems have been developed for the different industries requiring them. This work focuses on developing a CAPP system for mould base makers. At present, most process planning for the pro- duction of mould bases is done manually. The process plans depend very much on the decisions of the process planner. The introduction of CAPP systems should ensure consistently good process plans with more comprehensive consideration ofCorrespondence and offprint requests to: K.-S. Lee, Department of Mechanical and Production Engineering, The National University of Singapore, 10 Kent Ridge Crescent, Singapore 119260. E-mail: mpeleeksnus.edu.sgthe manufacturing parameters. CAPP systems are required in industry for the following reasons:1. Mould base companies are receiving an increasing number of requests to manufacture customised mould bases, in which additional features are added to a standard mould base. Therefore, extra operations are required to create these new features. Usually, standard mould bases have a predetermined process plan, which is optimised for the amount of machining required. As new operations are added, this optimised process plan is disrupted and manual process planning is unable to keep up with the changes. CAPP systems are able to re-optimise the process plan constantly to ensure optimality of the process plans used.2. Overall shop floor conditions should be taken into account during process planning. Manual process planning is unable to consider all shop floor changes and apply them efficiently. Only CAPP systems allow rigorous consideration of optimis- ation.The goal of this work is to develop a CAPP system for process planning mould bases. IMOLD (Intelligent Mold Design) is a knowledge-based application software developed at the Department of Mechanical Engineering, NUS to facilitate plastic injection mould design. The system is an addition to IMOLD, and it process plans the mould bases created using IMOLD. Databases of machines, tools, precedence constraints, and the model part file are read together with real-time inputs of machine availability during process planning. An operator is required to enter the customised features and a process plan is then generated using some form of artificial intelligence. The branch and bound technique is the chosen search algor- ithm here.This paper presents the operation of a flexible CAPP system aimed at assisting process planners in more comprehensive considerations during operations planning. A brief literature survey is provided of some forms of artificial intelligence used in process planning and related work in this field. Problem formulation and the branch and bound algorithm implemented are included in the following sections. Lastly, a case study demonstrates the usability and potential of this system. A comparison between branch and bound based CAPP and genetic algorithm based CAPP is shown in a second case study. 2. BackgroundProcess planning is the preparation of a set of detailed instruc- tions for all the steps required to create the final product from a piece of raw material 1. The quality of a process plan depends very much on the skills of the process planner, as extensive knowledge of the available tools, the machines and the operations needed to create a part is required 2. A CAPP system is therefore seen as an important tool for assisting in process planning.A CAPP system should optimise a part for all possible methods of manufacturing. However, many reported CAPP systems are not able to generate globally optimised process plans 3. As a result, there has been an increasing use of artificial intelligence to search for global solutions 4,5. Many of the reported methods involve only feature sequencing with- out including details of the operations required 6,7. Details of the operations are necessary for allocating shop floor resources for performing the operations.The performance measure is the objective function to be maximised or minimised in all optimisation problems. For process planning, the objective is either to minimise time, cost, or sometimes both. There is a variety of work done using cost as the performance measure 8. However, there is also a range of cost models that can be used to consider and calculate cost 9,10, but there is no universal method to account for costs. It is known that to minimise work-in-progress and the flow- time of jobs in a job shop, process plans with the least overall machining time should be used 11. We therefore use time, as it is a more definite basis on which to quantify the quality of generated process plans. This choice is further justified, as the delivery time of mould bases is very important in mould- making industries.An exhaustive sequential search for a process plan solution leads to unacceptable computation times when a large number of operations are required. This work uses a branch and bound algorithm to search intelligently for the optimal or near optimal process plan. The branch and bound algorithm is a well-known search algorithm for implicit enumeration of the search space 12. Its use as an artificial intelligence method has been reported widely in the areas of scheduling, process planning, and problem solving 13.Some work has been reported using the branch and bound technique for process planning 1416. However, the nature of process plans in those works is different from the process planning required for the mould making industry. This work uses the branch and bound technique to process plan all the operations considering all tool access directions on all the available machines and tools for each mould base plate. To the best of our knowledge, such a level of consideration has not been dealt with in other related studies.3. Problem FormulationA process-planning problem is constrained to the number of operations, precedence relations, machines, machining direction, and tools. The optimised solution is a way to sequence theoperations with their associated machines to produce a process plan, which takes the least possible production time.3.1 Process Planning ModelThe information required for optimisation is extracted from mould bases modelled using IMOLD. This database of oper- ations, machines, machining direction, tools, and precedence constraints is used for process planning together with machine availability. A schematic representation of this model is shown in Fig. 1 and the following assumptions are made:1. Only one operation can be processed by one machine at a time.2. All the machines can access the part at only one particular face. If machining is to be done on another face, the part has to be taken down and set-up time has to be incurred to replace the part facing a different direction.3. Cranes or robots are available at all times. No waiting time is allowed for time wasted while waiting for machinery or labour to move the parts.Customised features require the process planner to input the necessary data manually. This is because a single feature can be created by many possible methods and this allows the process planner more control over the system. The assigned operations and the final generated process plan should satisfy the following conditions:1. The features of the mould base plate are recognised with the operations assigned to them. The operations assigned should produce the desired shape, dimension, tolerance, and finish to the feature.Fig. 1. The process planning model.2. The sequence of operations obtained from the process plan should not violate any precedence relations governing the operations.machining direction, but no change of machine between the two operations. It is defined as,3n13. Operations can only be carried out on available machines with the available tools, which are capable of machiningMDST =i=1(K(MDi+1,MDi)that particular feature.The process plan obtained should include the number of operations to be carried out, the sequence of these operations, the machines, machining direction, and corresponding tools used. Such details are necessary so that time can be saved for operations to be carried out on a particular machine using the same set-up. For example, a blind hole must be drilled in the+x direction whereas a through hole can be drilled from the+x or x directions. It can be seen by considering just these two operations, that the process plan should try to perform these two operations on the same machine from the +x direc- tion so that extra set-up time is not incurred.3.2 The Objective FunctionTo quantify the objective function, which is the overall machin- ing time (OMT), we use a calculation framework similar to that used by Zhang et al. 17. The objective function is calculated for each successive sequence of the process plans, and the sequence that yields the minimum OMT will be taken as the final process plan. There are 3 areas which contribute to the calculation of OMT, and they are machine set-up times, machining direction set-up times, and machining times.3.2.1 Machine Set-up Time3Machine set-up time (MST) is considered whenever there is a change of machines between two operations. It is defined as the time required to move between machines and the set-up time of the mould baseplate onto the machine in a particular direction. It is defined for a total of all n operations as,n11 K(Mi+1,Mi) MDSTIi+1)(3)MDi is the machining direction selected to process operation i and MDSTIi is the machining direction set-up time index for the machine used in operation i. MDSTIi and MSTIi are related by the difference in time to move the part between the old and new machine.MSTIi = MDSTIi(4)+ (Time to move part between machines)As no waiting time for the cranes or robots is assumed, we take MDSTIi and MSTIi to be the same.3.2.3 Machining Time3Machining time MT is the actual time to perform all machining operations such as drilling, milling, or grinding on the assigned machines with the respective tools.ni iMT =(MTM ,T )i(5)i=1The machining time for a single operation can vary according to the assigned machine and tool selected. From this, there exists one or more possible MTi for a single operation.3.2.4 Overall Machining TimeOverall machining time is the total of all machine change set- up times, machining direction change set-up times and all machining times.OMTmin = (MST + MDST + MT)optimised sequence(6) The objective is to produce a sequence of operations that willMST =where,i=1(K(Mi+1,Mi) MSTIi+1)(1)K(Mi+1,Mi) =1 if i = 11 if Mi+1 G Mi (i 1)(2)0 if Mi+1= Mi(i 1)require the least OMT.Table 1. Types of machines, MSTI, MDSTI and types of suitable tool.Machines (M)MSTI, MDSTI(min)Tool types Suitable (T)1. FARTWARTH VBM-5VL5, 51vertical surface miller2. HAMAI-4DS horizontal gang6, 61surface miller3. Manual chamfering machine2, 254. OKAMATO grinding machine4, 425. HUACHONG grinding3, 32machine6. Radial drilling machine2, 24, 67. MORI SEIKI MV65-503, 31,3,4,6,7,8,9vertical CNC milling8. MAKINO MC98 vertical4, 41,3,4,6,7,8,9Mi refers to the machine selected to process operation i,MSTIi refers to the machine set-up time index for the machineused in operation i, and n is the number of operations selected for the whole series of operations identified from the mould fea- tures.3.2.2 Machining Direction Set-up TimeCNC millingMachining direction set-up time (MDST) is the time required to change the orientation of the mould baseplate on the same machine. MDST is calculated only when there is a change in1. Face mill cutter; 2. Grinding wheel; 3. End mill; 4. NC spot drill;5. Edge-grinding wheel; 6. Drill; 7. Reamer; 8. Boring tool; 9. Tap drillFig. 2. Customised core plate part with 11 additional operations.4. Branch and Bound AlgorithmA branch and bound algorithm was chosen as the search algorithm to be used as it has a proven track record in this area. Its robust and enumerative nature should yield an optimal or near optimal solution. The search space of most branch and bound algorithms is inherently large and computationally complex. This means that effective heuristic and efficient lower bound calculations are important for decreasing search space to help arrive at a good solution earlier.4.1 Implemented AlgorithmThe algorithm starts by sequencing one of the available oper- ations and this is called branching the node. By branching a node, a new node is formed and the node is kept in the search space if its lower bound value is better than the upper bound value or vice versa. A heuristic is used to schedule the remaining operations for every node and the best solution found so far will be recorded as the upper bound value. The next node to be branched is the one with the best lower bound value, as it is deemed to have the best potential. As more nodes are branched, more and more operations will be sequenced, and the upper bound value will become smaller and smaller. Thealgorithm stops when the upper bound value is smaller than all lower bound values and the process plan is the sequence that yields the upper bound solution.To balance the quality of the solution and the computation time, a termination condition is set such that the program will exit when there is no more improvement to the upper bound value after a certain number of cycles (Xc). For most problems, it was found that a value of about 10 000 for Xc will yield near optimal solutions while giving a computation time of less than 10 min.To explain the branch and bound algorithm better, we use the conventions of the A* algorithm. The mathematical rep- resentation of the lower bound function f(Sa) for sequence Sa is defined asf(Sa) = g(Sa) + h(Sa)(7)where g(Sa) is the cost incurred to reach Sa and h(Sa) is a function that calculates the estimated cost of reaching the final schedule. When all the operations are sequenced, h(Sk(final) = 0, the objective function can then be calculated as f(Sk(final) = g(Sk(final). The implemented branch and bound algorithm can be briefly summarised as follows:beginStep 1. S0 Initial situation (no operation sequenced) Open S0doStep 2. Choose in Open, a node with sequence Sa, which has the best lower boundOpen Open SaStep 3. Sequence all the possibilities starting from Safor each possibility SkStep 4. Use a heuristic to schedule the remaining operationsSk(final)objective function = g(Sk(final)Step 5. Update the upper bound valueif g(Sk(final) is betterthen upper bound = f(Sk(final)Step 6. Calculated the lower boundfor each possibility k, f(Sk) = g(Sk) + h(Sk)Step 7. Include branched node into search spaceif f(Sk) better than upper boundthen Open Open + SkendStep 8. Discard all nodes in Open with f(S) worse than, or equal to, upper boundwhile Termination condition G OR Open G end4.2 Constant Machine / Machining Direction HeuristicA good heuristic will help to generate good solutions as early as possible. When good solutions are generated early, the upper bound value will become lower and has a higher chance of rejecting unpromising nodes with higher lower bound values. This will reduce the search space so that time can be spent more efficiently on nodes, which might give a better solution than the current best. However, when a heuristic becomes too complex and computationally intensive, it causes each branch to take a much longer time and can significantly increase the overall running time. There is thus a need to use a simple and effective heuristic.When a process planner plans for a particular job, operations that require both the same machine and machining direction will usually be grouped and carried out together. To build on that behaviour, the heuristic will keep looking for the sub- sequent operation that has the same machine and machining direction as the previous one. The heuristic can be briefly summarised as:doStep 1. To determine operation i+1,for all other operations, which can be processed using, machine Michoose the operation with a corresponding machine and machining direction which will yield the lowest added time (AT = MDSTi+1 + MSTi+1 + MTi+1)Step 2. if no operation is chosen, i.e. none of the remaining available operations can be processed by machine Mi, choose the operation with the lowest ATwhile there are still unassigned operations, i = i + 1endThe heuristic will choose an available operation that has the same machine and machining direction as the previous oper- ation if the time is shorter. In cases where time is saved by carrying out that operation on a faster machine, the faster machine is chosen. By having a heuristic like this, the process plan will not always force operations to be carried out on the same machine and in the same machining direction but rather allow different machines to be used if time can be saved.4.3 Lower Bound CalculationThe lower bound value is an estimate of the best possible solution that can arise from the current sequence of a node. A simple way of calculating the lower bound would be to add up the minimum process times for all remaining operations. However, that will underestimate the lower bound value of that node as no set-up time is included in the estimate. Underestimating lower bound values causes many unpromising nodes to be branched and hence wastes time. To obtain best possible solution, we included the set-up when necessary into the lower bound calculations. It is found tha
展开阅读全文