含不相关机的动态可重入柔性流水车间问题的混合DABC-GA算法

为了改善生产线的物流平衡和加强阶段间的时间衔接,扩展一般可重入柔性流水车间调度理论,以最小化总加权完工时间为目标,研究了每阶段含不相关并行机的动态可重入柔性流水车间问题,工件在各阶段的加工时间取决于加工它的机器。鉴于所研究问题为NP-hard问题,首先,建立整数规划模型;其次,设计元胞矩阵编码方案,提出融合离散人工蜂群算法和遗传算法的一种混合算法以获得问题的近优解;最后,为了评估混合算法的性能,将所提出算法和一些元启发式算法进行了不同规模问题的对比测试,实验结果说明了所提算法的有效性。     

求解混合流水线调度问题的离散人工蜂群算法

本文给出了一种离散的人工蜂群算法(HDABC)用于求解混合流水车间调度(HFS)问题。采用工件排序的编码方式,并设计了四种邻域结构。雇佣蜂依次分派到解集中每个解,采用结合问题特征的局部搜索策略完成挖掘搜索工作。跟随蜂随机选择两个解并挑选较优者作为当前解,完成进一步的探优过程。侦察蜂采用三种策略跳出局部极小。通过34个同构并行机HFS问题和2个异构并行机HFS实际调度问题的实验,并与当前文献中的典型算法对比,验证了本文提出的算法无论在算法时间还是在求解质量上,都具备良好的性能。     

A discrete bilevel brain storm algorithm for solving a sales territory design problem: a case study

A sales territory design problem faced by a manufacturing company that supplies products to a group of customers located in a service region is addressed in this paper. The planning process of designing the territories has the objective to minimizing the total dispersion of the customers without exceeding a limited budget assigned to each territory. Once territories have been determined, a salesperson has to define the day-by-day routes to satisfy the demand of customers. Currently, the company has established a service level policy that aims to minimize total waiting times during the distribution process. Also, each territory is served by a single salesperson. A novel discrete bilevel optimization model for the sales territory design problem is proposed. This problem can be seen as a bilevel problem with a single leader and multiple independent followers, in which the leader’s problem corresponds to the design of territories (manager of the company), and the routing decision for each territory corresponds to each follower. The hierarchical nature of the current company’s decision-making process triggers some particular characteristics of the bilevel model. A brain storm algorithm that exploits these characteristics is proposed to solve the discrete bilevel problem. The main features of the proposed algorithm are that the workload is used to verify the feasibility and to cluster the leader’s solutions. In addition, four discrete mechanisms are used to generate new solutions, and an elite set of solutions is considered to reduce computational cost. This algorithm is used to solve a real case study, and the results are compared against the current solution given by the company. Results show a reduction of more than 20% in the current costs with the solution obtained by the proposed algorithm. Furthermore, a sensitivity analysis is performed, providing interesting managerial insights to improve the current operations of the company.     

A biased random-key genetic algorithm with forward-backward improvement for the resource constrained project scheduling problem

This paper presents a biased random-key genetic algorithm for the resource constrained project scheduling problem. The chromosome representation of the problem is based on random keys. Active schedules are constructed using a priority-rule heuristic in which the priorities of the activities are defined by the genetic algorithm. A forward-backward improvement procedure is applied to all solutions. The chromosomes supplied by the genetic algorithm are adjusted to reflect the solutions obtained by the improvement procedure. The heuristic is tested on a set of standard problems taken from the literature and compared with other approaches. The computational results validate the effectiveness of the proposed algorithm.     

On the computation of all supported efficient solutions in multi-objective integer network flow problems

This paper presents a new algorithm for identifying all supported non-dominated vectors (or outcomes) in the objective space, as well as the corresponding efficient solutions in the decision space, for multi-objective integer network flow problems. Identifying the set of supported non-dominated vectors is of the utmost importance for obtaining a first approximation of the whole set of non-dominated vectors. This approximation is crucial, for example, in two-phase methods that first compute the supported non-dominated vectors and then the unsupported non-dominated ones. Our approach is based on a negative-cycle algorithm used in single objective minimum cost flow problems, applied to a sequence of parametric problems. The proposed approach uses the connectedness property of the set of supported non-dominated vectors/efficient solutions to find all integer solutions in maximal non-dominated/efficient facets.     

