Local search and genetic algorithm for the job shop scheduling problem with sequence dependent setup times

The Job Shop Scheduling Problem (JSP) is an example of a combinatorial optimization problem that has interested researchers for several decades. In this paper we confront an extension of this problem called JSP with Sequence Dependent Setup Times (SDST-JSP). The approach extends a genetic algorithm and a local search method that demonstrated to be efficient in solving the JSP. For local search, we have formalized neighborhood structures that generalize three well-know structures defined for the JSP. We have conducted an experimental study across conventional benchmark instances showing that the genetic algorithm exploited in combination with the local search, considering all three neighborhoods at the same time, provides the best results. Moreover, this approach outperforms the current state-of-the-art methods.     

Metaheuristics can solve sudoku puzzles

In this paper we present, to our knowledge, the first application of a metaheuristic technique to the very popular and NP-complete puzzle known as ‘sudoku’. We see that this stochastic search-based algorithm, which uses simulated annealing, is able to complete logic-solvable puzzle-instances that feature daily in many of the UK’s national newspapers. We also introduce a new method for producing sudoku problem instances (that are not necessarily logic-solvable) and use this together with the proposed SA algorithm to try and discover for what types of instances this algorithm is best suited. Consequently we notice the presence of an ‘easy-hard-easy’ style phase-transition similar to other problems encountered in operational research.     

A morph-based simulated annealing heuristic for a modified bin-packing problem

This paper presents a local-search heuristic, based on the simulated annealing (SA) algorithm for a modified bin-packing problem (MBPP). The objective of the MBPP is to assign items of various sizes to a fixed number of bins, such that the sum-of-squared deviation (across all bins) from the target bin workload is minimized. This problem has a number of practical applications which include the assignment of computer jobs to processors, the assignment of projects to work teams, and infinite-loading machine scheduling problems. The SA-based heuristic we developed uses a morph-based search procedure when looking for better allocations. In a large computational study we evaluated 12 versions of this new heuristic, as well as two versions of a previously published SA-based heuristic that used a completely random search. The primary performance measure for this evaluation was the mean percent above the best known objective value (MPABKOV). Since the MPABKOV associated with the best version of the random-search SA heuristic was more than 290 times larger than that of the best version of the morph-based SA heuristic, we conclude that the morphing process is a significant enhancement to SA algorithms for these problems.     

Simulated annealing for discrete optimization with estimation

We extend the basic convergence results for the Simulated Annealing (SA) algorithm to a stochastic optimization problem where the objective function is stochastic and can be evaluated only through Monte Carlo simulation (hence, disturbed with random error). This extension is important when either the objective function cannot be evaluated exactly or such an evaluation is computationally expensive. We present a modified SA algorithm and show that under suitable conditions on the random error, the modified SA algorithm converges in probability to a global optimizer. Computational results and comparisons with other approaches are given to demonstrate the performance of the proposed modified SA algorithm.     

Approximated algorithms for the minimum dilation triangulation problem

The complexity status of the minimum dilation triangulation (MDT) problem for a general point set is unknown. Therefore, we focus on the development of approximated algorithms to find high quality triangulations of minimum dilation. For an initial approach, we design a greedy strategy able to obtain approximate solutions to the optimal ones in a simple way. We also propose an operator to generate the neighborhood which is used in different algorithms: Local Search, Iterated Local Search, and Simulated Annealing. Besides, we present an algorithm called Random Local Search where good and bad solutions are accepted using the previous mentioned operator. For the experimental study we have created a set of problem instances since no reference to benchmarks for these problems were found in the literature. We use the sequential parameter optimization toolbox for tuning the parameters of the SA algorithm. We compare our results with those obtained by the OV-MDT algorithm that uses the obstacle value to sort the edges in the constructive process. This is the only available algorithm found in the literature. Through the experimental evaluation and statistical analysis, we assess the performance of the proposed algorithms using this operator.     

SPT optimality (mostly) via linear programming

One of the oldest results in scheduling theory is that the Shortest Processing Time (SPT) rule finds an optimal solution to the problem of scheduling jobs on identical parallel machines to minimize average job completion times. We present a new proof of correctness of SPT based on linear programming (LP). Our proof relies on a generalization of a single-machine result that yields an equivalence between two scheduling problems. We first identify and solve an appropriate variant of our problem, then map its solutions to solutions for our original problem to establish SPT optimality. Geometric insights used therein may find further uses; we demonstrate two applications of the same principle in generalized settings.     

Hybrid parallel tempering and simulated annealing method

