A heuristic algorithm for master production scheduling problem with controllable processing times and scenario-based demands

Master production scheduling (MPS) is widely used by manufacturing industries in order to handle the production scheduling decisions in the production planning hierarchy. The classical approach to MPS assumes infinite capacity, fixed (i.e. non-controllable) processing times and a single pre-determined scenario for the demand forecasts. However, the deterministic optimisation approaches are sometimes not suitable for addressing the real-world problems with high uncertainty and flexibility. Accordingly, in this paper, we propose a new practical model for designing an optimal MPS for the environments in which processing times may be controllable by allocating resources such as facilities, energy or manpower. Due to the NP-hardness of our model, an efficient heuristic algorithm using local search technique and theory of constraints is developed and analysed. The computational results especially for large-sized test problems show that the average optimality gap of proposed algorithm is four times lower than that of exact solution using GAMS while it consumes also significantly smaller run times. Also, the analysis of computational results confirms that considering the controllable processing times may improve the solution space and help to more efficiently utilise the available resources. According to the model structure and performance of the algorithm, it may be proposed for solving large and complex real-world problems particularly the machining and steel industries.     

An adaptive multi-modal optimization algorithm for simulation-based design of power-electronic circuits

This article introduces a non-gradient optimization algorithm for the simulation-based design of nonlinear power-electronic circuits where multiple local minima may exist. The algorithm steers a simultaneous search for multiple optima by generating a multi-resolution mesh in the search space. It adaptively increases its resolution only in regions where the presence of local optima is likely, thus offering significant savings in the number of (simulation-based) objective-function evaluations. The algorithm's relatively low computational intensity, its independence of local gradient information and its capability to discover multiple local minima simultaneously make it appealing for the optimization of expensive black-box functions. The article shows an implementation of the algorithm in MATLAB^® and links it to the PSCAD^®/EMTDC transient simulation program. Examples of the application of the proposed algorithm for both analytical and simulation-based objective functions are included.     

Phase retrieval from speckle images

In ground-based astronomy, the inverse problem of phase retrieval from speckle images is a means to calibrate static aberrations for correction by active optics. It can also be used to sense turbulent wavefronts. However, the number of local minima drastically increases with the turbulence strength, mainly because of phase wrapping ambiguities. Multifocal phase diversity has been considered to overcome some ambiguities of the phase retrieval problem. We propose an effective algorithm for phase retrieval from a single focused image. Our algorithm makes use of a global optimization strategy and an automatically tuned smoothness prior to overcome local minima and phase degeneracies. We push the limit of D/r(0)=4 achieved by Irwan and Lane [J. Opt. Soc. Am. A.15, 2302 (1998)] up to D/r(0)=11, which is a major improvement owing to the drastic increase in the problem complexity. We estimate the performances of our approach from consistent simulations for different turbulence strengths and noise levels (down to 1500 photons per image). We also investigate the benefit of temporal correlation.     

Enhanced balancing Neumann–Neumann preconditioning in computational fluid and solid mechanics

In this work, we propose an enhanced implementation of balancing Neumann–Neumann (BNN) preconditioning together with a detailed numerical comparison against the balancing domain decomposition by constraints (BDDC) preconditioner. As model problems, we consider the Poisson and linear elasticity problems. On one hand, we propose a novel way to deal with singular matrices and pseudo‐inverses appearing in local solvers. It is based on a kernel identification strategy that allows us to efficiently compute the action of the pseudo‐inverse via local indefinite solvers. We further show how, identifying a minimum set of degrees of freedom to be fixed, an equivalent definite system can be solved instead, even in the elastic case. On the other hand, we propose a simple implementation of the algorithm that reduces the number of Dirichlet solvers to only one per iteration, leading to similar computational cost as additive methods. After these improvements of the BNN preconditioned conjugate gradient algorithm, we compare its performance against that of the BDDC preconditioners on a pair of large‐scale distributed‐memory platforms. The enhanced BNN method is a competitive preconditioner for three‐dimensional Poisson and elasticity problems and outperforms the BDDC method in many cases. Copyright © 2013 John Wiley & Sons, Ltd.     

A surrogate-model based multi-modal optimization algorithm

