Rapport de Recherche Laforia /
Laforia research reports
16 pages - Janvier/January 1996 - Document en anglais.
PostScript : 53 Ko /Kb
Titre / Title: Case-Based Reasoning and Tabu Search for the Single Machine Scheduling Problem: first Results
Abstract : Combinatorial optimisation differs from general problem solving in the nature of goals to be achieved. The difficulty of achieving optimisation goals leads to a general lack of confidence concerning the knowledge that can be learned during optimisation. We point out that this makes analytical learning techniques, like EBL or derivational analogy, inappropriate to the resolution of optimisation problems. Operations research methods cope with combinatorial optimisation, however without using symbolic learning.
Integrated in the Tabu search framework, we propose a system that learns control knowledge in optimisation domains while the resolution is in progress. A casebased learning technique is used to store and reuse control knowledge within the same instance of an optimisation problem. The approach, called ALOIS, does not attempt to transfer the acquired case library to any otha instance of the same problem. ALOIS is designed to be domainindependert, using a general rulebased reasoner to explore the solution space. Its application to the single machine scheduling problem with variable setup times is illustrated and discussed.
Publications internes Laforia 1995 / Laforia research reports 1995