A hybrid scatter search/electromagnetism meta-heuristic for project scheduling

In the last few decades, several effective algorithms for solving the resource-constrained project scheduling problem have been proposed. However, the challenging nature of this problem, summarised in its strongly NP-hard status, restricts the effectiveness of exact optimisation to relatively small instances. In this paper, we present a new meta-heuristic for this problem, able to provide near-optimal heuristic solutions for relatively large instances. The procedure combines elements from scatter search, a generic population-based evolutionary search method, and from a recently introduced heuristic method for the optimisation of unconstrained continuous functions based on an analogy with electromagnetism theory. We present computational experiments on standard benchmark datasets, compare the results with current state-of-the-art heuristics, and show that the procedure is capable of producing consistently good results for challenging instances of the resource-constrained project scheduling problem. We also demonstrate that the algorithm outperforms state-of-the-art existing heuristics.     

A tree search method for the container loading problem with shipment priority

This paper addresses a special kind of container loading problem with shipment priority. We present a tree search method, which is based on a greedy heuristic. In the greedy heuristic, blocks made up of identical items with the same orientation are selected for packing into a container. Five evaluation functions are proposed for block selection, and the different blocks selected by each evaluation function constitute the branches of the search tree. A method of space splitting and merging is also embedded in the algorithm to facilitate efficient use of the container space. In addition, the proposed algorithm covers an important constraint called shipment priority to solve practical problems. The validity of the proposed algorithm is examined by comparing the present results with those of published algorithms using the same data.     

A hybrid tabu search/branch & bound approach to solving the generalized assignment problem

A new approach for solving the generalized assignment problem (GAP) is proposed that combines the exact branch & bound approach with the heuristic strategy of tabu search (TS) to produce a hybrid algorithm for solving GAP. The algorithm described uses commercial software to solve sub-problems generated by the TS guiding strategy. The TS approach makes use of the concept of referent domain optimisation and introduces novel add/drop strategies. In addition, the linear programming relaxation of GAP that forms part of the branch & bound approach is itself helpful in suggesting which variables might take binary values. Computational results on benchmark test instances are presented and compared with results obtained by the standard branch & bound approach and also several other heuristic approaches from the literature. The results show the new algorithm performs competitively against the alternatives and is able to find some new best solutions for several benchmark instances.     

The influence of the fitness evaluation method on the performance of multiobjective search algorithms

In this paper we are concerned with finding the Pareto optimal front or a good approximation to it. Since non-dominated solutions represent the goal in multiobjective optimisation, the dominance relation is frequently used to establish preference between solutions during the search. Recently, relaxed forms of the dominance relation have been proposed in the literature for improving the performance of multiobjective search methods. This paper investigates the influence of different fitness evaluation methods on the performance of two multiobjective methodologies when applied to a highly constrained two-objective optimisation problem. The two algorithms are: the Pareto archive evolutionary strategy and a population-based annealing algorithm. We demonstrate here, on a highly constrained problem, that the method used to evaluate the fitness of candidate solutions during the search affects the performance of both algorithms and it appears that the dominance relation is not always the best method to use.     

A vehicle routing problem with multi-trips and time windows for circular items

This article presents a vehicle routing problem with time windows, multiple trips, a limited number of vehicles and loading constraints for circular objects. This is a real problem experienced by a home delivery service company. A linear model is proposed to handle small problems and a two-step heuristic method to solve real size instances: the first step builds an initial solution through the modification of the Solomon I1 sequential insertion heuristic, and the second step improves the initial solution through the Tabu search algorithm proposed; in both steps, the problems related to circle packing with different sizes and bin packing are solved jointly with the use of heuristics. Finally, the computing results for two different sets of instances are presented.     

On convergence of a smoothing Broyden-like method for P0-NCP

A smoothing Broyden-like method is proposed for solving nonlinear complementarity problem in this paper. The algorithm considered here is based on the smooth approximation Fischer–Burmeister function and makes use of the line search rule of Li and Fukushima [A derivative-free line search and global convergence of Broyden-like method for nonlinear equations, Optim. Methods Software 13(3) (2000) 181–201]. Under suitable conditions, the iterates generated by the proposed method converge to a solution of the nonlinear complementarity problem globally and superlinearly.     

A smoothing Newton method for NCPs with the P0-property

