Heuristic optimization system for the determination of index positions on CNC magazines with the consideration of cutting tool duplications

This paper presents a meta-heuristic optimization system developed for the determination of optimal index positions of cutting tools on the tool magazines (automatic tool changer (ATC) or turret magazine, etc.) of CNC (computerized numerical control) machine tools. The selection of index positions is performed using a simulated annealing (SA) algorithm that takes the following as the input: (1) a list of cutting tools assigned to certain machining operations; (2) the number of copies of each cutting tool available in the workshop; (3) total number of index positions on the tool magazines; (4) the indexing time of a tool magazine of a CNC machine tool specified by manufacturer. Then, the SA algorithm determines index locations of cutting tools on the tool magazines. Dereli et al. and Dereli and Filiz previously studied the present problem by using genetic algorithms (GAs). However, the duplication of cutting tools was not taken into account in their works, although it can reduce the total tool-indexing time and therefore improve the productivity considerably. Nevertheless, the consideration of the ‘tool duplications’ makes the problem much harder to model and to solve. In this paper, a novel solution representation-scheme based on the SA, which enables easy manipulation during feasible neighbourhood solution generation, is proposed for the determination of the index positions of cutting tools on the CNC magazines with the consideration of ‘tool duplications’. Example problems are solved to present the implementation and merits of the proposed optimisation system. It is shown that it is possible to allocate the cutting tools in an efficient manner on the CNC magazines with the developed system.     

Decomposition of Petri nets and Lagrangian relaxation for solving routing problems for AGVs

In this paper, we propose a Lagrangian relaxation method for solving routing problems for multiple AGVs by decomposition of timed Petri nets. The AGV routing problem is represented by an optimal transition firing sequence problem for timed Petri nets. The timed Petri net is decomposed into several subnets in which the subproblem for each subnet can be easily solved by Dijkstra's algorithm. We show that each subproblem generated by each subnet is polynomially solvable. The optimality of the solution can be evaluated by the duality gap derived by the Lagrangian relaxation method. The performance of the proposed method is compared with a conventional optimisation algorithm with the penalty function method. The effectiveness of the proposed method is demonstrated.     

An exact penalty function method for optimising QAP formulation in facility layout problem

A quadratic assignment problem (QAP), which is a combinatorial optimisation problem, is developed to model the problem of locating facilities with material flows between them. The aim of solving the QAP formulation for a facility layout problem (FLP) is to increase a system’s operating efficiency by reducing material handling costs, which can be measured by interdepartmental distances and flows. The QAP-formulated FLP can be viewed as a discrete optimisation problem, where the quadratic objective function is optimised with respect to discrete decision variables subject to linear equality constraints. The conventional approach for solving this discrete optimisation problem is to use the linearisation of the quadratic objective function whereby additional discrete variables and constraints are introduced. The adoption of the linearisation process can result in a significantly increased number of variables and constraints; solving the resulting problem can therefore be challenging. In this paper, a new approach is introduced to solve this discrete optimisation problem. First, the discrete optimisation problem is transformed into an equivalent nonlinear optimisation problem involving only continuous decision variables by introducing quadratic inequality constraints. The number of variables, however, remains the same as the original problem. Then, an exact penalty function method is applied to convert this transformed continuous optimisation problem into an unconstrained continuous optimisation problem. An improved backtracking search algorithm is then developed to solve the unconstrained optimisation problem. Numerical computation results demonstrate the effectiveness of the proposed new approach.     

Loading and scheduling for flexible manufacturing systems with controllable processing times

This study addresses the problem of determining the allocation of operations and their tools to machines, the operation processing times and the allocation/sequence of the parts to be processed on each machine for flexible manufacturing systems with controllable processing times. Tool lives, tool copies and tool sharing are also considered. An integer programming model is developed for the objective of minimizing the sum of operation processing and tardiness costs. Then, iterative algorithms are proposed that solve the two subproblems iteratively, where the loading subproblem is solved by a modified bin packing algorithm under initial processing times and the resulting scheduling subproblem is solved by a priority scheduling method while modifying the loading plans and operation processing times iteratively. Computational experiments were carried out, and the results are reported.     

