Genetic algorithms and simulated annealing for scheduling in agile manufacturing

In this paper, genetic algorithms and simulated annealing are applied to scheduling in agile manufacturing. The system addressed consists of a single flexible machine followed by multiple identical assembly stations, and the scheduling objective is to minimize the makespan. Both genetic algorithms and simulated annealing are investigated based on random starting solutions and based on starting solutions obtained from existing heuristics in the literature. Overall, four new algorithms are developed and their performance is compared to the existing heuristics. A 2³ factorial experiment, replicated twice, is used to compare the performance of the various approaches, and identify the significant factors that affect the frequency of resulting in the best solution and the average percentage deviation from a lower bound. The results show that both genetic algorithms and simulated annealing outperform the existing heuristics in many instances. In addition, simulated annealing outperforms genetic algorithms with a more robust performance. In some instances, existing heuristics provide comparable results to those of genetic algorithms and simulated annealing with the added advantage of being simpler. Significant factors and interactions affecting the performance of the various approaches are also investigated.     

Simulated annealing based parallel genetic algorithm for facility layout problem

The facility layout problem (FLP), a typical combinational optimisation problem, is addressed in this paper by implementing parallel simulated annealing (SA) and genetic algorithms (GAs) based on a coarse-grained model to derive solutions for solving the static FLP with rectangle shape areas. Based on the consideration of minimising the material flow factor cost (MFFC), shape ratio factor (SRF) and area utilisation factor (AUF), a total layout cost (TLC) function is derived by conducting a weighted summation of MFFC, SRF and AUF. The evolution operations (including crossover, mutation, and selection) of GA provide a population-based global search in the space of possible solutions, and the SA algorithm can lead to an efficient local search near the optimal solution. By combing the characteristics of GA and SA, better solutions will be obtained. Moreover, the parallel implementation of simulated annealing based genetic algorithm (SAGA) enables a quick search for the optimal solution. The proposed method is tested by performing a case study simulation and the results confirm its feasibility and superiority to other approaches for solving FLP.     

A simulated annealing algorithm based on a closed loop layout for facility layout design in flexible manufacturing systems

Facility layout design problems in flexible manufacturing systems (FMS) differ from traditional facility design problems and are more difficult to solve because there are more constraints that must be considered (i.e., cell shape, cell orientation, pick-up and drop-off point positions). The focus of this paper is on the closed loop type layout, which is based on a predetermined layout pattern. This layout pattern is commonly found in manufacturing settings since it requires a simplified material handling system configuration and since it facilitates a modular and expandable layout structure. The open-field type layout problem, where there is no predetermined layout pattern, may potentially have a more efficient configuration, since there are fewer restrictions. However, this problem is more difficult to solve and may result in configurations that are not desirable due to the lack of structure or modularity. The procedure developed in this paper improves the efficiency of the closed loop configuration by changing the rectangular shape of the loop to different sizes. In many cases, the resulting closed loop layout proves to be as efficient as the open field layout. A simulated annealing procedure (SA-CL) is used to search for the configuration that minimizes the total material handling costs. A comparison of the results with existing methods indicates that, based on solution quality and computational time, the SA-CL offers a favourable alternative for efficient layout design.     

Solving structural optimization problems with genetic algorithms and simulated annealing

In this paper we study the performance of two stochastic search methods: Genetic Algorithms and Simulated Annealing, applied to the optimization of pin‐jointed steel bar structures. We show that it is possible to embed these two schemes into a single parametric family of algorithms, and that optimal performance (in a parallel machine) is obtained by a hybrid scheme. Examples of applications to the optimization of several real steel bar structures are presented. Copyright © 1999 John Wiley & Sons, Ltd.     

一种混合优化策略在工步排序中的应用

结合创成式ＣＡＰＰ系统中工步优化问题，介绍了由遗传算法（ＧｅｎｅｔｉｃＡｌｇｏｒｉｔｈｍｓ，ＧＡ）和模拟退火算法（ＳｉｍｕｌａｔｅｄＡｎｎｅａｌｉｎｇＡｌｇｏｒｉｔｈｍｓ，ＳＡ）构成的混合寻优策略。最后以一箱体的工艺规划过程为例，将基于混合寻优策略的工步排序融入以加工中心为主要加工设备的ＣＡＰＰ工艺决策过程。     

