An estimation of distribution algorithm for hybrid flow shop scheduling under stochastic processing times

The estimation of distribution algorithm (EDA) has recently emerged as a promising alternative to traditional evolutionary algorithms for solving combinatorial optimisation problems. This paper presents a novel two-phase simulation-based EDA (TPSB-EDA) for minimising the makespan of a hybrid flow shop under stochastic processing times. To address the stochastic scheduling problem efficiently, the proposed TPSB-EDA incorporates a two-phase simulation model to estimate the performance of candidate solutions. In this model, an optimal back propagation network is firstly applied to identify a set of roughly good solutions, and then the selected solutions are further evaluated by a discrete-event simulation algorithm. Moreover, an annealing selection mechanism (ASM) is adopted to preserve the population diversity of EDA. Different from the selection operators of common EDAs, the ASM uses Boltzmann probability in the annealing algorithm to select part of population to establish the probabilistic model. Computation results indicate that the TPSB-EDA provides good solutions in the aspects of solution quality and computational efficiency.     

Particle-swarm harmony search for water network design

The optimal design of water distribution networks is a non-linear, multi-modal, and constrained problem classified as an NP-hard combinatorial problem. Because of the drawbacks of calculus-based algorithms, the problem has been tackled by assorted stochastic algorithms, such as the genetic algorithm, simulated annealing, tabu search, shuffled frog-leaping algorithm, ant colony optimization algorithm, harmony search, cross entropy, and scatter search. This study proposes a modified harmony search algorithm incorporating particle swarm concept. This algorithm was applied to the design of four bench-mark networks (two-loop, Hanoi, Balerma, and New York City networks), with good results.     

Task assignment problems in distributed computing systems by simulated annealing

Abstract

The stochastic, heuristic search algorithm called simulated annealing is considered for the problems of static task assignment in distributed computing systems. The purposes of task assignment problems are to assign modules of programs over a set of interconnected processors in order to both maximize the utilization of processors and minimize interprocessor communication costs. This problem has been proven to be NP‐hard. Although simulated annealing has been applied to a broad class of combinatorial optimization problems, but it requires a long computation time in order to converge to the globally optimal solution. In this paper, we design a very efficient annealing schedule with good move generation strategies and use the concept of specific heat and the frozen condition to obtain near‐optimal solutions for task assignment problems with a significantly large reduction in the number of iterations.     

A new simulated annealing algorithm for the facility layout problem

In this paper we present an application of simulated annealing to facility layout problems with single and multiple floors. The facility layout problem is highly combinatorial in nature and generally exhibits many local minima. These properties make it a suitable candidate for simulated annealing. Using a new candidate layout generation routine and spacefilling curves, we develop an improvement-type layout algorithm based on simulated annealing that considers an expanded set of department exchanges. The resulting algorithm achieves low-cost solutions that are much less dependent on the initial layout than other approaches. We compare the performance of the simulated-annealing based algorithm with both steepest-descent and randomized approaches from the literature. Unlike other simulated annealing papers which typically present a statistical experiment to evaluate the effect of numerous control settings, all the experiments presented in this paper were conducted with control settings that are constant or easily specified. This approach facilitates the application of the proposed algorithm to real-life facility layout problems in both single and multiple floor facilities. Although the algorithm presented here can be applied to many types of facilities, our primary focus is on production facilities.     

基于离散差分进化算法的随机车辆路径问题

针对差分进化算法求解组合优化问题存在的局限性,引入计算机语言中的2种按位运算符,对差分进化算法的变异算子进行重新设计,用来求解不确定需求和旅行时间下同时取货和送货的随机车辆路径问题（SVRPSPD）。通过对车辆路径问题的benchmark问题和SVRPSPD问题进行路径优化,并同差分进化算法和遗传算法的计算结果进行比较,验证了离散差分进化算法的性能。结果表明,离散差分进化算法在解决复杂的SVRPSPD问题时,具有较好的优化性能,不仅能得到更好的优化结果,而且具有更快的收敛速度。     

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

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

OPTIMAL STRUCTURAL DESIGN BY ANT COLONY OPTIMIZATION

Ant colony optimization (ACO) is a relatively new heuristic combinatorial optimization algorithm in which the search process is a stochastic procedure that incorporates positive feedback of accumulated information. The positive feedback (;i.e., autocatalysis) facility is a feature of ACO which gives an emergent search procedure such that the (common) problem of algorithm termination at local optima may be avoided and search for a global optimum is possible.

The ACO algorithm is motivated by analogy with natural phenomena, in particular, the ability of a colony of ants to ‘optimize’ their collective endeavours. In this paper the biological background for ACO is explained and its computational implementation is presented in a structural design context. The particular implementation of ACO makes use of a tabu search (TS) local improvement phase to give a computationally enhanced algorithm (ACOTS).

