Local search heuristics for two-stage flow shop problems with secondary criterion

This paper develops and compares different local search heuristics for the two-stage flow shop problem with makespan minimization as the primary criterion and the minimization of either the total flow time, total weighted flow time, or total weighted tardiness as the secondary criterion. We investigate several variants of simulated annealing, threshold accepting, tabu search, and multi-level search algorithms. The influence of the parameters of these heuristics and the starting solution are empirically analyzed. The proposed heuristic algorithms are empirically evaluated and found to be relatively more effective in finding better quality solutions than the existing algorithms.Scope and purposeTraditional research to solve multi-stage scheduling problems has focused on single criterion. However, in industrial scheduling practices, managers develop schedules based on multi-criteria. Scheduling problems involving multiple criteria require significantly more effort in finding acceptable solutions and hence have not received much attention in the literature. This paper considers one such multiple criteria scheduling problem, namely, the two-machine flow shop problem where the primary criterion is the minimization of makespan and the secondary criterion is one of the three most popular performance measures, namely, the total flow time, total weighted flow time, or total weighted tardiness. Based on the principles of local search, development of heuristic algorithms, that can be adapted for several multi-criteria scheduling problems, is discussed. Using the example of the two-machine flow shop problem with secondary criterion, computational experiments are used to evaluate the utility of the proposed algorithms for solving scheduling problems with a secondary criterion.     

Nonlinear analysis of truss by energy minimization

New analysis methods for trusses with material and geometric nonlinearity are presented using the energy principles and modified sequential quadratic programming (SQP) algorithms.The analysis problem of a truss with material nonlinearity is formulated as the total complementary energy minimization problem and the member forces are determined by using modified SQP algorithms.The truss subject to nonlinearities both in material properties and finite displacements is solved by the combination of complementary and potential energy minimization algorithms.The problem formulations on the basis of energy principles are quite simple and the proposed analysis methods can be applicable for any type of nonlinear material problem. The efficiency and reliability of the proposed method are clarified by giving numerical results for 3–33-bar statically indeterminate trusses with three types of nonlinear materials.     

Modified iterated simulated annealing algorithm for structural synthesis

A new hybrid simulated annealing method is presented for the optimization of structural systems subjected to dynamic loads. The optimization problem is formulated as a structural weight minimization, with time-varying constraints on floor displacements, velocities, accelerations, or floor drifts, and structural member combined stresses. In addition, time-invariant constraints on structural frequencies and member sizes that will satisfy the strong column–weak beam philosophy of the building codes can be imposed. The method uses elements of existing simulated annealing algorithms and introduces certain new procedures. Firstly, the search range is automatically reduced, by using the updated information of the current design, at each iteration. Secondly, the inner and outer iteration loops are implemented. Thirdly, sensitivity analysis of the time-varying global displacements is performed with respect to the design variables that are the structural member cross-sectional areas. The results of the sensitivity analysis identify which design variables must be modified to decrease the global displacements in the most effective manner. However, once the variables are identified from the sensitivity analysis, the new values of these variables are determined in a random manner. The possibility of attaining a global minimum is thus maintained. The method is suited for structural optimization problems with time-varying constraints because the annealing is a random search technique and can locate global rather than local minima.     

A posteriori error estimator and adaptive procedures for computation of shakedown and limit loads on pressure vessels

Adaptive finite element procedures are presented for the computation of upper bounds estimates of limit and shakedown loads for pressure vessels. The method consists of an h-type adaptive mesh refinement strategy based upon an a-posteriori error estimator measured by the energy norm. The problem is formulated in a kinematic approach using Koiter's shakedown theorem. A constitutive model, for elastic-perfectly plastic materials, relates the plastic strains increments and curvatures to plastic multipliers through the flow law associated with a shell piecewise-linear yield surface (hexagonal prism). A consistent relationship between nodal displacements and nodal plastic multipliers is enforced by minimizing the strain residual between the total strain and the plastic strain increments, which is measured with respect to the energy norm. Discretization of the shell into finite elements allows the reduction of the problem to a minimization problem which is solved by linear programming.     

Optimum design of plano-milling machine structure using finite element analysis

