Dans ce TP, vous allez choisir et implémenter des recherches itératives avancées pour le problème SMTWTP.
Contrairement à ce qu'on a fait jusqu'à présent, vous allez vous organiser en binôme. Chaque binôme devra implémenter (au moins) deux versions de recherche itérative, e.g., ILS et Tabu Search. Autrement dit, chaque membre du binôme devra implémenter (au moins) un algorithme avancé.
En prenant inspiration des articles suivants choisir et implémenter une recherche itérative avancée pour le SMTWTP. ATTENTION : Vous n'êtes pas tenus de refaire les mêmes algorithmes cités ci-dessus, mais plutôt de s'en inspirer (par exemple en considérant d'autres types de voisinages) et pourquoi pas de les améliorer en utilisant les différents principes vus en cours.
ILS
Design of Iterated Local Search: An Example Application to the Single Machine Total Weighted Tardiness Problem. Matthijs den Besten, Thomas Stutzle, and Marco Dorigo. Applications of Evolutionary Computing, Volume 2037, pp. 441–452, 2001
An Iterated Dynasearch Algorithm for the Single-Machine Total Weighted Tardiness Scheduling Problem. Richard K. Congram, Chris N. Potts and Steven van de Velde. INFORMS Journal on Computing, 14(1):52–67, 2002
TS
A Tabu Search Algorithm for the Single-Machine Total Weighted Tardiness Scheduling Problem. U. Bilge, M. Kurtula, and F. Kirac. European Journal of Operational Research, 176:1423–1435, 2007
VND/VNS
On Heuristic Search for the Single Machine Total Weighted Tardiness Scheduling Problem -- Some Theoretical Insights and their Empirical Verification. Martin J. Geiger. European Journal of Operational Research, 207:1235–1243, 2010
Effectuer les mêmes tests (déviation et nombre d'évaluations) pour évaluer les performances de vos algorithmes et les comparer. Remarque : En particulier, lorsque vos algorithmes ont des conditions d'arrêts différentes, et pour être juste lors de la comparaison, vous pouvez en plus comparer leurs performances à nombre d'évaluations égales ou en fixant un nombre d'évaluation (par exemple, le nombre d'évaluation maximum observé avec votre VND). Vous pouvez aussi faire varier le nombre d'évaluations et tracer l'évolution de la fitness de la solution trouvée par chaque algorithme au cours des différentes itérations. Ceci vous permet par exemple d'avoir une idée sur la vitesse de convergence de vos recherche au cours du temps.
Testez vos algorithmes sur les grandes instances données dans le premier atelier.