Self-adaptiveness in particle swarm optimisation to enhance available transfer capability using thyristor-controlled series compensation (TCSC)

Available transfer capability (ATC) is one of the challenging criteria under the functioning of the deregulated power system. The high demand for improving ATC is generally met using flexible alternating current transmission system (FACTS) devices in the power system. However, it suffers from serious crisis during determination of the optimal location and compensation stage of FACTS. The present study uses thyristor-controlled series compensation (TCSC) devices in order to compensate for the limitation of FACTS. Further, a novel self-adapted particle swarm optimisation (SAPSO) algorithm is proposed in this study for enhancing ATC. Experiments are carried on three benchmark bus systems such as IEEE 24, IEEE 30 and IEEE 57. Performance and statistical analyses are carried out by comparing the proposed SAPSO with the conventional PSO. Eventually, the study proves the effectiveness of the proposed method in case of ATC enhancement.     

Optimisation of cutting parameters using a multi-objective genetic algorithm

This paper presents a new optimisation technique based on genetic algorithms (GA) for determination of cutting parameters in machining operations. The cutting parameters considered in this study are cutting speed, feed rate and cutting depth. The effect of these parameters on production time, production cost and roughness is mathematically formulated. A genetic algorithm with multiple fitness functions is proposed to solve the formulated problem. The proposed algorithm finds multiple solutions along the Pareto optimal frontier. Experimental results show that the proposed algorithm is both effective and efficient, and can be integrated into an intelligent process planning system for solving complex machining optimisation problems.     

The optimal feedrate planning on five-axis parametric tool path with geometric and kinematic constraints for CNC machine tools

The optimal feedrate planning on five-axis parametric tool path with multi-constraints remains challenging due to the variable curvature of tool path curves and the nonlinear relationships between the Cartesian space and joint space. The methods for solving this problem are very limited at present. The optimal feedrate associated with a programmed tool path is crucial for high speed and high accuracy machining. This paper presents a novel feedrate optimisation method for feedrate planning on five-axis parametric tool paths with preset multi-constraints including chord error constraint, tangential kinematic constraints and axis kinematic constraints. The proposed method first derives a linear objective function for feedrate optimisation by using a discrete format of primitive continuous objective function. Then, the preset multi-constraints are converted to nonlinear constraint conditions on the decision variables in the linear objective function and are then linearised with an approximation strategy. A linear model for feedrate optimisation with preset multiple constraints is then constructed, which can be solved by well-developed linear programming algorithms. Finally, the optimal feedrate can be obtained from the optimal solution and fitted to the smooth spline curve as the ultimate feedrate profile. Experiments are conducted on two parametric tool paths to verify the feasibility and applicability of the proposed method that show both the planning results and computing efficiency are satisfactory when the number of sampling positions is appropriately determined.     

Integer programming approach to the printed circuit board grouping problem

A printed circuit board (PCB) grouping problem arising from the electronics industry is considered. Given a surface-mounting device with a number of component feeders and several types of PCBs to be produced, the problem is how to group the PCBs so that the total set-up time for component feeders is minimized. The problem is formulated as an integer-programming problem and a column generation approach is proposed to solve it. In this approach, the original problem is decomposed into a master problem and a column-generation subproblem. Starting with a few columns in the master problem, new columns are generated successively by solving the subproblem optimally. To solve the subproblem, a branch-and-cut approach is used. To solve the master problem, a branch-and-bound algorithm is used with the generated columns. However, a branching strategy is also proposed that maintains consistency in the column-generation procedure after branching. Computational experiments show that the solution approach gives high-quality solutions in reasonable computing time.     