A discrete artificial bee colony algorithm for the no-idle permutation flowshop scheduling problem with the total tardiness criterion

In this paper, we present a discrete artificial bee colony algorithm to solve the no-idle permutation flowshop scheduling problem with the total tardiness criterion. The no-idle permutation flowshop problem is a variant of the well-known permutation flowshop scheduling problem where idle time is not allowed on machines. In other words, the start time of processing the first job on a given machine must be delayed in order to satisfy the no-idle constraint. The paper presents the following contributions: First of all, a discrete artificial bee colony algorithm is presented to solve the problem on hand first time in the literature. Secondly, some novel methods of calculating the total tardiness from makespan are introduced for the no-idle permutation flowshop scheduling problem. Finally, the main contribution of the paper is due to the fact that a novel speed-up method for the insertion neighborhood is developed for the total tardiness criterion. The performance of the discrete artificial bee colony algorithm is evaluated against a traditional genetic algorithm. The computational results show its highly competitive performance when compared to the genetic algorithm. Ultimately, we provide the best known solutions for the total tardiness criterion with different due date tightness levels for the first time in the literature for the Taillard’s benchmark suit.     

A modified method for constructing efficient solutions structure of MOLP

This paper deals with a recently proposed algorithm for obtaining all weak efficient and efficient solutions in a multi objective linear programming (MOLP) problem. The algorithm is based on solving some weighted sum problems, and presents an easy and clear solution structure. We first present an example to show that the algorithm may fail when at least one of these weighted sum problems has not a finite optimal solution. Then, the algorithm is modified to overcome this problem. The modified algorithm determines whether an efficient solution exists for a given MOLP and generates the solution set correctly (if exists) without any change in the complexity.     

Minimizing shifts for personnel task scheduling problems: A three-phase algorithm

The personnel task scheduling problem is a subject of commercial interest which has been investigated since the 1950s. This paper proposes an effective and efficient three-phase algorithm for solving the shift minimization personnel task scheduling problem (SMPTSP). To illustrate the increased efficacy of the proposed algorithm over an existing algorithm, computational experiments are performed on a test problem set with characteristics motivated by employee scheduling applications. Experimental results show that the proposed algorithm outperforms the existing algorithm in terms of providing optimal solutions, improving upon most of the best-known solutions and revealing high-quality feasible solutions for those unsolved test instances in the literature.     

High-Level Relay Hybrid Metaheuristic Method for Multi-Depot Vehicle Routing Problem with Time Windows

This paper presents an efficient hybrid metaheuristic solution for multi-depot vehicle routing with time windows (MD-VRPTW). MD-VRPTW involves the routing of a set of vehicles with limited capacity from a set of depots to a set of geographically dispersed customers with known demands and predefined time windows. The present work aims at using a hybrid metaheuristic algorithm in the class of High-Level Relay Hybrid (HRH) which works in three levels and uses an efficient genetic algorithm as the main optimization algorithm and tabu search as an improvement method. In the genetic algorithm various heuristics incorporate local exploitation in the evolutionary search. An operator deletion- retrieval strategy is executed which shows the efficiency of the inner working of the proposed method. The proposed algorithm is applied to solve the problems of the standard Cordeau??s Instances. Results show that proposed approach is quite effective, as it provides solutions that are competitive with the best known in the literature.     

The use of possibility theory in the definition of fuzzy Pareto-optimality

Pareto-optimality conditions are crucial when dealing with classic multi-objective optimization problems. Extensions of these conditions to the fuzzy domain have been discussed and addressed in recent literature. This work presents a novel approach based on the definition of a fuzzily ordered set with a view to generating the necessary conditions for the Pareto-optimality of candidate solutions in the fuzzy domain. Making use of the conditions generated, one can characterize fuzzy efficient solutions by means of carefully chosen mono-objective problems and Karush-Kuhn-Tucker conditions to fuzzy non-dominated solutions. The uncertainties are inserted into the formulation of the studied fuzzy multi-objective optimization problem by means of fuzzy coefficients in the objective function. Some numerical examples are analytically solved to illustrate the efficiency of the proposed approach.     

