An ant colony system-based hybrid algorithm for square root concave cost transhipment problems

Concave cost transhipment problems are difficult to optimally solve for large-scale problems within a limited period of time. Recently, some modern meta-heuristics have been employed for the development of advanced local search based or population-based stochastic search algorithms that can improve the conventional heuristics. Besides these meta-heuristics, the ant colony system algorithm is a population-based stochastic search algorithm which has been used to obtain good results in many applications. This study employs the ant colony system algorithm, coupled with some genetic algorithm and threshold accepting algorithm techniques, to develop a population based stochastic search algorithm for efficiently solving square root concave cost transhipment problems. The developed algorithms are evaluated with a number of problem instances. The results indicate that the proposed algorithm is more effective for solving square root concave cost transhipment problems than other recently designed local search based algorithms and genetic algorithm.     

Cutting Plane and Branch and Bound for Solving a Class of Scheduling Problems

Two general purpose integer programming algorithms, one a fractional cutting-plane algorithm and the other a branch-and-bound algorithm, were investigated. The cutting-plane algorithm easily solves an important class of integer problems, a class of scheduling problems for the assigning of personnel to work shifts over a fixed period of time. Scheduling problems were constructed with 14 to 189 integer variables and with 14 to 21 constraints. The general branch-and-bound search was not effective on this class of scheduling problems, but it was effective on the classical test problems found in the literature of integer programming, many of which were not handled by the cutting-plane algorithm.     

Scheduling with shutdowns and sequence dependent set-up times

This paper considers a single machine scheduling problem with ready and due times constraints on jobs, shutdown constraints on the machine and sequence dependent set-up times among jobs. The shutdown is a disruptive event such as holiday, breaks or machine maintenance, and has a prespecified period when the machine will be interrupted. If no pre-emption is allowed for jobs, shutdown constraints divide the planning horizon into disconnected time windows. An optimization algorithm based on the branch-and-bound method is developed to minimize the maximum tardiness for solving the problem. This paper further develops the post-processing algorithm that manipulates the starting time of the shutdown period so as to reduce the obtained maximum tardiness. The post-processing algorithm can determine plural schedules to reduce the maximum tardiness, and the production manager will select the objective schedule among them for the interest of overall efficiency. Computational results for the proposed algorithms will indicate that the post-processing algorithm can improve upon the original solution and the problems with multiple shutdowns and with set-up times varying widely can be satisfactorily solved.     

基于周期采样的数据流频繁项集挖掘算法研究

针对用于数据流频繁项集挖掘的现有方法存在引入过多次频繁项集以及时空性能与输出精度较低的问题,利用Chebyshev不等式,构造了项集频度周期采样的概率误差边界,给出了动态检测项集支持度变化方法.提出了一种基于周期采样的数据流频繁项集挖掘算法FI-PS,该算法通过跟踪项集支持度变化确定项集支持度的稳定性,并以此作为调整窗口大小以及采样周期的依据,从而以一个较大的概率保证项集支持度误差有上界.理论分析及实验证明该算法有效,在保证挖掘结果准确度相对较好的条件下,可获得较优执行性能.     

An Economic Lot Size Model for Perishable Products with Age-Dependent Inventory and Backorder Costs

This paper presents an Economic Lot Size (ELS) model for perishable products where the costs of holding inventory stocks (having backorders) in each period depend on the age of inventories (backorders). We propose a polynomial-time dynamic programming algorithm to solve two structured problems, one with non-decreasing demands and the other with non-decreasing marginal backorder cost with respect to the age of the backorder. Our results generalize a recent study on an ELS model for perishable product but without backorders.     

基于AFSA-GA串行算法的桥式起重机主梁轻量化设计

针对传统设计中因采用理论与经验相结合的方法而导致的桥式起重机主梁设计周期长、截面尺寸大、材料利用率低及设计成本与制造成本高等问题，提出以优势互补为理念的串行算法，即采用2种算法循环执行多次，直到满足输出要求。充分利用遗传算法（genetic algorithm,GA）全局快速收敛，人工鱼群算法（artificial fish swarm algorithm,AFSA）在小变量范围中求解精度较高、稳定性好等优势，通过在AFSA中增加缩小变量范围模块来构建AFSA-GA串行算法。选用3种类型测试函数对AFSA-GA进行可行性验证，并将AFSA-GA应用于50 t/22.5 m的桥式起重机主梁轻量化设计，以验证该串行算法的实用性。结果表明AFSA-GA在求解精度、收敛速度、鲁棒性方面满足工程实际要求，且具有适用性。工程实证表明AFSA-GA串行算法可应用于桥式起重机主梁轻量化设计，可达到缩短设计周期、减小截面尺寸及提高材料利用率的目的。     

一种运动目标位置合成的快速算法

研究用经纬仪测定运动目标位置过程中的有关问题。为保证算法的实时性,采用直线插值方法。根据非整数倍周期时的偏差量,给出偏差量在整数倍周期时的带有延时作为参数的表示式。利用这一表示式,在目标作匀加速运动的前提下提出了延时的辨识方法,从而解决了目标位置合成中的难题。     

