A Pareto-based hybrid multiobjective evolutionary approach for constrained multipath traffic engineering optimization in MPLS/GMPLS networks

This paper proposes a hybrid evolutionary algorithm for solving the constrained multipath traffic engineering problem in MPLS (Multi-Protocol Label Switching) network and its extended architecture GMPLS (Generalized MPLS). Multipath traffic engineering is gaining more importance in contemporary networks. It aims to satisfy the requirements of emerging network applications while optimizing the network performance and the utilization of the available resources within the network. A formulation of this problem as a multiobjective constrained mixed-integer program, which is known to be NP-hard, is first extended. Then, we develop a hybrid heuristic algorithm based on combining linear programming with a devised Pareto-based genetic algorithm for approximating the optimal Pareto curve. A numerical example is adopted from the literature to evaluate and compare the performance of six variations of the proposed heuristic. We study the statistical significance of the results using Kruskal–Wallis nonparametric test. We also compare the results of the heuristic approach with the lexicographic weighted Chebyshev method using a variety of performance metrics.     

Minimizing makespan in a flow shop with two batch-processing machines using simulated annealing

This paper aims at minimizing the makespan of two batch-processing machines in a flow shop. The processing times and the sizes of the jobs are known and non-identical. The machines can process a batch as long as its capacity is not exceeded. The processing time of a batch is the longest processing time among all the jobs in that batch. The problem under study is NP-hard for makespan objective. Consequently, a heuristic based on Johnson's algorithm and a simulated annealing (SA) algorithm is proposed. Random instances were generated to verify the effectiveness of the proposed approaches. The results obtained from SA were compared with the proposed heuristic and a commercial solver. The SA outperformed both the heuristic and the commercial solver. On larger problem instances, the heuristic outperformed the commercial solver.     

Maximum lifetime data sensing and extraction in energy constrained networked sensor systems

We focus on data gathering problems in energy constrained networked sensor systems. The system operates in rounds where a subset of the sensors generate a certain number of data packets during each round. All the data packets need to be transferred to the base station. The goal is to maximize the system lifetime in terms of the number of rounds the system can operate. We show that the above problem reduces to a restricted flow problem with quota constraint, flow conservation requirement, and edge capacity constraint. We further develop a strongly polynomial time algorithm for this problem, which is guaranteed to find an optimal solution. We then study the performance of a distributed shortest path heuristic for the problem. This heuristic is based on self-stabilizing spanning tree construction and shortest path routing methods. In this heuristic, every node determines its sensing activities and data transfers based on locally available information. No global synchronization is needed. Although the heuristic cannot guarantee optimality, simulations show that the heuristic has good average case performance over randomly generated deployment of sensors. We also derive bounds for the worst case performance of the heuristic.     

Scheduling precedence constrained task graphs with non-negligibleintertask communication onto multiprocessors

The multiprocessor scheduling problem is the problem of scheduling the tasks of a precedence constrained task graph (representing a parallel program) onto the processors of a multiprocessor in a way that minimizes the completion time. Since this problem is known to be NP-hard in the strong sense in all but a few very restricted eases, heuristic algorithms are being developed which obtain near optimal schedules in a reasonable amount of computation time. We present an efficient heuristic algorithm for scheduling precedence constrained task graphs with nonnegligible intertask communication onto multiprocessors taking contention in the communication channels into consideration. Our algorithm for obtaining satisfactory suboptimal schedules is based on the classical list scheduling strategy. It simultaneously exploits the schedule-holes generated in the processors and in the communication channels during the scheduling process in order to produce better schedules. We demonstrate the effectiveness of our algorithm by comparing with two competing heuristic algorithms available in the literature     

On scheduling transactions in a grid processing system considering load through Ant Colony Optimization