In this article a new algorithm for optimization of multi-modal, nonlinear, black-box objective functions is introduced. It extends the recently-introduced adaptive multi-modal optimization by incorporating surrogate modelling features similar to response surface methods. The resulting algorithm has reduced computational intensity and is well-suited for optimization of expensive objective functions. It relies on an adaptive, multi-resolution mesh to obtain an initial estimation of the objective function surface. Local surrogate models are then constructed and used to generate additional trial points around the local minima discovered. The steps of mesh refinement and surrogate modelling continue until convergence is achieved. The algorithm produces progressively accurate surrogate models, which can be used for post-optimization studies such as sensitivity and tolerance analyses with minimal computational effort. This article demonstrates the effectiveness of the algorithm using comparative optimization of several multi-modal objective functions, and shows an engineering application of the design of a power electronic converter.     

Cyclic transfers in school timetabling

In this paper we propose a neighbourhood structure based on sequential/cyclic moves and a cyclic transfer algorithm for the high school timetabling problem. This method enables execution of complex moves for improving an existing solution, while dealing with the challenge of exploring the neighbourhood efficiently. An improvement graph is used in which certain negative cycles correspond to the neighbours; these cycles are explored using a recursive method. We address the problem of applying large neighbourhood structure methods on problems where the cost function is not exactly the sum of independent cost functions, as it is in the set partitioning problem. For computational experiments we use four real world data sets for high school timetabling in the Netherlands and England. We present results of the cyclic transfer algorithm with different settings on these data sets. The costs decrease by 8–28% if we use the cyclic transfers for local optimization compared to our initial solutions. The quality of the best initial solutions are comparable to the solutions found in practice by timetablers.     

Mathematical analysis and solution methodology for an inverse spectral problem arising in the design of optical waveguides

We analyse mathematically the problem of determining refractive index profiles from some desired/measured guided waves propagating in optical fibres. We establish the uniqueness of the solution of this inverse spectral problem assuming that only one guided mode is known. We then propose an iterative computational procedure for solving numerically the considered inverse spectral problem. Numerical results are presented to illustrate the potential of the proposed regularized Newton algorithm to efficiently and accurately retrieve the refractive index profiles even when the guided mode measurements are highly noisy.     

Heuristic,storage space minimization methods for facility layouts served by looped AGV systems

An analytical method for predicting work-in-process storage requirements resulting from a fixed number of looping, automated guided vehicles (AGVs) serving a line layout is described. The method is based on a model of storage queue dynamics that predicts material flow rates and vehicle response times resulting from vehicle dispatching within a single loop system. The method is applied in the development of two heuristic, random number driven procedures designed to perform sequential search for WIP storage minimizing line layouts over alternative AGV fleet sizes. The first algorithm is a greedy, ‘CRAFT like’ procedure based on local improvement in storage requirements using random, pairwise exchanges of workcentre locations. The second algorithm is a modification to the greedy procedure using simulated annealing methods designed to avoid trapping at local minima. Limited computational studies using the methods are reported.     

Glass-like energy and property landscape of Pt nanoclusters

Pt nanoclusters play an important role in catalysis-related applications.Essential to their activities are their geometries and energy landscapes.In this work,we studied the energy landscapes of Pt clusters using a parallel differential evolution optimization algorithm and an accelerated ab initio atomic relaxation method,which allowed us to explore unprecedentedly large numbers of geometry local minima at ab initio level.We found many lower-energy isomers with low symmetry in their geometry.The energy landscapes were demonstrated to be glass-like with a large number of local minimum structures close to the global minimum.The electronic and magnetic properties of most glass-like local minima were dramatically different from the global minimum,and they should be observed in the experimental measurements.The connections between these local minima were further analyzed using data mining techniques.     

无人机电子稳像技术中角点检测算法的改进

无人机航空遥感电子稳像系统中,稳像的关键技术之一是影像特征点的选取,其中图像角点是遥感影像中重要的特征信息,准确地选取角点可提高图像处理的精度。然而现有的图像角点检测算法多因计算速度慢不能满足视频图像数字稳像的实时性。因此提出了一种基TSUSAN角点检测算法的改进算法。新算法分析了影像中角点所在区域的灰度变化特征,改进了SUSAN角点检测算法中的判断准则,提高了算法的精度和速度。实验结果表明,改进的算法可较大幅度的提高运算速度,满足稳像技术对视频图像实时处理的要求。     