A simulated annealing method for design of laminates with required stiffness properties

Designing a laminate based on its stiffness properties requires finding the optimum lamination stacking sequence to yield the required stiffness properties. The design variables to be considered are the number of layers and orientation angle of fibers in each layer group, which are treated as discrete-variables. The optimum lamination is then obtained by minimizing a cost function composed of the relative difference between the calculated effective stiffness properties and weight of trial laminate and the desired properties. This error minimization problem was solved using a modified simulated annealing heuristic method. The new simulated annealing implementation comprises a cooling procedure in which the temperature decrease relied adaptively on the objective function evolution. It is shown that the proposed method can give rise to an improvement in convergence speed. To achieve a further improvement in the performance of the method, simulated annealing parallelization implemented using the proposed cooling process. The main features of this algorithm are described and its encouraging results are presented.     

Effective hybrid genetic algorithm for minimizing makespan on a single-batch-processing machine with non-identical job sizes

The paper addresses minimizing makespan by a genetic algorithm (GA) for scheduling jobs with non-identical sizes on a single-batch-processing machine. A batch-processing machine can process up to B jobs simultaneously. The processing time of a batch is equal to the longest processing time among all jobs in the batch. Two different GAs are proposed based on different encoding schemes. The first is a sequence-based GA (SGA) that generates random sequences of jobs using GA operators and applies the batch first fit heuristic to group the jobs. The second is a batch-based hybrid GA (BHGA) that generates random batches of jobs using GA operators and ensures feasibility by using knowledge of the problem based on a heuristic procedure. A greedy local search heuristic based on the problem characteristics is hybridized with a BHGA that has the ability of steering efficiently the search toward the optimal or near-optimal schedules. The performance of proposed GAs is compared with a simulated annealing (SA) approach proposed by Melouk et al. (Melouk, S., Damodaran, P. and Chang, P.Y., Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing. Int. J. Prod. Econ., 2004, 87, 141–147) and also against a modified lower bound proposed for the problem. Computational results show that BHGA performs considerably well compared with the modified lower bound and significantly outperforms the SGA and SA in terms of both quality of solutions and required runtimes.     

基于退火算法的物流配送网的求优研究

模拟退火算法是一种启发式算法,是受到加热紧缩的退火过程所启发而提出来一种求解组合优化问题的一种逼近算法。算法要优于传统的贪婪算法,避免了陷入局部最优的可能,从而达到全局最优解。在物流配送网络中经常为有一些寻求最短路径等问题出现,为了能够达到最短、最优、最经济等,需要进行物流配送路径寻优。文中采用模拟退火算法进行一个示例的验证,效果证明可行。     

基于遗传模拟退火算法的空袭兵力分配及优化

对遗传模拟退火算法中的交叉、变异操作进行了改进，并实施了最优保留策略，形成了改进遗传模拟退火算法．以突击效果最大化和兵力损失最小化为目标函数，以空袭兵力总量的限制、空袭兵器挂载类型的限制等为约束条件，建立了空袭兵力分配及优化模型．在考虑兵力分配模型特点的基础上，利用改进遗传模拟退火算法求解．通过与多目标数学规划和标准遗传算法优化进行的比较表明，该方法能够有效地解决带约束的多目标优化问题．     

Some results characterizing the finite time behaviour of the simulated annealing algorithm

TheSimulated Annealing algorithm is a probabilistic search technique for finding the minimum cost state in a set Ω. The algorithm has been successfully used to obtain near-optimal solutions for problems for which no other effective algorithms exist. For example, problems in integrated circuit layout and in finite impulse response (FIR) filter design have been solved using annealing. In most applications, Ω is finite set, and the annealing algorithm may be modelled as a time-inhomogeneous Markov chain on Ω with transition probabilities that are powers of a time varying parameter ε. It has been shown by several researchers that if ε is driven to 0 sufficiently slowly, then the algorithm will eventually find a minimum cost state in Ω with probability 1. In this paper, we will focus on the finite-time behaviour of the annealing algorithm. In particular, we will summarize some results relating the number of steps taken by the algorithm to the quality of the solutions obtained. These results provide qualitative as well as quantitative information about the status of the annealing algorithm after a finite number of steps. This will be illustrated using some examples.     