Covariance matrix adapted evolution strategy algorithm-based solution to dynamic economic dispatch problems

This article presents a covariance matrix adapted evolution strategy (CMAES) algorithm to solve dynamic economic dispatch (DED) problems. The DED is an extension of the conventional economic dispatch problem, in which optimal settings of generator units are determined with a predicted load demand over a period of time. In this article, the applicability and validity of the CMAES algorithm is demonstrated on three DED test systems with a sequential decomposition approach. The results obtained using the CMAES algorithm are compared with results obtained using the real-coded genetic algorithm, the Nelder–Mead simplex method, and other methods from the literature. To compare the performance of the various algorithms, statistical measures like best, mean, worst, standard deviation, and mean computation time over 20 independent runs are taken. The effect of population size on the performance of the CMAES algorithm is also investigated. The simulation experiments reveal that the CMAES algorithm performs better in terms of fuel cost and solution consistency. Karush–Kuhn–Tucker conditions are applied to the solutions obtained using the CMAES algorithm to verify optimality. It is found that the obtained results satisfy the Karush–Kuhn–Tucker conditions and confirm optimality.     

A new optimization algorithm for solving complex constrained design optimization problems

This article presents the performance of a very recently proposed Jaya algorithm on a class of constrained design optimization problems. The distinct feature of this algorithm is that it does not have any algorithm-specific control parameters and hence the burden of tuning the control parameters is minimized. The performance of the proposed Jaya algorithm is tested on 21 benchmark problems related to constrained design optimization. In addition to the 21 benchmark problems, the performance of the algorithm is investigated on four constrained mechanical design problems, i.e. robot gripper, multiple disc clutch brake, hydrostatic thrust bearing and rolling element bearing. The computational results reveal that the Jaya algorithm is superior to or competitive with other optimization algorithms for the problems considered.     

An artificial bee colony algorithm for the economic lot scheduling problem

In this study, we present an artificial bee colony (ABC) algorithm for the economic lot scheduling problem modelled through the extended basic period (EBP) approach. We allow both power-of-two (PoT) and non-power-of-two multipliers in the solution representation. We develop mutation strategies to generate neighbouring food sources for the ABC algorithm and these strategies are also used to develop two different variable neighbourhood search algorithms to further enhance the solution quality. Our algorithm maintains both feasible and infeasible solutions in the population through the use of some sophisticated constraint handling methods. Experimental results show that the proposed algorithm succeeds to find the all the best-known EBP solutions for the high utilisation 10-item benchmark problems and improves the best known solutions for two of the six low utilisation 10-item benchmark problems. In addition, we develop a new problem instance with 50 items and run it at different utilisation levels ranging from 50 to 99% to see the effectiveness of the proposed algorithm on large instances. We show that the proposed ABC algorithm with mixed solution representation outperforms the ABC that is restricted only to PoT multipliers at almost all utilisation levels of the large instance.     

Applying simulated annealing to the open shop scheduling problem

This paper addresses the problem of scheduling a nonpreemptive open shop with the objective of minimizing makespan. A neighborhood search algorithm based on the simulated annealing technique is proposed. The algorithm is tested on randomly generated problems, benchmark problems in the literature, and new hard problems generated in this paper. Computational results show that the algorithm performs well on all of the test problems. In many cases, an optimum solution is found, and in others the distance from the optimum or lower bound is quite small. Moreover, some of the benchmark problems in the literature are solved to optimality for the first time.     

The machine layout problem in robot cells

This paper addresses the machine layout problem in a flexible manufacturing cell served by a robot. The objective of the proposed approach is to obtain the optimum values of the locations and orientations of machines and the corresponding feasible configurations of the robot at each input/output location. Two optimization criteria have been considered, the travel time and the total joint displacement for all possible sequences of operations required by the robot at a given period of time. Non-linear optimization models are proposed which can be applied not only to a planar robot but also to an industrial one. The optimization problems were solved by a sequential quadratic programming algorithm.     

Dynamic-demand capacitated facility location problems with and without relocation

We consider two multi-period dynamic-demand capacitated location problems. In the first problem, the facilities are allowed to be relocated in each period, whereas in the second they are kept at a fixed location determined at the beginning of the planning horizon. We provide Lagrangian Relaxation and Benders Decomposition algorithms, including an ?-optimal BD algorithm, for the solution for the first model and a Benders Decomposition algorithm for the second. For detailed analysis, we generate a wide variety of instances to test the performance of the algorithms by taking into account varying number of customer locations and time periods in the planning horizon as well as fixed cost structures and facility capacities. We observe that the efficiency of the solution algorithms depends on the input data structure, specifically the cost structures, the facility capacities (which, in turn, dictate the expected number of open facilities), and the variation in the total customer demand from period to period.     

Solving the facility and layout and location problem by ant-colony optimization-meta heuristic