In this paper, we propose a new hybrid scheme of parallel tempering and simulated annealing (hybrid PT/SA). Within the hybrid PT/SA scheme, a composite system with multiple conformations is evolving in parallel on a temperature ladder with various transition step sizes. The simulated annealing (SA) process uses a cooling scheme to decrease the temperature values in the temperature ladder to the target temperature. The parallel tempering (PT) scheme is employed to reduce the equilibration relaxation time of the composite system at a particular temperature ladder configuration in the SA process. The hybrid PT/SA method reduces the waiting time in deep local minima and thus leads to a more efficient sampling capability on high-dimensional complicated objective function landscapes. Compared to the approaches PT and parallel SA with the same temperature ladder, transition step sizes, and cooling scheme (parallel SA) configurations, our preliminary results obtained with the hybrid PT/SA method confirm the expected improvements in simulations of several test objective functions, including the Rosenbrock’s function and the “rugged” funnel-like function, and several instantiations of the traveling salesman problem. The hybrid PT/SA may have slower convergence than genetic algorithms (GA) with good crossover heuristics, but it has the advantage of tolerating “bad” initial values and displaying robust sampling capability, even in the absence of additional information. Moreover, the hybrid PT/SA has natural parallelization potential.     

Solving the robust two-stage capacitated facility location problem with uncertain transportation costs

In this study, we start from a multi-source variant of the two-stage capacitated facility location problem (TSCFLP) and propose a robust optimization model of the problem that involves the uncertainty of transportation costs. Since large dimensions of the robust TSCFLP could not be solved to optimality, we design a memetic algorithm (MA), which represents a combination of an evolutionary algorithm (EA) and a modified simulated annealing heuristic (SA) that uses a short-term memory of undesirable moves from previous iterations. A set of computational experiments is conducted to examine the impact of different protection levels on the deviation of the objective function value. We also investigate the impact of variations of transportation costs that may occur on both transhipment stages on the total cost for a fixed protection level. The obtained results may help in identifying a sustainable and efficient strategy for designing a two stage capacitated transportation network with uncertain transportation costs, and may be applicable in the design and management of similar transportation networks.     

Linear interpolation for image conversion between square structure and hexagonal structure

Spiral Architecture (SA) is a relatively new and powerful image structure consisting of hexagonal pixels arranged in a onedimensional coordinate system. However, all the existing hardware for capturing image and for displaying image are produced based on traditional square image structure. In this paper, we present a software approach to represent an image on SA based on linear interpolation method. We perform edge detection on SA to demonstrate the advantages of image processing on SA. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Spectral analytic comparisons for data augmentation

The sandwich algorithm (SA) is an alternative to the data augmentation (DA) algorithm that uses an extra simulation step at each iteration. In this paper, we show that the sandwich algorithm always converges at least as fast as the DA algorithm, in the Markov operator norm sense. We also establish conditions under which the spectrum of SA dominates that of DA. An example illustrates the results.     

Constraint Propagation and Problem Decomposition: A Preprocessing Procedure for the Job Shop Problem

In recent years, constraint propagation techniques have been shown to be highly effective for solving difficult scheduling problems. In this paper, we present an algorithm which combines constraint propagation with a problem decomposition approach in order to simplify the solution of the job shop scheduling problem. This is mainly guided by the observation that constraint propagation is more effective for small problem instances. Roughly speaking, the algorithm consists of deducing operation sequences that are likely to occur in an optimal solution of the job shop scheduling problem (JSP).The algorithm for which the name edge-guessing procedure has been chosen – since with respect to the job shop scheduling problem (JSP) the deduction of machine sequences is mainly equivalent to orienting edges in a disjunctive graph – can be applied in a preprocessing step, reducing the solution space, thus speeding up the overall solution process. In spite of the heuristic nature of edge-guessing, it still leads to near-optimal solutions. If combined with a heuristic algorithm, we will demonstrate that given the same amount of computation time, the additional application of edge-guessing leads to better solutions. This has been tested on a set of well-known JSP benchmark problem instances.     

Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem

The unconstrained binary quadratic programming problem (BQP) is known to be NP-hard and has many practical applications. This paper presents a simulated annealing (SA)-based heuristic for the BQP. The new SA heuristic for the BQP is based on a simple (1-opt) local search heuristic and designed with a simple cooling schedule, but the multiple annealing processes are adopted. To show practical performances of the SA, we test on publicly available benchmark instances of large size ranging from 500 to 2500 variables and compare them with other heuristics such as multi-start local search, the previous SA, tabu search, and genetic algorithm incorporating the 1-opt local search. Computational results indicate that our SA leads to high-quality solutions with short times and is more effective than the competitors particularly for the largest benchmark set. Furthermore, the values of new best-known solutions found by the SA for several large instances are also reported.     

Simulated annealing for the unconstrained quadratic pseudo-Boolean function