In this paper ACOTS is applied to the optimal structural design, in terms of weight minimization, of a 25-bar space truss. The design variables are the cross-sectional areas of the bars, which take discrete values. Numerical investigation of the 25-bar space truss gave the best (i.e., lowest to-date) minimum weight value. This example provides evidence that ACOTS is a useful and technically viable optimization technique for discrete-variable optimal structural design.     

Cell formation in group technology: A combinatorial search approach

This paper addresses the cell formation problem in group technology (GT). We develop two heuristic methods for generating solutions to the problem. These methods are based on two powerful combinatorial search methods simulated annealing and tabu search. The performance of the heuristics is examined using randomly generated, published and industry data. The results indicate that the simulated annealing based heuristic is the preferred technique in the context of the problem addressed in this paper. Further, we also demonstrate that the simulated annealing based heuristic generates near-optimal solutions to the cell formation model formulated in this paper.     

基于整体退火遗传算法的膜系设计方法

提出了以遗传算法和模拟退火算法相结合的整体退火遗传算法（ＧＡＳＡ）进行膜系设计的新方法。整体退火遗传算法具有全局寻优能力,与作为现代光学薄膜自动设计的主要方法－针法相比,在相同薄膜层数情况下用该方法设计可以得到较优的结果,或者用更少的薄膜层数达到同样的设计结果。并且对初始条件不敏感,可以确定膜层厚度边界,以确保制备方便。理论与实例表明该方法是高效的和可靠的。     

Scheduling a flow-line manufacturing cell: a tabu search approach

The performance of two heuristic procedures for the scheduling of a flow-line manufacturing cell was compared. We propose a procedure based on a combinatorial search technique known as tabu search. The new procedure is compared with a heuristic based on simulated annealing which was proposed in earlier research. The scheduling problem addressed here differs from the traditional flow-shop scheduling problem in the sense that we are interested in sequencing part families (i.e. groups of jobs which share a similar setup) as well as individual jobs within each family. The results reveal that the tabu search heuristic outperforms the simulated annealing heuristic by generating 'better solutions' in less computation time.     

Deterministic and stochastic approach for safety and reliability optimization of captive power plant maintenance scheduling using GA/SA-based hybrid techniques: A comparison of results

This paper presents a comparison of results for optimization of captive power plant maintenance scheduling using genetic algorithm (GA) as well as hybrid GA/simulated annealing (SA) techniques. As utilities catered by captive power plants are very sensitive to power failure, therefore both deterministic and stochastic reliability objective functions have been considered to incorporate statutory safety regulations for maintenance of boilers, turbines and generators. The significant contribution of this paper is to incorporate stochastic feature of generating units and that of load using levelized risk method. Another significant contribution of this paper is to evaluate confidence interval for loss of load probability (LOLP) because some variations from optimum schedule are anticipated while executing maintenance schedules due to different real-life unforeseen exigencies. Such exigencies are incorporated in terms of near-optimum schedules obtained from hybrid GA/SA technique during the final stages of convergence. Case studies corroborate that same optimum schedules are obtained using GA and hybrid GA/SA for respective deterministic and stochastic formulations. The comparison of results in terms of interval of confidence for LOLP indicates that levelized risk method adequately incorporates the stochastic nature of power system as compared with levelized reserve method. Also the interval of confidence for LOLP denotes the possible risk in a quantified manner and it is of immense use from perspective of captive power plants intended for quality power.     

供应链中随机需求车辆选径问题的研究

结合供应链的需要给出了允许两次服务失败的数学模型,提出了一种混沌神经网络求解算法,对该问题进行了求解,并与SA算法进行了比较.结果表明该算法具有很强的避免陷入局部极小点的能力,较大地提高了优化的性能和搜索效率,适用于求解车辆选径问题.     

JIT mixed-model sequencing with batching and setup considerations via search heuristics

This research addresses the problem of sequencing items for production when it is desired that the production sequences result in minimal usage rates–surrogate measures for flexibility in a JIT environment. While seeking sequences with minimal usage rates, the number of required setups for the sequences is also considered, along with feasible batch-sizing combinations. The general intent is to find minimum usage-rate sequences for each associated number of setups and total batches. This multiple objective problem is addressed via a three-dimensional efficient frontier. Because the combinatorial nature of sequencing problems typically provides an intractable search space for problems of ‘real world’ size, the search heuristics of simulated annealing and genetic algorithms are presented and used to find solutions for several problem sets from the literature. Experimentation shows that the simulated annealing approach outperforms the genetic algorithm approach in both objective function and CPU performance.     

Statistical reconstruction and Karhunen–Loève expansion for multiphase random media