Load balanced transaction scheduling problem is an important issue in distributed computing environments including grid system. This problem is known to be NP-hard and can be solved by using heuristic as well as any meta-heuristic method. We ponder over the problem of the load balanced transaction scheduling in a grid processing system by using an Ant Colony Optimization for load balancing. The problem that we consider is to achieve good execution characteristics for a given set of transactions that has to be completed within their given deadline. We propose a transaction processing algorithm based on Ant Colony Optimization (ACO) for load balanced transaction scheduling. We modify two meta-heuristic along with ACO and three heuristic scheduling algorithms for the purpose of comparison with our proposed algorithm. The results of the comparison show that the proposed algorithm provides better results for the load balanced transaction scheduling in the grid processing system.     

A heuristic algorithm for optimal fleet composition with vehicle routing considerations

This paper proposes a fast heuristic algorithm for solving a combined optimal fleet composition and multi-period vehicle routing problem. The aim of the problem is to determine an optimal fleet mix, together with the corresponding vehicle routes, to minimize total cost subject to various customer delivery requirements and vehicle capacity constraints. The total cost includes not only the fixed, variable, and transportation costs associated with operating the fleet, but also the hiring costs incurred whenever vehicle requirements exceed fleet capacity. Although the problem under consideration can be formulated as a mixed-integer linear program (MILP), the MILP formulation for realistic problem instances is too large to solve using standard commercial solvers such as the IBM ILOG CPLEX optimization tool. Our proposed heuristic decomposes the problem into two tractable stages: in the first (outer) stage, the vehicle routes are optimized using cross entropy; in the second (inner) stage, the optimal fleet mix corresponding to a fixed set of routes is determined using dynamic programming and golden section search. Numerical results show that this heuristic approach generates high-quality solutions and significantly outperforms CPLEX in terms of computational speed.     

数据立方体选择的改进遗传算法

数据立方体选择问题是一个NP完全问题。研究了利用遗传算法来解决立方体选择问题,提出了一个结合局部搜索机制的遗传算法。这一算法的核心思想在于,首先运用一个基于单位空间最大收益值的预处理算法来生成初始解,然后该初始解经结合了局部搜索机制的遗传算法进行提高。实验结果表明,该算法在寻优性能上优于启发式算法和经典遗传算法。     

Applying multi-objective ant colony optimization algorithm for solving the unequal area facility layout problems

The unequal area facility layout problem (UA-FLP) which deals with the layout of departments in a facility comprises of a class of extremely difficult and widely applicable multi-objective optimization problems with constraints arising in diverse areas and meeting the requirements for real-world applications. Based on the heuristic strategy, the problem is first converted into an unconstrained optimization problem. Then, we use a modified version of the multi-objective ant colony optimization (MOACO) algorithm which is a heuristic global optimization algorithm and has shown promising performances in solving many optimization problems to solve the multi-objective UA-FLP. In the modified MOACO algorithm, the ACO with heuristic layout updating strategy which is proposed to update the layouts and add the diversity of solutions is a discrete ACO algorithm, with a difference from general ACO algorithms for discrete domains which perform an incremental construction of solutions but the ACO in this paper does not. We propose a novel pheromone update method and combine the Pareto optimization based on the local pheromone communication and the global search based on the niche technology to obtain Pareto-optimal solutions of the problem. In addition, the combination of the local search based on the adaptive gradient method and the heuristic department deformation strategy is applied to deal with the non-overlapping constraint between departments so as to obtain feasible solutions. Ten benchmark instances from the literature are tested. The experimental results show that the proposed MOACO algorithm is an effective method for solving the UA-FLP.     

求解矩形Packing问题的砌墙式启发式算法

为求解正交矩形Packing问题提出了一个新颖而有效的砌墙式启发式算法.该算法主要基于砌墙式启发式策略,其思想主要来源于砖匠在砌墙过程中所积累的经验:基于基准砖的砌墙规则.对国际上公认的大量的Bench-mark问题例的计算结果表明,该算法的计算速度不仅比著名的现代启发式算法快,而且获得更优的高度.     

Using genetic algorithms to design mesh networks