The problem of optimum design of plano-milling machine structure is formulated as a nonlinear mathematical programming problem with the objective of minimizing the structural weight. The plano-milling machine structure is idealized with triangular plate elements and three dimensional frame elements based on finite element displacement method. Constraints are placed on static deflections and principal stresses in the problem formulation. The optimization problem is solved by using an interior penalty function method in which the Davidon-Fletcher-Powell variable metric unconstrained minimization technique and cubic interpolation method of one dimensional search are employed. A numerical example is presented for demonstrating the effectiveness of the procedure outlined. The results of sensitivity analysis conducted with respect to design variables and fixed parameters about the optimum point are also reported.     

An efficient technique for finding the desired global optimum of robotic joint displacement

For an industrial robot on a daily operation basis such as pick and place, it is desired to minimize the robotic joint displacements when moving the robot from one location to another. The objective of the optimization here is to simultaneously minimize a robot end effector's positional error and the robotic joint displacements. By modifying the searching algorithm in the existing complex optimization method, this article presents a technique for finding the desired global optimum solution more efficiently. To compare the optimum searching capability between the proposed and existing searching algorithms, a modified Himmelblau's function is used as an objective function. The presented technique is then applied to a spatial three-link robot manipulator for global minimization of the joint displacements. © 1992 John Wiley & Sons, Inc.     

Estimating software project effort using analogies

Accurate project effort prediction is an important goal for the software engineering community. To date most work has focused upon building algorithmic models of effort, for example COCOMO. These can be calibrated to local environments. We describe an alternative approach to estimation based upon the use of analogies. The underlying principle is to characterize projects in terms of features (for example, the number of interfaces, the development method or the size of the functional requirements document). Completed projects are stored and then the problem becomes one of finding the most similar projects to the one for which a prediction is required. Similarity is defined as Euclidean distance in n-dimensional space where n is the number of project features. Each dimension is standardized so all dimensions have equal weight. The known effort values of the nearest neighbors to the new project are then used as the basis for the prediction. The process is automated using a PC-based tool known as ANGEL. The method is validated on nine different industrial datasets (a total of 275 projects) and in all cases analogy outperforms algorithmic models based upon stepwise regression. From this work we argue that estimation by analogy is a viable technique that, at the very least, can be used by project managers to complement current estimation techniques     

Minimum weight design of membrane structures

Algorithms to find the minimum weight design of a 3-dimensional membrane—rod structure are presented. Constraints are on strength and displacements. Variables are ply thicknesses, cross section areas, angles of orthotropy and node point coordinates in a FE-approximation.

To solve the optimization problem a sequence of strictly convex subproblems is created. Each subproblem is solved by using the duality theory for convex programming.

Results are presented for a delta-wing, a tower and a bridge structure.     

Chaotic local search algorithm

The steepest descent search algorithm is modified in conjunction withchaos to solve the optimization problem of an unstructured search space. The problem is that given only the gradient information of the quality function at the present configuration,X(t), we must find the value of a configuration vector that minimizes the quality function. The proposed algorithm starts basically from the steepest descent search technique but at the prescribed points, i.e., local minimum points, the chaotic jump is performed by the dynamics of a chaotic neuron. Chaotic motions are mainly caused because the Gaussian function has a hysteresis as a refractoriness. An adaptation mechanism to adjust the size of the chaotic jump is also given. In order to enhance the probability of finding the global minimum, a parallel search strategy is developed. The validity of the proposed method is verified in simulation examples of the function minimization problem and the motion planning problem of a mobile robot. This work was presented, in part, at the International Symposium on Artificial Life and Robotics, Oita, Japan, February 18–20, 1996     

Iterated local search algorithms for the Euclidean Steiner tree problem in n dimensions

We propose algorithmic frameworks based on the iterated local search (ILS) metaheuristic to obtain good‐quality solutions for the Euclidean Steiner tree problem (ESTP) in n dimensions. This problem consists in finding a tree with minimal total length that spans p points given in an n‐dimensional Euclidean space and, eventually, also some additional points whose insertion contributes to reduce the total length of the tree. These ILS approaches make use of both the tree enumeration structure, called topology‐describing vector, and the exact minimization step of a well‐known branch‐and‐bound method for the ESTP. Computational results are provided.     