Termed as random media, rocks, composites, alloys and many other heterogeneous materials consist of multiple material phases that are randomly distributed through the medium. This paper presents a robust and efficient algorithm for reconstructing random media, which can then be fed into stochastic finite element solvers for statistical response analysis. The new method is based on nonlinear transformation of Gaussian random fields, and the reconstructed media can meet the discrete‐valued marginal probability distribution function and the two‐point correlation function of the reference medium. The new method, which avoids iterative root‐finding computation, is highly efficient and particularly suitable for reconstructing large‐size random media or a large number of samples. Also, benefiting from the high efficiency of the proposed reconstruction scheme, a Karhunen–Loève (KL) representation of the target random medium can be efficiently estimated by projecting the reconstructed samples onto the KL basis. The resulting uncorrelated KL coefficients can be further expressed as functions of independent Gaussian random variables to obtain an approximate Gaussian representation, which is often required in stochastic finite element analysis. Copyright © 2015 John Wiley & Sons, Ltd.     

An a Priori Bounded Model for Transportation Problems with Stochastic Demand and Integer Solutions

A linear approximation model is developed for transportation problems with stochastic demand where integer solutions are required. The technique reduces the stochastic integer programming problem to a deterministic linear approximating problem which can be solved as a capacitated transportation problem. Either the transportation algorithm or the primal-dual algorithm may be used thereby insuring integer solutions.     

Using queuing theory and simulated annealing to design the facility layout in an AGV-based modular manufacturing system

An automated guided vehicle-based flow production system is used for manufacturing prefabricated bathroom units. One unit can occupy a space of more than 10?m². Due to large time deviations in sequential processes, queues are formed and greater plant space is needed. Reducing work-in-progress helps to save plant space but renders manufacture less efficient. The research explores better workstation arrangements. An open queuing network (OQN) model was used to approximate the flow production system. Since the problem of workstation arrangement is a combinatorial optimisation problem, simulated annealing (SA) was applied to search for a good solution. The combination of an OQN model and SA provides a powerful tool to solve the facility layout problem for a stochastic flow production system. The experimental results show that the proposed approach has the potential to guide industrial layout design and practice.     

Monte Carlo algorithm for least dependent non-negative mixture decomposition

We propose a simulated annealing algorithm (stochastic non-negative independent component analysis, SNICA) for blind decomposition of linear mixtures of non-negative sources with non-negative coefficients. The demixing is based on a Metropolis-type Monte Carlo search for least dependent components, with the mutual information between recovered components as a cost function and their non-negativity as a hard constraint. Elementary moves are shears in two-dimensional subspaces and rotations in three-dimensional subspaces. The algorithm is geared at decomposing signals whose probability densities peak at zero, the case typical in analytical spectroscopy and multivariate curve resolution. The decomposition performance on large samples of synthetic mixtures and experimental data is much better than that of traditional blind source separation methods based on principal component analysis (MILCA, FastICA, RADICAL) and chemometrics techniques (SIMPLISMA, ALS, BTEM).     

Efficient anticorrelated variance reduction for stochastic simulation of biochemical reactions

We investigate the computational challenge of improving the accuracy of the stochastic simulation estimation by inducing negative correlation through the anticorrelated variance reduction technique. A direct application of the technique to the stochastic simulation algorithm (SSA), employing the inverse transformation, is not efficient for simulating large networks because its computational cost is similar to the sum of independent simulation runs. We propose in this study a new algorithm that employs the propensity bounds of reactions, introduced recently in their rejection‐based SSA, to correlate and synchronise the trajectories during the simulation. The selection of reaction firings by our approach is exact due to the rejection‐based mechanism. In addition, by applying the anticorrelated variance technique to select reaction firings, our approach can induce substantial correlation between realisations, hence reducing the variance of the estimator. The computational advantage of our rejection‐based approach in comparison with the traditional inverse transformation is that it only needs to maintain a single data structure storing propensity bounds of reactions, which is updated infrequently, hence achieving better performance.Inspec keywords: biochemistry, data structures, biology computing, inverse transforms, stochastic processes, large‐scale systemsOther keywords: stochastic simulation estimation, anticorrelated variance reduction technique, stochastic simulation algorithm, computational cost, independent simulation runs, rejection‐based SSA, reaction firings, rejection‐based mechanism, anticorrelated variance technique, substantial correlation, estimator, rejection‐based approach, single data structure storing propensity, biochemical reactions, anticorrelated variance reduction     

Optimizing financial and physical assets with?chance-constrained programming in?the?electrical?industry

This paper deals with a Chance-Constrained Programming formulation and approximate resolution of an offer-demand equilibrium problem in the context of electricity markets. First, we state the probabilistic model. Computing the coefficients of the problem matrix is easy for financial assets, but a challenging task for physical assets. By introducing maximal production capacities, the computation becomes tractable for thermal plants but still leads to a combinatorial problem for hydraulic production. The obtained problem matrix is sparse, large scale and with random coefficients describing underlying uncertainty factors affecting the available power of assets. Second, we suggest some ways for approximately solving the obtained combinatorial chance-constrained program, which is in fact a stochastic multi-knapsack problem. A formal link between joint and individual chance constraints is exhibited and may lead to a simplified processing of the problem. Finally we illustrate our approximate algorithm on a stylized example.     

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.