Niedarwinowska ewolucja w rozwiązywaniu problemu harmonogramowania

• Autorzy: Paweł B. Myszkowski
• Języki publikacji: PL

Abstrakty

Problem harmonogramowania był intensywnie badany i wiadomo, że jest NP- trudny, kombinatorycznie optymalizacyjny i wymaga spełnienia wielu ograniczeń. Do grupy problemów harmonogramowania zaliczane są problemy podziału pracy na wiele urządzeń (job-shop scheduling), układanie planów zajęć w szkole (timetable problem), ustalanie kolejności egzaminów na uczelni wyższej (examination timetabling), układanie planu zajęć na uczelni wyższej (university course timetabling problem, UCTP) oraz wiele innych. Dla potrzeb niniejszego artykułu pojęcie harmonogramowania ograniczone zostanie do UCTP i będzie jako takie rozpatrywane. Przy wyborze problemu kierowano się łatwością dostępu do danych oraz utylitarnym aspektem badań (przedstawione rozwiązanie docelowo przeznaczone jest do działania na rzeczywistych danych na Wydziale Informatyki i Zarządzania Politechniki Wrocławskiej). (fragment tekstu)

Słowa kluczowe

PL

Harmonogram; Algorytmy genetyczne

EN

Schedule; Genetic algorithms

• Czasopismo: Prace Naukowe Akademii Ekonomicznej we Wrocławiu
• Rocznik: 2003
• Numer: nr 975 Pozyskiwanie wiedzy i zarządzanie wiedzą
• Strony: 322--331

Twórcy

autor

Paweł B. Myszkowski

• Politechnika Wrocławska

Bibliografia

• Bierwirth C., Mattfeld D.C.: Production scheduling and rescheduling with genetic algorithms, Evolutionary Computation 7(1), 1999.
• Burke E.K., Elliman D.G., Weare R.: A University Timetabling System based on Graph Colouring and Constraint Manipulation, 1993.
• Burke E.K. Newall J., Weare R.: A Memetic Algorithm for University Exam Timetabling, 1996.
• Cichosz P.: Systemy uczące się. Warszawa: WNT 2000.
• Colorni A., Dorigo M., Maniezzo V.: Genetic algorithms: a new approach to the time-table problem. Lecture in Notes in Computer Science - NATO SI Series, Vol. F 82, Springer- Verlag, 1990.
• Colorni A., Dorigo M., Maniezzo V.: A genetic algorithm to solve the timetable problem. Computational optimization and applications journal, 1993.
• Colorni A., Dorigo M., Maniezzo V.: Metaheuristic for High-school timetabling. Computational optimization and applications journal, 1997.
• Goldberg D.E.: Algorytmy Genetyczne i ich zastosowania. Warszawa: WNT 1995.
• Kwaśnicka H., Myszkowski P.: Metody data mining w analizie giełdy. Ewolucja strategii. Materiały konferencji 'Pozyskiwanie Wiedzy z Baz Danych'. Karpacz 2002.
• Michalewicz Z.: Algorytmy genetyczne + struktury danych = programy ewolucyjne. Warszawa: WNT 1996.
• Michalski R.: Learning and Evolution: An Introduction to Non-Darwinian Evolutionary Computation. Invited paper, Twelfth International Symposium on Methodologies for Intelligent Systems, Charlotte, NC, 2000.
• Michalski R.: Learnable Evolution Model: Evolutionary Processes Guided by Machine Learning. Machine Learning, 38, 2000.
• Michalski R., Kaufman K.: Applying Learnable Evolution Model to Heat Exchanger Design. Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI-2000) and Twelfth Annual Conference on Innovative Applications of Artificial Intelligence (IAAI- 2000), Austin, TX, 2000.
• Michalski R., Cervone G., Kaufman K.: Speeding Up Evolution through Learning. LEM, Proceedings of the Ninth International Symposium on Intelligent Information Systems, Bystra, Poland, June 12-16 2000.
• Michalski R., Coletti M., Lash T., Mandsager C., Moustafa R.: An Experimental Application of Learnable Evolution Model and Genetic Algorithms to Parameter Estimation in Digital Signal Filters Design. Proceedings of the 1999 Genetic and Evolutionary Computation Conference (GECCO), Orlando, July, 1999.
• Norberciak M.: Przegląd metod automatycznego planowania - przykład wykorzystania algorytmu genetycznego w rozwiązywaniu prostego problemu planowania. "Prace Naukowe Zakładu Informatyki Politechniki Wrocławskiej", 2002.
• Ross P., Corne D., Fang H.L.: Successful lecture Timetabling with evolutionary algorithms. Workshop Notes, ECAI'94 Workshop, 1994.
• Rossi-Doria O., Blum C., Knowles J., Sampels M., Socha K., Paechter B.: A local search for the timetabling problem, 2002.
• Socha K., Sampels M., Manfrin M.: Ant Algorithms for the University Course Timetabling Problem with Regard to the State-of-the-Art, 2002.