Planification sous contrainte de ressources : Une approche de marche aléatoire de Monte Carlo

La nécessité d'économiser des ressources limitées, comme le carburant ou l'argent, est une caractéristique omniprésente des problèmes de planification. Si les ressources ne peuvent être renouvelées, le planificateur doit se contenter de l'approvisionnement initial. Il est alors d'une importance capitale de savoir dans quelle mesure le problème est contraint, c'est-à-dire si et dans quelle mesure l'approvisionnement initial en ressources dépasse le besoin minimum. Bien qu'il existe un grand nombre d'ouvrages sur la planification numérique et la planification avec des ressources, cette contrainte sur les ressources n'a été que très peu étudiée. Nous commençons ici à aborder ce sujet de manière plus détaillée. Nous généralisons la notion précédente de contrainte de ressources, caractérisée par une caractéristique numérique du problème C≥1, au cas de ressources multiples. Nous implémentons une suite étendue de benchmarks contrôlant C. Nous menons une étude à grande échelle de l'état actuel de l'art en fonction de C, mettant en évidence les techniques qui contribuent au succès. Nous introduisons deux nouvelles techniques en plus d'une méthode récente de marche aléatoire de Monte Carlo, résultant en un planificateur qui, dans ces benchmarks, surpasse les planificateurs précédents lorsque les ressources sont rares(C proche de 1). Nous étudions les paramètres qui influencent les performances de ce planificateur, et nous montrons que l'une des deux nouvelles techniques fonctionne bien également sur les benchmarks IPC habituels.