变邻域搜索算法求解机器人制造单元调度问题——排序依赖转换时间

针对排序依赖转换时间的两机器机器人制造单元调度问题的NP难特性,设计了变邻域搜索算法求解。为了加快算法收敛速度,设计了工件阻塞时间最小化生成初始解;为了搜索到更好解,分析了算法的参数取值。通过随机产生算例测试,提出算法优于模拟退火算法,证实了提出算法的有效性。     

Optimal machining conditions with dual criteria and applications to scheduling

A bicriterion machining economics problem is presented, considering the minimization of the unit production cost and the maximization of the production rate. The bicriterion machining time is first defined as a weighted average of the maximum production rate machining time and of the minimum unit cost machining time using a weighted-sums technique and an arbitrary weighting factor. Then using a vector-maximum approach, a bicriterion machining lime is defined through the introduction of an optimal weighting factor. This weighting factor reflects the relative importance of the two criteria and it is a function of the delay time cost, that is, the cost associated with the difference in actual processing times between the two criteria. It is shown that the vector-maximum approach outperforms the weighting-sums technique. Furthermore, the bicriterion machining lime leans towards the maximum production rate machining time as the delay time cost increases. It is also shown that the actual processing time is proportional to a machining constant regardless of the objective function utilized when tools with similar characteristics are used. Based upon this finding the mean flowtime can be minimized by processing the parts in ascending order of the machining constant values.     

An elastic-plastic analysis of non-axisymmetric structures

Previously a method of analyzing elastic non-axisymmetric problems was developed. This method involved dividing the structure into segments in the r−θ plane and performing an axisymmetric analysis. The displacements were then forced to match at selected nodes. This yields a set of perturbation displacements for each segment. The total displacement in the structure is the axisymmetric displacement plus the perturbation displacement.

In this study this method is expanded to include elastic-plastic material behavior with strain hardening effects. For the elastic-plastic analysis the von Mises-Hencky yield condition and the Prager, or kinematic, strain hardening rule are used. The method is applied to a number of examples to test its accuracy. Numerical results are presented and discussed.     

The conjugate gradient method for optimal control problems

This paper extends the conjugate gradient minimization method of Fletcher and Reeves to optimal control problems. The technique is directly applicable only to unconstrained problems; if terminal conditions and inequality constraints are present, the problem must be converted to an unconstrained form; e.g., by penalty functions. Only the gradient trajectory, its norm, and one additional trajectory, the actual direction of search, need be stored. These search directions are generated from past and present values of the objective and its gradient. Successive points are determined by linear minimization down these directions, which are always directions of descent. Thus, the method tends to converge, even from poor approximations to the minimum. Since, near its minimum, a general nonlinear problem can be approximated by one with a linear system and quadratic objective, the rate of convergence is studied by considering this case. Here, the directions of search are conjugate and hence the objective is minimized over an expanding sequence of sets. Also, the distance from the current point to the miminum is reduced at each step. Three examples are presented to compare the method with the method of steepest descent. Convergence of the proposed method is much more rapid in all cases. A comparison with a second variational technique is also given in Example 3.     

Study on Robot Path Planning Based on an Improved Artificial Potential Field Method

The method of artificial potential field has obvious advantages among the robot path planning methods including simple structure, small amount of calculation and relatively mature in theory. This paper puts forward the ＂Integral method＂ focusing on solving the problem of local minimization. The method analyses the distribution of obstructions in a given environment and regards adjacent obstacles as a whole, By changing the parameters of the repulsive force field, robots can quickly get out of the minimum point and move to the target point. This paper uses the Simurosot platform to carry on the simulation experiment on the improved artificial potential field method, which projects a feasible path successfully and verifies this method.     

Optimization of distributed tree queries

In this paper the problem of finding an optimum strategy of semi joins for solving tree queries is studied under the objective of total time minimization. Tree queries that are conjunctions of equi-join clauses such that any two relations in the query have at most one attribute in common are considered. This class of tree queries is a superset of classes of tree queries, such as chain queries and simple queries, that have been studied for semi-join optimization in the literature. An algorithm based on dynamic programming to find the optimum semi-join strategy for a given query is presented. The search space for finding the optimum is reduced by eliminating strategies that can never be the optimum. This is accomplished by utilizing a set of properties that a potentially optimum strategy should satisfy.     