Applying an electromagnetism-like mechanism algorithm on parameter optimisation of a multi-pass milling process

Multi-pass milling is a common manufacturing process in practical production. Parameter optimisation is of great significance since the parameters largely affect the production time, quality, cost and some other process performance measures. However, the parameter optimisation of the multi-pass milling process is a nonlinear constrained optimisation problem. It is very difficult to obtain satisfactory results by the traditional optimisation methods. Therefore, in this paper, a new optimisation technique based on the electromagnetism-like mechanism (EM) algorithm is proposed to solve the parameter optimisation problem in a multi-pass milling process. The EM algorithm is a population based meta-heuristic algorithm for unconstrained optimisation problems. As the parameter optimisation problem is a constrained problem, the proposed approach handles the constraints of the problem by improving the charge calculation formula combined with the feasibility and dominance rules at the same time. This paper also puts forward flexible cutting strategies to simultaneously optimise the depth of cut for each pass, cutting speed and feed to improve solutions. A case study is presented to verify the effectiveness of the proposed approach. The results show that the proposed method is better than other algorithms and achieves significant improvement.     

Many-objective harmony search for integrated order planning in steelmaking-continuous casting-hot rolling production of multi-plants

This paper investigates a challenging problem of integrated order planning (IOP) in steelmaking-continuous casting-hot rolling production of multiple plants with consideration of four conflicting objectives. The objective functions refer to the earliness/tardiness ratio, the non-hot charge ratio and the imbalance ratio of production capacity utilisation corresponding to SCC plants and HR Plants. The IOP guided by the integration strategy, which includes the vertical integration of production stages and the horizontal integration of steel plants, is regarded as a large-scale many-objective optimisation problem. To deal with the difficulty of large-scale decision variables, we introduce a new concept named ‘order-set’ for modelling. In addition, a novel knee point-driven many-objective global-best harmony search (KGHS) algorithm, mainly integrating a KGHS process and a new knee point-driven Pareto optimisation, is developed to tackle this many-objective problem. The proposed model and algorithm were tested with benchmarks and real production data. Experiments demonstrate that the proposed approach generates effective solutions superior to those generated by the other popular many-objective optimisation methods.     

Mathematical models and a hunting search algorithm for the no-wait flowshop scheduling with parallel machines

Majority of researches in no-wait flowshop scheduling assume that there is only one machine at each stage. But, factories commonly duplicate machines in parallel for each operation. In this case, they balance the speed of the stages, increase the throughput of the shop floor and reduce the impact of bottleneck stages. Despite their importance, there is no paper to study the general no-wait flowshop with parallel machines. This paper studies this problem where the objective is to minimise makespan. Since there is no mathematical model for the problem, we first mathematically formulate it in form of two mixed integer linear programming models. By the models, the small instances are optimally solved. We then propose a novel hunting search metaheuristic algorithm (HSA) to solve large instances of the problem. HSA is derived based on a model of group hunting of animals when searching for food. A set of experimental instances are carried out to evaluate the algorithm. The algorithm is carefully evaluated for its performance against an available algorithm by means of statistical tools. The related results show that the proposed HSA provides sound performance comparing with other algorithms.     

Research on resources optimisation deployment model and algorithm for collaborative manufacturing process

Agility is the competitive advantage in the global manufacturing environment. It is believed that agility can be realised by networked manufacturing resource optimisation deployment. However, this is a challenge to us now. To solve this question, logical manufacturing unit and logical manufacturing process are proposed to decompose and model the networked manufacturing task, and networked manufacturing resources are organised and modelled based on physical manufacturing unit. During the deployment of manufacturing resources to the task, many factors should be taken into consideration. Of these, manufacturing cost, time and quality are the most important factors. In this paper, before these factors are considered, networked manufacturing resources pre-deployment is carried out to find the candidate manufacturing resources on the basis of manufacturing abilities. Then, resources optimisation deployment is modelled as a multi-objectives optimisation. This optimisation problem is solved based on genetic algorithm after transforming the multi-objectives optimisation problem to a single objectives optimisation problem. Although we may not find the optimal solution for the problem by genetic algorithm, the better and feasible solution is produced. Thus, this algorithm is efficient and can be applicable to practical problem. At last, an illustrative example is presented to show the application of the proposed algorithm.     