A batching-move iterated local search algorithm for the bin packing problem with generalized precedence constraints

In this paper, we propose a generalisation of the bin packing problem, obtained by adding precedences between items that can assume heterogeneous non-negative integer values. Such generalisation also models the well-known Simple Assembly Line Balancing Problem of type I. To solve the problem, we propose a simple and effective iterated local search algorithm that integrates in an innovative way of constructive procedures and neighbourhood structures to guide the search to local optimal solutions. Moreover, we apply some preprocessing procedures and adapt classical lower bounds from the literature. Extensive computational experiments on benchmark instances suggest that the developed algorithm is able to generate good quality solutions in a reasonable computational time.     

Decoding the energy landscape: extracting structure, dynamics and thermodynamics

Describing a potential energy surface in terms of local minima and the transition states that connect them provides a conceptual and computational framework for understanding and predicting observable properties. Visualizing the potential energy landscape using disconnectivity graphs supplies a graphical connection between different structure-seeking systems, which can relax efficiently to a particular morphology. Landscapes involving competing morphologies support multiple potential energy funnels, which may exhibit characteristic heat capacity features and relaxation time scales. These connections between the organization of the potential energy landscape and structure, dynamics and thermodynamics are common to all the examples presented, ranging from atomic and molecular clusters to biomolecules and soft and condensed matter. Further connections between motifs in the energy landscape and the interparticle forces can be developed using symmetry considerations and results from catastrophe theory.     

AASMAn: An adaptive organisational policy for a society of market-based agents

Several formalisms for implementing organisational policies that assign specific roles to each of the agents in a multi-agent system (MAS) have been proposed like the contract net protocol, the social reasoning mechanism and the distributed computational economy. However, as no single organisation is appropriate in all situations, organisation self design had been proposed to allow an organisation of problem solvers to adapt itself to a dynamically changing environment. In this paper we propose an adaptive organisational framework that exploits and integrates the essential features of these existing organisational policies not only to meet the needs of time constrained noncritical applications, where computational load on the organisation cannot be predicted ahead of time, but also to utilise the available system resources efficiently. We also introduce the notion of decommitments and penalties in this approach which was not present in the original contract net protocol.     

AASMAn: An adaptive organisational policy for a society of market-based agents

Several formalisms for implementing organisational policies that assign specific roles to each of the agents in a multi-agent system (MAS) have been proposed like the contract net protocol, the social reasoning mechanism and the distributed computational economy. However, as no single organisation is appropriate in all situations, organisation self design had been proposed to allow an organisation of problem solvers to adapt itself to a dynamically changing environment. In this paper we propose an adaptive organisational framework that exploits and integrates the essential features of these existing organisational policies not only to meet the needs of time constrained noncritical applications, where computational load on the organisation cannot be predicted ahead of time, but also to utilise the available system resources efficiently. We also introduce the notion of decommitments and penalties in this approach which was not present in the original contract net protocol.     

A general framework for scheduling equipment and manpower at container terminals

In this paper, we propose a general model for various scheduling problems that occur in container terminal logistics. The scheduling model consists of the assignment of jobs to resources and the temporal arrangement of the jobs subject to precedence constraints and sequence-dependent setup times. We demonstrate how the model can be applied to solve several different real-world problems from container terminals in the port of Hamburg (Germany). We consider scheduling problems for straddle carriers, automated guided vehicles (AGVs), stacking cranes, and workers who handle reefer containers. Subsequently, we discuss priority rule based heuristics as well as a genetic algorithm for the general model. Based on a tailored generator for experimental data, we examine the performance of the heuristics in a computational study. We obtain promising results that suggest that the genetic algorithm is well suited for application in practice.     

A two-dimensional bin-packing problem with conflict penalties

In this paper, we address the two-dimensional bin-packing (2BP) problem with variable conflict penalties, which incur if conflicting items are loaded into the same bin. Such a problem is observed in applications such as supermarket chains and automobile components transportation. The problem not only focuses on minimisation of number of bins used, but also deals with the conflict penalties at the same time. We propose a heuristic method based on the IMA algorithm and adapt it to solve this problem. A local search procedure is also designed to further improve the solutions. For instances derived from benchmark test data, the computational results indicate that the adapted IMA heuristic algorithm with local search effectively balances the number of bins used and the conflict penalties. The algorithm outperforms several adapted approaches that are well known for the 2BP problems.     