Martins' algorithm revisited for multi-objective shortest path problems with a MaxMin cost function

This paper presents a direct extension of the label setting algorithm proposed by Martins in 1984 for the shortest path problem with multiple objectives. This extended version computes all the efficient paths from a given source vertex, to all the other vertices of the network. The algorithm copes with problems in which the "cost values" associated with the network arcs are positive. The proposed extension can handle objective functions that are either of the "sum" type or of the "bottleneck" type. The main modifications to Martins' algorithm for multi-objective shortest path problems are linked to the dominance test and the procedure for identifying efficient paths. The algorithmic features are described and a didactic example is provided to illustrate the working principle. The results of numerical experiments concerning the number of efficient solutions produced and the CPU time consumed for several configurations of objectives, on a set of randomly generated networks, are also provided. Received: February 2005 / Revised version: June 2005 AMS classification: 90C29, 90C27, 05C38, 90B18, 68M12     

A novel bee swarm optimization algorithm for numerical function optimization

The optimization algorithms which are inspired from intelligent behavior of honey bees are among the most recently introduced population based techniques. In this paper, a novel algorithm called bee swarm optimization, or BSO, and its two extensions for improving its performance are presented. The BSO is a population based optimization technique which is inspired from foraging behavior of honey bees. The proposed approach provides different patterns which are used by the bees to adjust their flying trajectories. As the first extension, the BSO algorithm introduces different approaches such as repulsion factor and penalizing fitness (RP) to mitigate the stagnation problem. Second, to maintain efficiently the balance between exploration and exploitation, time-varying weights (TVW) are introduced into the BSO algorithm. The proposed algorithm (BSO) and its two extensions (BSO–RP and BSO–RPTVW) are compared with existing algorithms which are based on intelligent behavior of honey bees, on a set of well known numerical test functions. The experimental results show that the BSO algorithms are effective and robust; produce excellent results, and outperform other algorithms investigated in this consideration.     

Discrete Capacity Assignment in IP networks using Particle Swarm Optimization

This paper presents a design methodology for IP networks under end-to-end Quality-of-Service (QoS) constraints. Particularly, we consider a more realistic problem formulation in which the link capacities of a general-topology packet network are discrete variables. This Discrete Capacity Assignment (DCA) problem can be classified as a constrained combinatorial optimization problem. A refined TCP/IP traffic modeling technique is also considered in order to estimate performance metrics for networks loaded by realistic traffic patterns. We propose a discrete variable Particle Swarm Optimization (PSO) procedure to find solutions for the problem. A simple approach called Bottleneck Link Heuristic (BLH) is also proposed to obtain admissible solutions in a fast way. The PSO performance, compared to that one of an exhaustive search (ES) procedure, suggests that the PSO algorithm provides a quite efficient approach to obtain (near) optimal solutions with small computational effort.     

Optimised crossover genetic algorithm for capacitated vehicle routing problem

This paper presents a genetic algorithm for solving capacitated vehicle routing problem, which is mainly characterised by using vehicles of the same capacity based at a central depot that will be optimally routed to supply customers with known demands. The proposed algorithm uses an optimised crossover operator designed by a complete undirected bipartite graph to find an optimal set of delivery routes satisfying the requirements and giving minimal total cost. We tested our algorithm with benchmark instances and compared it with some other heuristics in the literature. Computational results showed that the proposed algorithm is competitive in terms of the quality of the solutions found.     

High-order adaptive Gegenbauer integral spectral element method for solving non-linear optimal control problems

In this work, we propose an adaptive spectral element algorithm for solving non-linear optimal control problems. The method employs orthogonal collocation at the shifted Gegenbauer–Gauss points combined with very accurate and stable numerical quadratures to fully discretize the multiple-phase integral form of the optimal control problem. The proposed algorithm relies on exploiting the underlying smoothness properties of the solutions for computing approximate solutions efficiently. In particular, the method brackets discontinuities and ‘points of nonsmoothness’ through a novel local adaptive algorithm, which achieves a desired accuracy on the discrete dynamical system equations by adjusting both the mesh size and the degree of the approximating polynomials. A rigorous error analysis of the developed numerical quadratures is presented. Finally, the efficiency of the proposed method is demonstrated on three test examples from the open literature.     