Exact and approximate algorithms for part-machine clustering based on a relationship between interval graphs and Robinson matrices

An important manufacturing cell formation problem requires permutations of the rows (parts) and columns (machines) of a part-machine incidence matrix such that the reordered matrix exhibits a block-diagonal form. Numerous objective criteria and algorithms have been proposed for this problem. In this paper, a new perspective is offered that is based on the relationship between the consecutive ones property associated with interval graphs and Robinson structure within symmetric matrices. This perspective enables the cell formation problem to be decomposed into two permutation subproblems (one for rows and one for columns) that can be solved optimally using dynamic programming or a branch-and-bound algorithm for matrices of nontrivial size. A simulated annealing heuristic is offered for larger problem instances. Results pertaining to the application of the proposed methods for a number of problems from the literature are presented.     

A new deterministic global optimization method for general twice-differentiable constrained nonlinear programming problems

A deterministic global optimization method that is applicable to general nonlinear programming problems composed of twice-differentiable objective and constraint functions is proposed. The method hybridizes the branch-and-bound algorithm and a convex cut function (CCF). For a given subregion, the difference of a convex underestimator that does not need an iterative local optimizer to determine the lower bound of the objective function is generated. If the obtained lower bound is located in an infeasible region, then the CCF is generated for constraints to cut this region. The cutting region generated by the CCF forms a hyperellipsoid and serves as the basis of a discarding rule for the selected subregion. However, the convergence rate decreases as the number of cutting regions increases. To accelerate the convergence rate, an inclusion relation between two hyperellipsoids should be applied in order to reduce the number of cutting regions. It is shown that the two-hyperellipsoid inclusion relation is determined by maximizing a quadratic function over a sphere, which is a special case of a trust region subproblem. The proposed method is applied to twelve nonlinear programming test problems and five engineering design problems. Numerical results show that the proposed method converges in a finite calculation time and produces accurate solutions.     

Minimisation of total tardiness for identical parallel machine scheduling using genetic algorithm

In recent years research on parallel machine scheduling has received an increased attention. This paper considers minimisation of total tardiness for scheduling of n jobs on a set of m parallel machines. A spread-sheet-based genetic algorithm (GA) approach is proposed for the problem. The proposed approach is a domain-independent general purpose approach, which has been effectively used to solve this class of problem. The performance of GA is compared with branch and bound and particle swarm optimisation approaches. Two set of problems having 20 and 25 jobs with number of parallel machines equal to 2, 4, 6, 8 and 10 are solved with the proposed approach. Each combination of number of jobs and machines consists of 125 benchmark problems; thus a total for 2250 problems are solved. The results obtained by the proposed approach are comparable with two earlier approaches. It is also demonstrated that a simple GA can be used to produce results that are comparable with problem-specific approach. The proposed approach can also be used to optimise any objective function without changing the basic GA routine.     

Exact algorithms for the job sequencing and tool switching problem

The job Sequencing and tool Switching Problem (SSP) involves optimally sequencing jobs and assigning tools to a capacitated magazine in order to minimize the number of tool switches. This article analyzes two integer linear programming formulations for the SSP. A branch-and-cut algorithm and a branch-and-bound algorithm are proposed and compared. Computational results indicate that instances involving up to 25 jobs can be solved optimally using the branch-and-bound approach.     

A particle swarm optimisation for the no-wait flow shop problem with due date constraints

