Streams - Meta heuristics

Organiser: Ralf Keuthen

to name but a few, have been proposed to tackle these usually large and complex problems. The metaheuristic stream at YOR12 is open to all of these heuristic and metaheuristic approaches for solving real life applications as well as combinatorial optimisation problems.

29-Mar-01:11:00:Pope C15
Heuristic and metaheuristic approaches to optimize component placement in the Assembly of Printed Circuit Boards
Keuthen, Ralf, Cowling Peter and Burke Edmund, University of Nottingham

This talk considers scheduling problems arising for numerically controlled machines in the assembly of printed circuit boards. In order to maximize the throughput rate of these machines the time taken for the pick and place sequence of components for each board has to be minimized. The determination of good pick and place sequences for component placement machine gives rise to various closely related combinatorial optimization problems. Considering the assembly of a set of Printed Circuit Boards on a single machine the initial problem can be divided into three subproblems:

1. the order in which the different circuit board types should be processed on the machine,
2. the assignment of component types to feeder rack locations for each circuit board,
3. the component placement sequence for each board.

Further complicating factors to this complex multilevel scheduling problem may be introduced by tool switches, machinery specifications or multiple machines on a production line. This talk is going to present suitable models for this complex scheduling problem and introduce heuristic and metaheuristic techniques to determine good, locally optimal solutions.

Keywords: heuristics, modelling, production scheduling

29-Mar-01:11:30:Pope C15
A Long-Haul Truck Scheduling Problem with Time Windows
Neri, Patricia, Mitchell Lee and Ware Keith, United Parcel Service

We consider a long-haul truck scheduling problem with time windows, multiple depots, and a heterogeneous vehicle fleet. Trips may be composed of several loops between domiciles, must last for a week, and may start on any day of the week. The Problem is complicated by several agreements regulating the cost, duration, required rest periods, and starting locations of trips. Equipment must balance between loops. The overall objective is to minimize total cost.

We implemented a model for solving this problem using ILOG's Optimization Programming Language, a modeling language for combinatorial optimization that supports constraint programming. We describe our model, solution approach and experiences in solving this problem.

29-Mar-01:12:00:Pope C15
Tabu Search for 0-1 Multidimensional Knapsack Revisited: Choosing Internal Heuristics and Fine Tuning of Parameters
Blesa, M. Josep & Hernandez, Lluis & Xhafa, Fatos, Departament de Llenguatges i Sistemes Informatics, Universitat Politecnica de Catalunya (SPAIN)

We present a new implementation of Tabu Search (TS) method for 0-1 Multi-dimensional Knapsack problem. This problem is a widely studied combinatorial optimization problem and is known to belong to the class of NP-hard problems (Garey and Johnson, 1979). Several heuristics have been applied to sub-optimally solve it, among those heuristics there is also the Tabu Search, first applied to the problem by Glover et al., 1996 (see also, Hanafi et al., 1996).

TS is a general method for sub-optimally solving hard combinatorial problems. It is, in fact, a meta-heuristic since it uses internally several heuristics such as intensification, diversification, neigborhood exploration, etc. Due to this, TS is quite flexible and hence different implementation of the method for the same problem are possible. The success of the method depends on the careful choice of these heuristics and on the fine tuning of parameters such as number of intensifications, number of diversifications, when to intensifiy/diversify the search, the number of iterations an item remains tabu, etc.

We present a new C++ implementation of TS for Knapsack. Our motivation was to obtain it from a generic skeleton for Tabu Search method so we could provide different implementations of internal heuristics and an efficient fine tuning of parameters. Our contribution can be summarized as follows:

1. We propose a new way of intensifying and diversifying the search. While in existing implementations for the problem these methods are "forced" to be executed a certain number of times, our implementation invokes them when the search fails to improve the solution. We also introduce two ways of diversifying, namely the "soft" and "strong" diversification. The intensification is done by rewarding solutions while the soft diversification by penalizing them (both rewarding and penalizing use the history on the solutions); the strong diversification is roughly an escape mecanism. Also a new aspiration criteria is given which helps improving the quality of solutions.
2. Our implementation is obtained from a generic C++ skeleton for TS method (Blesa and Xhafa, 2000). This enables us with the possibility to provide new implementations for internal heuristics without changing the rest of the implementation. This is achived due to component reuse and other features of Object Oriented Programming. By now, we have done this for the neighborhood exploration method by implementing it in two different ways and have experimentally evidenced how the implementation of internal heuristics of TS impacts the success of the method.
3. Experimental results: We have tested our program with standard instances (small and medium size from [Freville, Plateau, 1990] and big size instances from OR-Library [Beasley, 1990]). For instances of small and medium size we have always found the optimum solution, except for KNAP50. For bigger size instances our fitness is very close to the best known fitness of other ad hoc implementations (for extensive experimental results of the two implementations metioned above see http://www.lsi.upc.es/~mjblesa/TSExperiments/knapsack.html , that is frequently updated).
4. We have also experimented to find good values for the TS parameters, such as number of intensifications, number of diversifications, the number of iterations an item remains tabu, number of best solutions so far, etc. This is quite desirable for TS implementations, for example this has been done for Quadratic Assignment Problem (see Hertz et al., 1997). The experimental results give evidence that our parameters conduct the search to good solutions. Current Work: We are currently parallelizing the sequential implementations in different ways so as to benefit from the use of network resources.

Keywords: Knapsack Problem, Tabu Search Method, Heuristics, Optimization

29-Mar-01:14:00:Pope C15
A Hyperheuristic Approach to the Summit Scheduling Problem
Soubeiga, Eric, Cowling Peter and Kendall Graham, University of Nottingham

The concept of a hyperheuristic is introduced as an approach that operates at a higher lever of abstraction than current metaheuristic approaches by heuristically managing the choice as to which of several lower-level solution methods should be applied, depending upon the characteristics of the region of the solution space currently under exploration. We analyze the behavior of several different hyperheuristic approaches for a real-world personnel scheduling problem. Results obtained show the effectiveness of our approach for this problem and suggest wider applicability of hyperheuristic approaches to other problems of scheduling and combinatorial optimization

Keywords: Hyperheuristics, Heuristics, Metaheuristics, Personnel Scheduling, Local Search, Choice Function

29-Mar-01:14:30:Pope C15
Multi Agent Systems for Dynamic Scheduling
Cowling, Peter, Ouelhadj, Djamila and Petrovic, S, School of Computer Sciences & IT, University of Nottingham

In most practical environments, scheduling is an ongoing reactive process where the presence of real time information continually forces reconsideration and revision of pre-established schedules. Scheduling research has largely ignored this problem, focusing instead on optimisation of static schedules. This paper outlines the limitations of static scheduling using OR techniques in the presence of real time information and gives a review of currently developing research on dynamic scheduling using a multi-agent approach. The advantages, potential and applications of this approach for dynamic scheduling are discussed.

Keywords: reactive scheduling, real-time information, multi-agent systems, intelligent agents