The hierarchical network problem is the problem of finding the least cost network, with nodes divided into groups, edges connecting nodes in each groups and groups ordered in a hierarchy. The idea of hierarchical networks comes from telecommunication networks where hierarchies exist. Hierarchical networks are described and a mathematical model is proposed for a two … Read more
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 … Read more
Given N customers and a set F of M potential facilities, the P-median problem consists in finding a subset of F with P facilities such that the cost of serving all customers is minimized. This is a well-known NP-complete problem with important applications in location science and classification (clustering). We present here a GRASP (Greedy … Read more
Given an undirected graph with edge weights, the MAX-CUT problem consists in finding a partition of the nodes into two subsets, such that the sum of the weights of the edges having endpoints in different subsets is maximized. It is a well-known NP-hard problem with applications in several fields, including VLSI design and statistical physics. … Read more
We propose in this work a hybrid improvement procedure for the bin packing problem. This heuristic has several features: the use of lower bounding strategies; the generation of initial solutions by reference to the dual min-max problem; the use of load redistribution based on dominance, differencing, and unbalancing; and the inclusion of an improvement process … Read more
We describe a new neighborhood structure for the capacitated minimum spanning tree problem. This neighborhood structure is used by a local search strategy, leading to good trade-offs between solution quality and computation time. We also propose a GRASP with path-relinking heuristic. It uses a randomized version of a savings heuristic in the construction phase and … Read more
This paper illustrates results obtained by a new metaheuristic approach, Greedy Randomized Adaptive Path Relinking, applied to solve static power transmission network design problems. This new approach consists of a generalization of GRASP concepts to explore different trajectories between two CitationAT&T Labs Research Report, December 2001 Submitted to PSCC’02.ArticleDownload View PDF
The Dedicated Aircraft Recovery Problem (DARP) involves decisions concerning aircraft to flight assignments in situations where unforeseen events have disrupted the existing flight schedule, e.g. bad weather causing flight delays. The dedicated aircraft recovery problem aims to recover these flight schedules through a series of reassignments of aircraft to flights, delaying of flights and cancellations … Read more
We present a heuristic method for general 0-1 mixed integer programming, intended for eventual incorporation into parallel branch-and-bound methods for solving such problems exactly. The core of the heuristic is a rounding method based on simplex pivots, employing only gradient information, for a strictly concave, differentiable merit function measuring integer feasibility. When local minima of … Read more
In the job shop scheduling problem (JSP), a finite set of jobs is processed on a finite set of machines. Each job is required to complete a set of operations in a fixed order. Each operation is processed on a specific machine for a fixed duration. A machine can process no more than one job … Read more