Designs for mesh communication networks must meet conflicting, interdependent requirements. This sets the stage for a complex problem with a solution that targets optimal topological connections, routing, and link capacity assignments. These assignments must minimize cost while satisfying traffic requirements and keeping network delays within permissible values. Since such a problem is NP-complete, developers must use heuristic techniques to handle the complexity and solve practical problems with a modest number of nodes. One heuristic technique, genetic algorithms, appears to be ideal to handle the design of mesh networks with capability of handling discrete values, multiobjective functions, and multiconstraint problems. Existing applications of genetic algorithms to this problem, however, have only optimized the network topology. They ignore the difficult subproblems of routing and capacity assignment, a crucial determiner of network quality and cost. This article presents a total solution to mesh network design using a genetic algorithm approach. The application is a 10-city network that links Hong Kong and nine other cities in China. The development demonstrates that this method can be used for networks of reasonable size with realistic topology and traffic requirements     

Manufacturing lot-sizing under MRP II environment: An improved analytical model & heuristic procedure

Under single-level lot-sizing problem, well known Wagner-Whitin algorithm based on Dynamic Programming (DP) provides optimal order schedule. Order schedule does not work properly under Manufacturing Resource Planning (MRP II), where it is considered multi-level capacitated problem and requirements of subcomponents are depend on the parent product. In this paper, we formulate a multi-level capacitated optimization model and develop a relatively efficient heuristic working under MRP II environment which considers work center capacities and interrelationship between levels in lot-sizing computation.     

Order acceptance and scheduling to maximize total net revenue in permutation flowshops with weighted tardiness

The order acceptance and scheduling (OAS) problem is important in make-to-order production systems in which production capacity is limited and order delivery requirements are applied. This study proposes a multi-initiator simulated annealing (MSA) algorithm to maximize the total net revenue for the permutation flowshop scheduling problem with order acceptance and weighted tardiness. To evaluate the performance of the proposed MSA algorithm, computational experiments are performed and compared for a benchmark problem set of test instances with up to 500 orders. Experimental results reveal that the proposed heuristic outperforms the state-of-the-art algorithm and obtains the best solutions in 140 out of 160 benchmark instances.     

A two-dimensional vector packing model for the efficient use of coil cassettes

We consider the problem of efficiently packing steel products, known as coils, into special containers, called cassettes for shipping. The objective is to minimize the number of cassettes used for packing all the given coils where each cassette has capacity limits on both total payload weight and size. We model this problem as a two-dimensional vector packing problem and propose a heuristic. We also analyze the worst-case performance of the proposed algorithm under a special condition which, in fact, holds for the particular real-world case that we handled. Our computational experiment with real production data shows that the proposed algorithm performs quite satisfactorily in practice.     

Decomposition heuristics for minimizing earliness–tardiness on parallel burn-in ovens with a common due date

This paper considers a scheduling problem for parallel burn-in ovens in the semiconductor manufacturing industry. An oven is a batch processing machine with restricted capacity. The batch processing time is set by the longest processing time among those of all the jobs contained in the batch. All jobs are assumed to have the same due date. The objective is to minimize the sum of the absolute deviations of completion times from the due date (earliness–tardiness) of all jobs. We suggest three decomposition heuristics. The first heuristic applies the exact algorithm due to Emmons and Hall (for the nonbatching problem) in order to assign the jobs to separate early and tardy job sets for each of the parallel burn-in ovens. Then, we use job sequencing rules and dynamic programming in order to form batches for the early and tardy job sets and sequence them optimally. The second proposed heuristic is based on genetic algorithms. We use a genetic algorithm in order to assign jobs to each single burn-in oven. Then, after forming early and tardy job sets for each oven we apply again sequencing rules and dynamic programming techniques to the early and tardy jobs sets on each single machine in order to form batches. The third heuristic assigns jobs to the m early job sets and m tardy jobs sets in case of m burn-in ovens in parallel via a genetic algorithm and applies again dynamic programming and sequencing rules. We report on computational experiments based on generated test data and compare the results of the heuristics with known exact solution for small size test instances obtained from a branch and bound scheme.     