Hybrid optimization and Bayesian inference techniques for a non‐smooth radiation detection problem

We propose several algorithms to recover the location and intensity of a radiation source located in a simulated 250 × 180 m block of an urban center based on synthetic measurements. Radioactive decay and detection are Poisson random processes, so we employ likelihood functions based on this distribution. Owing to the domain geometry and the proposed response model, the negative logarithm of the likelihood is only piecewise continuous differentiable, and it has multiple local minima. To address these difficulties, we investigate three hybrid algorithms composed of mixed optimization techniques. For global optimization, we consider simulated annealing, particle swarm, and genetic algorithm, which rely solely on objective function evaluations; that is, they do not evaluate the gradient in the objective function. By employing early stopping criteria for the global optimization methods, a pseudo‐optimum point is obtained. This is subsequently utilized as the initial value by the deterministic implicit filtering method, which is able to find local extrema in non‐smooth functions, to finish the search in a narrow domain. These new hybrid techniques, combining global optimization and implicit filtering address, difficulties associated with the non‐smooth response, and their performances, are shown to significantly decrease the computational time over the global optimization methods. To quantify uncertainties associated with the source location and intensity, we employ the delayed rejection adaptive Metropolis and DiffeRential Evolution Adaptive Metropolis algorithms. Marginal densities of the source properties are obtained, and the means of the chains compare accurately with the estimates produced by the hybrid algorithms. Copyright © 2016 John Wiley & Sons, Ltd.     

Genetic algorithm with local search for the unrelated parallel machine scheduling problem with sequence-dependent set-up times

In this paper, a genetic algorithm (GA) with local search is proposed for the unrelated parallel machine scheduling problem with the objective of minimising the maximum completion time (makespan). We propose a simple chromosome structure consisting of random key numbers in a hybrid genetic-local search algorithm. Random key numbers are frequently used in GAs but create additional difficulties when hybrid factors are implemented in a local search. The best chromosome of each generation is improved using a local search during the algorithm, but the better job sequence (which might appear during the local search operation) must be adapted to the chromosome that will be used in each successive generation. Determining the genes (and the data in the genes) that would be exchanged is the challenge of using random numbers. We have developed an algorithm that satisfies the adaptation of local search results into the GAs with a minimum relocation operation of the genes’ random key numbers – this is the main contribution of the paper. A new hybrid approach is tested on a set of problems taken from the literature, and the computational results validate the effectiveness of the proposed algorithm.     

Skid scheduling algorithm for a shipbuilding company

In the small- and medium-sized shipbuilding companies, the skid system, which is a kind of slips located on flat seashore, is widely used. To improve the productivity of the skid, many shipbuilders adopt the semi-tandem system, under which a number of ships can be built on a skid simultaneously. The focus of the research reported in this paper is to develop an efficient spatial schedule for the skid system that uses the semi-tandem system. First, we develop a length-time, two-dimensional packing model for this problem and propose a heuristic algorithm to use the skid efficiently when the launching schedule for ships is given. Then, by combining this heuristic and the GA (genetic algorithm), we develop a hybrid GA algorithm to determine the launching schedule of ships as well as the spatial schedule for the skid, which maximises the number of ships that can be built on the skid and minimises delayed or early launching of each ship. Through performing a series of computational experiments, we finally show that the proposed algorithm can provide solutions of good quality very efficiently.     

Convergence of the Schulz-Snyder phase retrieval algorithm to local minima

The Schulz-Snyder iterative algorithm for phase retrieval attempts to recover a nonnegative function from its autocorrelation by minimizing the I-divergence between a measured autocorrelation and the autocorrelation of the estimated image. We illustrate that the Schulz-Snyder algorithm can become trapped in a local minimum of the I-divergence surface. To show that the estimates found are indeed local minima, sufficient conditions involving the gradient and the Hessian matrix of the I-divergence are given. Then we build a brief proof showing how an estimate that satisfies these conditions is a local minimum. The conditions are used to perform numerical tests determining local minimality of estimates. Along with the tests, related numerical issues are examined, and some interesting phenomena are discussed.