Mathematical observations in structural dynamics

In dynamic structural analysis, the basic relations between forces and displacements for a beam element subjected to axial, torsional or flexural vibration are obtained either by solving the appropriate equation of motion or by using an approximate method. The exact equation leads to the dynamic stiffness matrix while the approximate method results in the superposition of elastic and inertial forces represented respectively by the stiffness and mass matrices.The common procedure in finding the natural frequencies is to set the determinant of the dynamic stiffness matrix for the system equal to zero. The approximate method leads to an eigenvalue type problem while the exact method results in a transcendental equation of trigonometric and hyperbolic functions. The natural frequencies in a region of interest are found by a systematic search in the determinntal function.The purpose of this paper is to show that the search technique cannot be applied for certain values of the argument at which the determinantal function is not defined. It is proved that the natural frequencies of any isolated member in the system are critical values for the determinantal function. A practical method is given to obviate the difficulty in order to find the natural frequencies from the determinant, including the critical values at which the dynamic stiffness matrix is not defined. Also, as part of this investigation, the mathematical relation is established between the dynamic stiffness matrix derived by the approximate finite element method and the results obtained from the exact Bernoulli-Euler equation for flexural vibration or the wave equation for axial or torsional vibration.     

A target-based color space for sea target detection

Sea target detection is a vital application for military and navigation purposes. A new supervised clustering method based on the combination of the PSO and FCM techniques is presented for the sea target detection problem. The color components of the target and non-target pixels in the RGB color space are used as features to train the classification algorithm. The new classifier is presented in the form of a new color space which we call the Target-based Color Space (TCS); in fact the RGB color space is converted to this new space through a 3×3 matrix. The Particle Swarm Optimization (PSO) algorithm is then used to search for the optimum weights of the conversion matrix which results in a more discriminating clustering space between the target and non-target pixels. In other words, solving the optimization problem, minimization of the objective function of the FCM clustering technique in linear and quadratic transform domain (with a NP-hard problem in quadratic conversion), is done using the PSO algorithm. The main objective of this work is to demonstrate the efficiency of using just color features, as well as color space conversion in the classification domain. Experimental results show the efficiency of new method in finding sea targets in color images.     

The optimal location of inspection stations using a rule-based methodology

The location of inspection stations is a significant component of production systems. In this paper, a prototype expert system is designed for deciding the optimal location of inspection stations. The production system is defined as a single channel of n serial operation stations. The potential inspection station can be located after any of the operation stations. Non-conforming units are generated from a compound binomial distribution with known parameters at any given operation station.

Traditionally Dynamic programming, Zero-one integer programming or Non-linear programming techniques are used to solve this problem. However a problem using these techniques is that the computation time becomes prohibitively large when the number of potential inspection stations are fifteen or more. An expert system has the potential to solve this problem using a rule-based system to determine the near optimal location of inspection stations.

The prototype expert system is divided into a static database, dynamic database and knowledge base. Based on defined production systems, the sophisticated rules are generated by the simulator as part of a knowledge base. A generate-and-test inference mechanism is utilized to search the solution space by applying appropriate symbolic and quantitative rules. The goal of the system is to determine the location of inspection stations while minimizing total cost.     

Evolutionary topology optimization of continuum structures with a global displacement control

The conventional compliance minimization of load-carrying structures does not directly deal with displacements that are of practical importance. In this paper, a global displacement control is realized through topology optimization with a global constraint that sets a displacement limit on the whole structure or certain sub-domains. A volume minimization problem is solved by an extended evolutionary topology optimization approach. The local displacement sensitivities are derived following a power-law penalization material model. The global control of displacement is realized through multiple local displacement constraints on dynamically located critical nodes. Algorithms are proposed to secure the stability and convergence of the optimization process. Through numerical examples and by comparing with conventional stiffness designs, it is demonstrated that the proposed approach is capable of effectively finding optimal solutions which satisfy the global displacement control. Such solutions are of particular importance for structural designs whose deformed shapes must comply with functioning requirements such as aerodynamic performances.