Sequencing of parts on single-stage multifunctional machining systems using a chaos-embedded simulated annealing algorithm

This paper deals with the objective of determining an optimal part sequence on a single-stage multifunctional machining system (SSMS) with a view to achieve the broad objectives of cost minimization and time minimization. SSMS has become a preferred alternative for manufacturers to use the resource efficiently, owing to the flexibility and process variety offered by it. This paper formulates a mathematical model that considers the minimization of both set-up cost and time simultaneously. The option of hiring an additional fixture has also been considered that enables the reduction in tool magazine replenishment and re-fixturing operations, which in turn offers economic advantage by way of reducing set-up cost. This study has proposed a new heuristic by modifying the simulated annealing concept to solve the underlying problem. The conventional simulated annealing search scheme is replaced by a chaotic search that takes into account the ergodic and stochastic properties of chaotic systems. In order to restrict the premature convergence and to diversify the search space, a modified perturbation scheme has been employed. The performance of the proposed algorithm was tested on a simulated case study adopted from the literature and the results obtained reveal the effectiveness and scalability of the proposed algorithm. The results establish that the proposed approach is effective and reactive to severe disturbances and must take place in the manufacturing environment.     

模拟退火优化BP神经网络在航向控制系统中的应用

目前，广泛运用于神经网络中的误差反向传播算法（BP算法）训练时间较长，且易陷入局部最优．为了克服BP算法的固有缺陷，文中提出了在BP算法中加入模拟退火算法权因子．在航向控制系统中进行了仿真，数据显示该算法比单纯BP算法更能优化控制器性能参数和全局搜索能力，收敛速度更快，精度提高比较明显。     

基于退火遗传算法的四阶带通箱设计

四阶带通式扬声器系统对扬声器单元参数和箱体参数的配合要求较高，设计复杂。文章中将模拟退火算法和遗传算法相结合，提出了运用具有全局搜索能力的模拟退火遗传算法(SAGA)来设计四阶带通扬声器系统的方法，该算法避免了单一遗传算法存在的早熟收敛和搜索效率较低等问题，提高了算法的收敛速度。文章中考虑了声导管泄漏损耗的影响，并提出了泄漏损耗的QL值的实际测定方法。测量结果表明理论曲线与实测曲线相吻合，说明模拟退火遗传算法能达到设计要求。     

Global optimization analysis of slope stability by simulated annealing with dynamic bounds and Dirac function

In slope stability analysis, the search for the minimum factor of safety is a difficult NP-hard global minimization problem as the objective function is non-smooth and non-convex and there are multiple local minima. The use of a simulated annealing method where the control variables are controlled within dynamic domains instead of the conventional static domains is proposed. A simple transformation technique for slopes with a soft band domain (equivalent to a Dirac function) is also proposed. With these improvements, the minimum factor of safety for complicated problems can be determined with high accuracy and reasonable computer time. The proposed algorithm is demonstrated to be efficient and effective for various difficult problems.     

Optimization of cardinality constrained portfolios with a hybrid local search algorithm

One of the main advantages of portfolios over single assets is that risk can be diversified without necessarily reducing the expected return - provided "proper" assets are selected and they are assigned the "proper" weights. Since in practice investors tend to restrict themselves to a rather small number of different assets, the decision which securities to include is a crucial one that turns out to be NP-hard. In this paper we suggest a hybrid local search algorithm which combines principles of Simulated Annealing and evolutionary strategies and which proved to highly efficiently approach this problem. Correspondence to: Dietmar MaringerThe authors would like to thank participants of the 4^th Metaheuristics International Conference and the Econometrics Research Seminar at the University of Geneva, U. Derigs, M. Gilli, H.-O. Günther, and two anonymous referees for valuable comments on earlier versions of this paper.     

