1. Le problème
Un robot doit remettre, le plus vite possible, des caisses numérotées dans l'ordre. Elles sont alignées dans des casiers et le robot dispose de 4 charriots qui permettent de déplacer les caisses. Ces derniers sont répartis sur deux rails de part et d'autre de la rangée de casiers et ils exécutent une commande par unité de temps parmis celles-ci :
- se déplacer à droite (>),
- se déplacer à gauche (<),
- prendre ou poser une caisse (#).
Le but est, pour une configuration donnée, de trouver le programme le moiuns coûteux possible pour que les charriots remettent les caisses dans l'ordre.
Voici les coûts unitaire :
- cycle (chaque charriot peut recevoir un ordre par cycle) : 10,
- déplacement d'un charriot : 1,
- chargement/déchargement d'une caisse : 2.