Abstract

In the search for better optimisation techniques, new methods that mix artificial intelligence and operations research have emerged. Search heuristics are integrated with optimisation algorithms. Approximation methods, like Hill Climbing, Simulated Annealing, and Tabu Search, that have been used with success in combinatorial optimization problems, are one of such research lines. This paper presents the key elements of approximation methods and combines them in a tool appropriate for solving sequencing and resource allocation problems. The system permits a clear division between problem specification and problem solving, allowing a declarative representation and therefore minimizing developing costs. The key issues discussed in this work are a model for representing this class of problems in a standard form, a set of strategies for applying the approximation methodology, and an expert system that dynamically manipulates the strategies’ parameters.
Keywords: artificial intelligence; heuristics; knowledge-based systems; optimisation

Publicado en Journal of the Operational Research Society (1998) Vol. 49, pp. 52-65. Documento completo Aquí.

Autores: M. Nussbaum, M. Sepúlveda, M. Singer, Ernesto Laval

Introduction

Sequencing problems are those in which it is necessary to determine the order in which a set of activities (jobs) is processed on a set of devices (machines). Resource allocation problems1 are those in which a set of scarce resources has to be assigned to fulfill a set of tasks. In both classes of problems there is a set of restrictions that define the feasible search space that has to be satisfied, minimising the resources’ cost and maximising the tasks’ benefit. These problems are of combinatorial nature making them extremely difficult to solve when the size of the problem grows. Therefore, practical problems cannot be confronted by human experts, not even with traditional optimization methods. The feasible solutions of a combinatorial problem, namely the different ways in which resources can be allocated in the defined problem, configure a search space that is finite, or infinite but innumerable. Even when the feasible solutions are finite, their number can grow exponentially in relation to the size of the problem.