S. Grolimund, J.-G. Ganascia Case-Based Reasoning and Tabu Search for the Single Machine Scheduling Problem: first Results L'optimisation combinatoire se distingue de la résolution de problèmes de par la nature des buts qu'elle poursuit. La diffi­ culté qu'il y a à résoudre les problèmes d'optimisation combina­ toire engendre une méfiance à l'égard des connaissances qui peu­ vent être apprises durant l'optimisation. I)e ce point de vue, les techniques d'apprentissage analytique classiques ne sont guère adaptées à la résolution de problèmes d'optimisation, alors qu'en revanche, les méthodes issues de la recherche opérationnelle s'y pretent. Cesdernieres n'intègrent cependant pas de techniques symboliques d'apprentissage. Nous proposons une approche, intégrée dans la méthode Tabou, permettant l'apprentissage de connaissances de contrôle dans des problèmes d'optimisation en cours de résolution. Une technique d'apprentissage à partir de cas acquiert et réutilise des con­ naissances de contrôle à l'intérieur de la même instance de problèmes. L'approche, appelée ALOIS, ne transfert pas de con­ naissance d'une optimisation à l'autre. En outre, elle est indépendante du domaine grâce à l'utilisation d'un système à base de règles pour l'exploration de l'espace de recherche. Nous il­ lustrons et commentons l'application d'ALOIS à un problème d'ordormancement de base. Combinatorial optimisation differs from general problem solving in the nature of goals to be achieved. The difficulty of achiev­ ing optimisation goals leads to a general lack of confidence con­ cerning 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 com­ binatorial 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 at­ tempt 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.