In this paper, we develop a simulated annealing (SA) based heuristic for the unconstrained quadratic pseudo-Boolean function. An algorithm that solves the problem in O(n²) at each temperature of the cooling schedule is given. The performance of SA based heuristic is compared with existing bounding algorithms for this problem. Computational results and comparisons on several hundred test problems demonstrate the efficiency of our heuristic in terms of solution quality and computational time. A new set of hard test problems with their best solution is provided to facilitate future comparison.     

An enumeration procedure for the assembly line balancing problem based on branching by non-decreasing idle time

In this article, we present a new exact algorithm for solving the simple assembly line balancing problem given a determined cycle time (SALBP-1). The algorithm is a station-oriented bidirectional branch-and-bound procedure based on a new enumeration strategy that explores the feasible solutions tree in a non-decreasing idle time order. The procedure uses several well-known lower bounds, dominance rules and a new logical test based on the assimilation of the feasibility problem for a given cycle time and number of stations (SALBP-F) to a maximum-flow problem.     

A new discrete particle swarm optimization approach for the single-machine total weighted tardiness scheduling problem with sequence-dependent setup times

In this paper we present a new Discrete Particle Swarm Optimization (DPSO) approach to face the NP-hard single machine total weighted tardiness scheduling problem in presence of sequence-dependent setup times. Differently from previous approaches the proposed DPSO uses a discrete model both for particle position and velocity and a coherent sequence metric. We tested the proposed DPSO mainly over a benchmark originally proposed by Cicirello in 2003 and available online. The results obtained show the competitiveness of our DPSO, which is able to outperform the best known results for the benchmark. In addition, we also tested the DPSO on a set of benchmark instances from ORLIB for the single machine total weighted tardiness problem, and we analysed the role of the DPSO swarm intelligence mechanisms as well as the local search intensification phase included in the algorithm.     

Numerical methods for stochastic programs with second order dominance constraints with applications to portfolio optimization

Inspired by the successful applications of the stochastic optimization with second order stochastic dominance (SSD) model in portfolio optimization, we study new numerical methods for a general SSD model where the underlying functions are not necessarily linear. Specifically, we penalize the SSD constraints to the objective under Slater’s constraint qualification and then apply the well known stochastic approximation (SA) method and the level function method to solve the penalized problem. Both methods are iterative: the former requires to calculate an approximate subgradient of the objective function of the penalized problem at each iterate while the latter requires to calculate a subgradient. Under some moderate conditions, we show that w.p.1 the sequence of approximated solutions generated by the SA method converges to an optimal solution of the true problem. As for the level function method, the convergence is deterministic and in some cases we are able to estimate the number of iterations for a given precision. Both methods are applied to portfolio optimization problem where the return functions are not necessarily linear and some numerical test results are reported.     

The Serret-Andoyer formalism in rigid-body dynamics: II. Geometry,stabilization, and control

This paper continues the review of the Serret-Andoyer (SA) canonical formalism in rigid-body dynamics, commenced by [1], and presents some new result. We discuss the applications of the SA formalism to control theory. Considerable attention is devoted to the geometry of the Andoyer variables and to the modeling of control torques. We develop a new approach to Stabilization of rigid-body dynamics, an approach wherein the state-space model is formulated through sets of canonical elements that partially or completely reduce the unperturbed Euler-Poinsot problem. The controllability of the system model is examined using the notion of accessibility, and is shown to be accessible. Based on the accessibility proof, a Hamiltonian controller is derived by using the Hamiltonian as a natural Lyapunov function for the closed-loop dynamics. It is shown that the Hamiltonian controller is both passive and inverse optimal with respect to a meaningful performance-index. Finally, we point out the possibility to apply methods of structure-preserving control using the canonical Andoyer variables, and we illustrate this approach on rigid bodies containing internal rotors.      

Descent Direction Stochastic Approximation Algorithm with Adaptive Step Sizes

A stochastic approximation (SA) algorithm with new adaptive step sizes for solving unconstrained minimization problems in noisy environment is proposed. New adaptive step size scheme uses ordered statistics of fixed number of previous noisy function values as a criterion for accepting good and rejecting bad steps. The scheme allows the algorithm to move in bigger steps and avoid steps proportional to $1/k$ when it is expected that larger steps will improve the performance. An algorithm with the new adaptive scheme is defined for a general descent direction. The almost sure convergence is established. The performance of new algorithm is tested on a set of standard test problems and compared with relevant algorithms. Numerical results support theoretical expectations and verify efficiency of the algorithm regardless of chosen search direction and noise level. Numerical results on problems arising in machine learning are also presented. Linear regression problem is considered using real data set. The results suggest that the proposed algorithm shows promise.