In this paper, we first investigate a two-parametric class of smoothing functions which contains the penalized smoothing Fischer-Burmeister function and the penalized smoothing CHKS function as special cases. Then we present a smoothing Newton method for the nonlinear complementarity problem based on the class of smoothing functions. Issues such as line search rule, boundedness of the level set, global and quadratic convergence are studied. In particular, we give a line search rule containing the common used Armijo-type line search rule as a special case. Also without requiring strict complementarity assumption at the P₀-NCP solution or the nonemptyness and boundedness of the solution set, the proposed algorithm is proved to be globally convergent. Preliminary numerical results show the efficiency of the algorithm and provide efficient domains of the two parameters for the complementarity problems.     

MultiGLODS: global and local multiobjective optimization using direct search

The optimization of multimodal functions is a challenging task, in particular when derivatives are not available for use. Recently, in a directional direct search framework, a clever multistart strategy was proposed for global derivative-free optimization of single objective functions. The goal of the current work is to generalize this approach to the computation of global Pareto fronts for multiobjective multimodal derivative-free optimization problems. The proposed algorithm alternates between initializing new searches, using a multistart strategy, and exploring promising subregions, resorting to directional direct search. Components of the objective function are not aggregated and new points are accepted using the concept of Pareto dominance. The initialized searches are not all conducted until the end, merging when they start to be close to each other. The convergence of the method is analyzed under the common assumptions of directional direct search. Numerical experiments show its ability to generate approximations to the different Pareto fronts of a given problem.     

A primal algorithm for the weighted minimum covering ball problem in $$\mathbb {R}^n$$

The nonlinear programming problem of finding the minimum covering ball of a finite set of points in \(\mathbb {R}^n\), with a positive weight corresponding to each point, is solved by a directional search method. At each iteration, the search path is either a ray or the arc of a circle and is determined by bisectors of points. Each step size along the search path is determined explicitly. The primal algorithm is shown to search along the farthest point Voronoi diagram of the given points. We provide computational results that show the efficiency of the algorithm when compared to general convex nonlinear optimization solvers.     

Recovering Beam Search: Enhancing the Beam Search Approach for Combinatorial Optimization Problems

A hybrid heuristic method for combinatorial optimization problems is proposed that combines different classical techniques such as tree search procedures, bounding schemes and local search. The proposed method enhances the classic beam search approach by applying to each partial solution corresponding to a node selected by the beam, a further test that checks whether the current partial solution is dominated by another partial solution at the same level of the search tree. If this is the case, the latter solution becomes the new current partial solution. This step allows to partially recover from previous wrong decisions of the beam search procedure and can be seen as a local search step on the partial solution. We present here the application to two well known combinatorial optimization problems: the two-machine total completion time flow shop scheduling problem and the uncapacitated p-median location problem. In both cases the method strongly improves the performances with respect to the basic beam search approach and is competitive with the state of the art heuristics.     

双机成比例无等待流水线重调度干扰管理研究

针对由异速机构成的双机成比例无等待流水线的加工特点,研究了机器扰动工况下的生产重调度问题,提出了兼顾初始调度目标(最小化制造期)和扰动修复目标(最小化工件滞后时间和)的干扰管理方法。在最短加工时间优先(SPT)排序规则的最优解特性分析基础上,证明了右移初始加工时间表是事后干扰管理的最优调度方案,建立了基于SPT规则的事前干扰管理模型,设计了基于理想点趋近的多目标处理策略,提出了离散量子微粒群优化与局部搜索机制相结合的启发式模型求解算法。算例实验结果表明,本文提出的干扰管理模型和算法是有效的。     

A hybrid genetic algorithm for the job shop scheduling problem

This paper presents a hybrid genetic algorithm for the job shop scheduling problem. The chromosome representation of the problem is based on random keys. The schedules are constructed using a priority rule in which the priorities are defined by the genetic algorithm. Schedules are constructed using a procedure that generates parameterized active schedules. After a schedule is obtained a local search heuristic is applied to improve the solution. The approach is tested on a set of standard instances taken from the literature and compared with other approaches. The computation results validate the effectiveness of the proposed algorithm.     

Solving a Real World Assignment Problem with a Metaheuristic

This paper investigates a real world assignment problem, which slightly differs from the classical generalized assignment problem (GAP). The large-scale number of variables in the related 0-1 linear program makes the use of commercial optimization packages impractical. We present here a metaheuristic using simulated annealing. It is based on successive reductions of the search space by identification of locally active constraints. Our approach employs a heuristic procedure to compute an initial (feasible or infeasible) 0/1 solution, and a double-criterion acceptance rule. The performance of the algorithm is demonstrated on real data sets.     