Comparison of the Luus–Jaakola optimization procedure and the genetic algorithm

The success of both genetic algorithms (GA) and the Luus–Jaakola (LJ) optimization procedure in engineering optimization and the desire for efficient optimization methods arising from practical experience make the comparison of these two methods necessary. The GA and the LJ optimization procedure are compared in terms of convergence speed and reliability in obtaining the global optimum. Instead of using the number of function evaluations, this study uses computation time for comparison of convergence speed, which is more precise. Although for some problems, such as parameter estimation for the catalytic cracking process of gas oil, both GA and LJ converge to the optimum rapidly and show high reliability; in most cases, the LJ optimization procedure was found to be faster than GA and exhibited higher reliability in obtaining the global optimum. Furthermore, the LJ optimization procedure is easier to program.     

Hybridizing a genetic algorithm with an artificial immune system for global optimization

This paper proposes an algorithm based on a model of the immune system to handle constraints of all types (linear, nonlinear, equality, and inequality) in a genetic algorithm used for global optimization. The approach is implemented both in serial and parallel forms, and it is validated using several test functions taken from the specialized literature. Our results indicate that the proposed approach is highly competitive with respect to penalty-based techniques and with respect to other constraint-handling techniques which are considerably more complex to implement.     

A constructive algorithm and a simulated annealing approach for solving flowshop problems with missing operations

In many practical cases of flowshop environments and especially in flowline manufacturing cells, some or all jobs may not require processing on all machines. Hence, this paper focuses on the flowshop scheduling problem with missing operations. A modification of the constructive NPS-set heuristic is proposed, which generates non-permutation schedules effectively. Furthermore, a two-phase simulated annealing (SA) method is presented that specifically considers missing operations in its procedure. The modified NPS-set heuristic and the two-phase SA are tested and statistically evaluated by an extensive computational study for total flow time criteria. The results show that the modified NPS-set heuristic as well as the specific consideration of missing operations can enhance the algorithms’ performance significantly.     

基于遗传算法的飞机复合材料结构装配压紧力大小与布局的优化基于遗传算法的飞机复合材料结构装配压紧力大小与布局的优化

针对飞机复合材料结构装配时出现间隙的问题,考虑用压紧力消除间隙可能引起层合板产生损伤,提出了基于遗传算法的压紧力大小和布局的优化算法。结合有限元分析方法,考虑压紧机构之间的干涉问题,以复合材料分层损伤为约束条件,以间隙消除率为优化目标,建立了压紧力大小和布局的优化模型。以复合材料翼盒为例,建立基于内聚力单元的有限元模型,使用上述方法优化复合材料壁板上的压紧力大小和布局。将优化后得到的压紧力方案在有限元模型上进行验算,计算间隙消除率并分析应力应变状态和分层损伤情况。结果表明,优化后的方案能够在不使壁板产生分层损伤的前提下提高间隙消除率,并且能够使壁板的应力和应变分布趋于均匀。当装配间隙的初始值为0.2~0.8 mm时,优化后的方案使间隙消除率提高至77.4%~100%,比优化前的方案提高了19.2%~177.8%。      

Applying tabu search and simulated annealing to the optimal design of sewer networks

Optimizations of sewer network designs create complicated and highly nonlinear problems wherein conventional optimization techniques often get easily bogged down in local optima and cannot successfully address such problems. In the past decades, heuristic algorithms possessing robust and efficient global search capabilities have helped to solve continuous and discrete optimization problems and have demonstrated considerable promise. This study applied tabu search (TS) and simulated annealing (SA) to the optimization of sewer network designs. For a case study, this article used the sewer network design of a central Taiwan township, which contains significantly varied elevations, and the optimal designs from TS and SA were compared with the original official design. The results show that, in contrast with the original design's failure to satisfy the minimum flow-velocity requirements, both TS and SA achieved least-cost solutions that also fulfilled all the constraints of the design criteria. According to the average performance of 200 trials, SA outperformed TS in both robustness and efficiency for solving sewer network optimization problems.