This paper describes a heuristic algorithm for solving the plant/facility location problem by applying ant-colony optimization meta-heuristic. The facility location problem is discussed, and a mathematical formulation is presented. The problem is then modelled as a quadratic assignment problem. An ant algorithm is developed to solve the problem. The results reveal that the proposed algorithm can be adaptively constructed to solve discrete plant location problems. This has been applied to a set of known test problems and appears to be able to compete with other current solutions with encouraging results.     

Analytical selection of masters for the reduced eigenvalue problem

Masters are defined as the degrees-of-freedom that are retained in the reduced eigenvalue problem. Various qualitative guidelines to select masters are published in the literature, but it is difficult to apply them to complex structures. In this paper a computational algorithm to select masters for complex structures is presented. This algorithm is based on a guideline¹⁴ which assures that the associated Guyan reduction process is valid. This algorithm eliminates one degree-of-freedom at a time satisfying the guideline, and preserves lower frequencies in the reduced eigenvalue problem. The algorithm presented in this paper is used to select masters for four different structural models. The natural frequencies of the associated reduced eigenvalue problems are calculated and compared with those calculated from the full eigenvalue problems.     

Computational Experience with a Sequencing Algorithm Adapted to the Tardiness Problem

This paper summarizes computational experience with a generalized dynamic programming algorithm known as the Chain Algorithm. This algorithm is a general purpose procedure for solving sequencing problems, and in this study the procedure is adapted to the problem of minimizing total tardiness in the single-machine model. The results indicate that at the present state of the art, 50-job problems can normally be solved in a few seconds of computer time, although memory requirements may be extensive.     

A Stepwise partial enumeration algorithm for the economic lot scheduling problem

This paper presents a stepwise partial enumeration algorithm for determining the economic lot schedule of a multiproduct single facility system on a repetitive basis. The algorithm is based on a simple “sufficient feasibility” test. The algorithm starts from a feasible schedule determined from the common cycle solution and continues stepwise partial enumerations to improve the schedule until no appreciable improvement occurs. Performance of the algorithm is demonstrated by solving six problems recently solved by Haessler. The algorithm gives better or equal solutions to the problems.     

NON-LINEAR STRUCTURAL RESPONSE USING ADAPTIVE DYNAMIC RELAXATION ON A MASSIVELY PARALLEL-PROCESSING SYSTEM

A parallel adaptive dynamic relaxation (ADR) algorithm has been developed for non-linear structural analysis. This algorithm has minimal memory requirements, is easily parallelizable and scalable to many processors, and is generally very reliable and efficient for highly non-linear problems. Performance evaluations on single-processor computers have shown that the ADR algorithm is reliable and highly vectorizable, and that it is competitive with direct solution methods for the highly non-linear problems considered. The present algorithm is implemented on the 512-processor Intel Touchstone DELTA system at Caltech, and it is designed to minimize the extent and frequency of interprocessor communication. The algorithm has been used to solve for the non-linear static response of two- and three-dimensional hyperelastic systems involving contact. Impressive relative speed-ups have been achieved and demonstrate the high scalability of the ADR algorithm. For the class of problems addressed, the ADR algorithm represents a very promising approach for parallel-vector processing.     

MULTIOBJECTIVE DESIGN OPTIMIZATION BY AN EVOLUTIONARY ALGORITHM

This paper presents an evolutionary algorithm for generic multiobjective design optimization problems. The algorithm is based on nondominance of solutions in the objective and constraint space and uses effective mating strategies to improve solutions that are weak in either. Since the methodology is based on nondominance, scaling and aggregation affecting conventional penalty function methods for constraint handling does not arise. The algorithm incorporates intelligent partner selection for cooperative mating. The diversification strategy is based on niching which results in a wide spread of solutions in the parametric space. Results of the algorithm for the design examples clearly illustrate the efficiency of the algorithm in solving multidisciplinary design optimization problems.     

A Swarm Metaphor for Multiobjective Design Optimization

This paper presents a new optimization algorithm to solve multiobjective design optimization problems based on behavioral concepts similar to that of a real swarm. The individuals of a swarm update their flying direction through communication with their neighboring leaders with an aim to collectively attain a common goal. The success of the swarm is attributed to three fundamental processes: identification of a set of leaders, selection of a leader for information acquisition, and finally a meaningful information transfer scheme. The proposed algorithm mimics the above behavioral processes of a real swarm. The algorithm employs a multilevel sieve to generate a set of leaders, a probabilistic crowding radius-based strategy for leader selection and a simple generational operator for information transfer. Two test problems, one with a discontinuous Pareto front and the other with a multi-modal Pareto front is solved to illustrate the capabilities of the algorithm in handling mathematically complex problems. Three well-studied engineering design optimization problems (unconstrained and constrained problems with continuous and discrete variables) are solved to illustrate the efficiency and applicability of the algorithm for multiobjective design optimization. The results clearly indicate that the swarm algorithm is capable of generating an extended Pareto front, consisting of well spread Pareto points with significantly fewer function evaluations when compared to the nondominated sorting genetic algorithm (NSGA).