A discrete filled function algorithm for approximate global solutions of max-cut problems

A discrete filled function algorithm is proposed for approximate global solutions of max-cut problems. A new discrete filled function is defined for max-cut problems and the properties of the filled function are studied. Unlike general filled function methods, using the characteristic of max-cut problems, the parameters in proposed filled function need not be adjusted. This greatly increases the efficiency of the filled function method. By combining a procedure that randomly generates initial points for minimization of the filled function, the proposed algorithm can greatly reduce the calculation cost and be applied to large scale max-cut problems. Numerical results on different sizes and densities test problems indicate that the proposed algorithm is efficient and stable to get approximate global solutions of max-cut problems.     

New simulation-based frameworks for multi-objective reliability-based design optimization of structures

In the present study, two new simulation-based frameworks are proposed for multi-objective reliability-based design optimization (MORBDO). The first is based on hybrid non-dominated sorting weighted simulation method (NSWSM) in conjunction with iterative local searches that is efficient for continuous MORBDO problems. According to NSWSM, uniform samples are generated within the design space and, then, the set of feasible samples are separated. Thereafter, the non-dominated sorting operator is employed to extract the approximated Pareto front. The iterative local sample generation is then performed in order to enhance the accuracy, diversity, and increase the extent of non-dominated solutions. In the second framework, a pseudo-double loop algorithm is presented based on hybrid weighted simulation method (WSM) and the Non-dominated Sorting Genetic Algorithm II (NSGA-II) that is efficient for problems including both discrete and continuous variables. According to hybrid WSM-NSGA-II, proper non-dominated solutions are produced in each generation of NSGA-II and, subsequently, WSM evaluates the reliability level of each candidate solution until the algorithm converges to the true Pareto solutions. The valuable characteristic of presented approaches is that only one simulation run is required for WSM during entire optimization process, even if solutions for different levels of reliability be desired. Illustrative examples indicate that NSWSM with the proposed local search strategy is more efficient for small dimension continuous problems. However, WSM-NSGA-II outperforms NSWSM in terms of solutions quality and computational efficiency, specifically for discrete MORBDOs. Employing global optimizer in WSM-NSGA-II provided more accurate results with lower samples than NSWSM.     

A simple greedy algorithm for a class of shuttle transportation problems

Greedy algorithms for combinatorial optimization problems are typically direct and efficient, but hard to prove optimality. The paper presents a special class of transportation problems where a supplier sends goods to a set of customers, returning to the source after each delivery. We show that these problems with different objective functions share a common structural property, and therefore a simple but powerful generic greedy algorithm yields optimal solutions for all of them.     

Bees algorithm for generalized assignment problem

Bees algorithm (BA) is a new member of meta-heuristics. BA tries to model natural behavior of honey bees in food foraging. Honey bees use several mechanisms like waggle dance to optimally locate food sources and to search new ones. This makes them a good candidate for developing new algorithms for solving optimization problems. In this paper a brief review of BA is first given, afterwards development of a BA for solving generalized assignment problems (GAP) with an ejection chain neighborhood mechanism is presented. GAP is a NP-hard problem. Many meta-heuristic algorithms were proposed for its solution. So far BA is generally applied to continuous optimization. In order to investigate the performance of BA on a complex integer optimization problem, an attempt is made in this paper. An extensive computational study is carried out and the results are compared with several algorithms from the literature.     

A self-adaptive global best harmony search algorithm for continuous optimization problems

This paper presents a self-adaptive global best harmony search (SGHS) algorithm for solving continuous optimization problems. In the proposed SGHS algorithm, a new improvisation scheme is developed so that the good information captured in the current global best solution can be well utilized to generate new harmonies. The harmony memory consideration rate (HMCR) and pitch adjustment rate (PAR) are dynamically adapted by the learning mechanisms proposed. The distance bandwidth (BW) is dynamically adjusted to favor exploration in the early stages and exploitation during the final stages of the search process. Extensive computational simulations and comparisons are carried out by employing a set of 16 benchmark problems from literature. The computational results show that the proposed SGHS algorithm is more effective in finding better solutions than the state-of-the-art harmony search (HS) variants.