An LP-based heuristic algorithm for the node capacitated in-tree packing problem

In this paper, we deal with the node capacitated in-tree packing problem. The input consists of a directed graph, a root node, a node capacity function and edge consumption functions for heads and tails. The problem is to find a subset of rooted spanning in-trees and their packing numbers, where the packing number of an in-tree is the number of times it is packed, so as to maximize the sum of packing numbers under the constraint that the total consumption of the packed in-trees at each node does not exceed the capacity of the node. This problem is known to be NP-hard.We propose a two-phase heuristic algorithm for this problem. In the first phase, it generates candidate spanning in-trees to be packed. The node capacitated in-tree packing problem can be formulated as an IP (integer programming) problem, and the proposed algorithm employs the column generation method for the LP (linear programming) relaxation problem of the IP to generate promising candidate in-trees. In the second phase, the algorithm computes the packing number of each in-tree. Our algorithm solves this second-phase problem by first modifying feasible solutions of the LP relaxation problem and then improving them with a greedy algorithm. We analyze upper and lower bounds on the solution quality of such LP-based algorithms for this problem.We conducted computational experiments on graphs used in related papers and on randomly generated graphs. The results indicate that our algorithm has a better performance than other existing methods.     

A genetic-algorithm-based heuristic for the GT cell formation problem

This paper presents a heuristic for the machine-part grouping problem which incorporates relevant production requirements such as routing sequence, production volume, unit handling size, unit processing time and cell size. The heuristic consists of two phases. The first phase is developed based on a genetic algorithm and greedy heuristic to solve the machine grouping problem. Once machine cells are identified, the second phase is employed to identify the associated part families. The performance of the heuristic is examined through a comparative study with some existing solution methods. Global efficiency, group efficiency, intercell move factor and grouping effectiveness are adopted as comparative measures.     

A new ant colony optimization based algorithm for data allocation problem in distributed databases

The Performance and the efficiency of a distributed database system depend highly on the way data are allocated to the sites. The NP-completeness of the data allocation problem and the large size of its real occurrence, call for employing a fast and scalable heuristic algorithm. In this paper, we address the data allocation problem in terms of minimizing two different types of data transmission across the network, i.e., data transmissions due to site-fragment dependencies and those caused by inter-fragment dependencies. We propose a new heuristic algorithm which is based on the ant colony optimization meta-heuristic, with regards to the applied strategies for query optimization and integrity enforcement. The goal is to design an efficient data allocation scheme to minimize the total transaction response time under memory capacity constraints of the sites. Experimental tests indicate that our algorithm is capable of producing near- optimal solutions within a reasonable time. The results also reveal the flexibility and scalability of the proposed algorithm.     

多星联合动态调度问题的启发式算法研究

对地观测多星联合动态调度问题是一类复杂的调度问题。在对多星联合动态调度问题的动态来源进行深入分析的基础上,对该问题进行了统一描述。针对问题的特点,提出了一种基于规则的启发式求解算法,设计了最大竞争度的退出启发式规则和最小冲突度的插入启发式规则。最后给出了一个应用实例,对算法进行了验证。     

Scheduling two-machine no-wait open shops to minimize makespan

This paper examines the problem of scheduling two-machine no-wait open shops to minimize makespan. The problem is known to be strongly NP-hard. An exact algorithm, based on a branch-and-bound scheme, is developed to optimally solve medium-size problems. A number of dominance rules are proposed to improve the search efficiency of the branch-and-bound algorithm. An efficient two-phase heuristic algorithm is presented for solving large-size problems. Computational results show that the branch-and-bound algorithm can solve problems with up to 100 jobs within a reasonable amount of time. For large-size problems, the solution obtained by the heuristic algorithm has an average percentage deviation of 0.24% from a lower bound value.