A probabilistic greedy search algorithm for combinatorial optimisation with application to the set covering problem

We present a probabilistic greedy search method for combinatorial optimisation problems. This approach is implemented and evaluated for the Set Covering Problem (SCP) and shown to yield a simple, robust, and quite fast heuristic. Tests performed on a large set of benchmark instances with up to 1000 rows and 10?000 columns show that the algorithm consistently yields near-optimal solutions.     

General variable neighborhood search for the continuous optimization

We suggest a new heuristic for solving unconstrained continuous optimization problems. It is based on a generalized version of the variable neighborhood search metaheuristic. Different neighborhoods and distributions, induced from different metrics are ranked and used to get random points in the shaking step. We also propose VNS for solving constrained optimization problems. The constraints are handled using exterior point penalty functions within an algorithm that combines sequential and exact penalty transformations. The extensive computer analysis that includes the comparison with genetic algorithm and some other approaches on standard test functions are given. With our approach we obtain encouraging results.     

Minimizing the total completion time in a two-machine flowshop with sequence-independent setup times

We consider the problem of minimizing the sum of completion times in a two-machine permutation flowshop subject to setup times. We propose a new priority rule, several constructive heuristics, local search procedures, as well as an effective multiple crossover genetic algorithm. Computational experiments carried out on a large set of randomly generated instances provide evidence that a constructive heuristic based on newly derived priority rule dominates all the proposed constructive heuristics. More specifically, we show that one of our proposed constructive heuristics outperforms the best constructive heuristic in the literature in terms of both error and computational time. Furthermore, we show that one of our proposed local search-based heuristics outperforms the best local search heuristic in the literature in terms of again both error and computational time. We also show that, in terms of quality-to-CPU time ratio, the multiple crossover genetic algorithm performs consistently well.     

Incorporating minimum Frobenius norm models in direct search

The goal of this paper is to show that the use of minimum Frobenius norm quadratic models can improve the performance of direct-search methods. The approach taken here is to maintain the structure of directional direct-search methods, organized around a search and a poll step, and to use the set of previously evaluated points generated during a direct-search run to build the models. The minimization of the models within a trust region provides an enhanced search step. Our numerical results show that such a procedure can lead to a significant improvement of direct search for smooth, piecewise smooth, and noisy problems.     

A two-stage intelligent search algorithm for the two-dimensional strip packing problem

This paper presents a two-stage intelligent search algorithm for a two-dimensional strip packing problem without guillotine constraint. In the first stage, a heuristic algorithm is proposed, which is based on a simple scoring rule that selects one rectangle from all rectangles to be packed, for a given space. In the second stage, a local search and a simulated annealing algorithm are combined to improve solutions of the problem. In particular, a multi-start strategy is designed to enhance the search capability of the simulated annealing algorithm. Extensive computational experiments on a wide range of benchmark problems from zero-waste to non-zero-waste instances are implemented. Computational results obtained in less than 60 seconds of computation time show that the proposed algorithm outperforms the supposedly excellent algorithms reported recently, on average. It performs particularly better for large instances.     

A tabu search algorithm for solving economic lot scheduling problem

The economic lot scheduling problem has driven considerable amount of research. The problem is NP-hard and recent research is focused on finding heuristic solutions rather than searching for optimal solutions. This paper introduces a heuristic method using a tabu search algorithm to solve the economic lot scheduling problem. Diversification and intensification schemes are employed to improve the efficiency of the proposed Tabu search algorithm. Experimental design is conducted to determine the best operating parameters for the Tabu search. Results show that the tabu search algorithm proposed in this paper outperforms two well known benchmark algorithms.     

An effective heuristic for minimising makespan on unrelated parallel machines

Scheduling independent tasks on unrelated machines is a relatively difficult and challenging problem. In this paper, we develop a tabu search based heuristic for minimising makespan for the above problem that can provide good quality solutions for practical size problems within a reasonable amount of computational time. Our adaptation of this tabu search uses hashing to control the tabu restrictions of the search process and requires fewer critical parameters than many of the common tabu search approaches employed for combinatorial optimisation. Hashing is simple to implement and very effective in providing a near-optimal solution. Computational results are presented to demonstrate the effectiveness of the proposed heuristic.