Rozwiązanie problemu m zadań - n maszyn metodą CLP oraz metodą genetyczną

Zostały zaprezentowane dwie różne metody rozwiązywania klasycznego problemu m zadań n maszyn. Pierwsza bazuje na programowaniu w logice z ograniczeniami (Constraint Logic Programming) i została zaimplementowana w językach CHIP v.5.2 i CHIP 4. Druga metoda, bazująca na dostosowanym do zagadnienia algorytmie genetycznym, została napisana w języku C++. Obydwie metody były testowane za pomocą sławnego benchmarku MT10 napisanego przez Mutha i Thompsona. W celu zwiększenia efektywności algorytmu w języku CHIP zostało zastosowanych wiele heurystyk. Najważniejsze polegały na zmianie metody ukonkretniania zmiennych, zmianie metody wyboru wartości z domeny i na losowaniu kolejności ukonkretniania zmiennych. Pierwsze dwie heurystyki przyczyniły się do przyspieszenia obliczeń, jednak uzyskiwane wyniki były jeszcze dalekie od rozwiązania optymalnego. Trzecia heurystyka, losująca kolejność zmiennych, poprawiła wynik, jedna po znacznie dłuższych obliczeniach. Po wprowadzeniu dodatkowej heurystyki, bazującej na wcześniejszych wynikach, udało się osiągnąć wynik 938 w zadawalającym czasie, 937 po dłuższych obliczeniach. Optymalny wynik to 930. Zmodyfikowany algorytm genetyczny zbudowany jest w oparciu o chromosom w postaci permutacji z powtórzeniami, a nie w postaci binarnej. Chromosom taki opisany został w artykule Genetic algorithms in engineering systems, którego autorami są A.M.S. Zalzala and P. J. Fleming. W algorytmie tym chromosom jest pozostawiony przy życiu, jeśli należy do ograniczonej grupy najlepszych chromosomów. Mutacja nie jest wywoływana losowo, lecz w sytuacji, gdy występują dwa lub więcej chromosomy z takim samym wynikiem. Operacja krzyżowania jest wykonywana dla każdej pary różnych chromosomów. Program taki pozwolił na uzyskanie wyniku 934.