This paper considers the no-wait flow shop scheduling problem with due date constraints. In the no-wait flow shop problem, waiting time is not allowed between successive operations of jobs. Moreover, a due date is associated with the completion of each job. The considered objective function is makespan. This problem is proved to be strongly NP-Hard. In this paper, a particle swarm optimisation (PSO) is developed to deal with the problem. Moreover, the effect of some dispatching rules for generating initial solutions are studied. A Taguchi-based design of experience approach has been followed to determine the effect of the different values of the parameters on the performance of the algorithm. To evaluate the performance of the proposed PSO, a large number of benchmark problems are selected from the literature and solved with different due date and penalty settings. Computational results confirm that the proposed PSO is efficient and competitive; the developed framework is able to improve many of the best-known solutions of the test problems available in the literature.     

Generating collision-free tool orientations for 5-axis NC machining with a short ball-end cutter

A novel tool orientation optimisation algorithm is proposed for 5-axis NC machining with a short ball-end cutter. It can generate collision-free and smooth tool orientations along with a safe and shortest tool length (SSTL). The use of shorter cutters without collision is a key advantage of 5-axis machining because the magnitude of tool deflection and the stability of cutting process are greatly affected by the slenderness ratio of the cutter. Existing methods can calculate the SSTL in the NC simulation process. However, the SSTL is essentially determined by the tool orientations and should be considered in the process of tool path generation. To overcome this limitation, a new tool orientation optimisation algorithm is proposed. The SSTL is determined by optimising the tool orientations under the constraints of global collision avoidance and tool orientation smoothness. The algorithm first computes the global accessibility cone and the SSTL along each accessible tool orientation. Then the tool orientations are optimised based on the discrete dynamic programming with the SSTL along the whole tool path being the optimisation objective. Finally, the tool path is generated by globally smoothing the tool orientations. Computational examples and cutting experiment are given to illustrate the validity and efficiency of the proposed algorithm.     

Ant colony optimisation with parameterised search space for the job shop scheduling problem

The job-shop scheduling problem (JSSP) is known to be NP-hard. Due to its complexity, many metaheuristic algorithm approaches have arisen. Ant colony metaheuristic algorithm, lately proposed, has successful application to various combinatorial optimisation problems. In this study, an ant colony optimisation algorithm with parameterised search space is developed for JSSP with an objective of minimising makespan. The problem is modelled as a disjunctive graph where arcs connect only pairs of operations related rather than all operations are connected in pairs to mitigate the increase of the spatial complexity. The proposed algorithm is compared with a multiple colony ant algorithm using 20 benchmark problems. The results show that the proposed algorithm is very accurate by generating 12 optimal solutions out of 20 benchmark problems, and mean relative errors of the proposed and the multiple colony ant algorithms to the optimal solutions are 0.93% and 1.24%, respectively.     

A genetic algorithm extended modified sub-gradient algorithm for cell formation problem with alternative routings

This paper addresses the cell formation problem with alternative part routes. The problem is considered in the aspect of the natural constraints of real-life production systems such as cell size, separation and co-location constraints. Co-location constraints were added to the proposed model in order to deal with the necessity of grouping certain machines in the same cell for technical reasons, and separation constraints were included to prevent placing certain machines in close vicinity. The objective is to minimise the weighted sum of the voids and the exceptional elements. A hybrid algorithm is proposed to solve this problem. The proposed algorithm hybridises the modified sub-gradient (MSG) algorithm with a genetic algorithm. MSG algorithm solves the sharp augmented Lagrangian dual problems, where zero duality gap property is guaranteed for a wide class of optimisation problems without convexity assumption. Generally, the dual problem is solved by using GAMS solvers in the literature. In this study, a genetic algorithm has been used for solving the dual problem at the first time. The experimental results show the advantage of combining the MSG algorithm and the genetic algorithm. Although the MSG algorithm, whose dual problem is solved by GAMS solver, and the genetic algorithm cannot find feasible solutions, hybrid algorithm generates feasible solutions for all of the test problems.