A Cross - Entropy Based Population Learning Algorithm for Discrete-Continuous Scheduling with Continuous Resource Discretisation

• Autorzy: Jędrzejowicz P. , Skakovski A.

Warianty tytułu

PL

Algorytm uczenia populacji z wykorzystaniem entropii skrośnej do rozwiązywania dyskretno-ciągłych problemów szeregowania z dyskretyzacją zasobu ciągłego

• Języki publikacji: EN

Abstrakty

EN

A problem of scheduling nonpreemtable tasks on parallel identical machines under constraint on discrete resource and requiring, additionally, renewable continuous resource to minimize the schedule length is considered in the paper. A continuous resource is divisible continuously and is allocated to tasks from given intervals in amounts unknown in advance. Task processing rate depends on the allocated amount of the continuous resource. The considered problem can be solved in two steps. The first step involves generating all possible task schedules and second - finding an optimal schedule among all schedules with optimal continuous resource allocation. To eliminate time consuming optimal continuous resource allocation, a problem Teta Z with continuous resource discretisation is introduced. Because Teta Z is NP-hard a population-learning algorithm (PLA2) is proposed to tackle the problem. PLA2 belongs to the class of the population-based methods. Experiment results proved that PLA2 excels known algorithms for solving the considered problem.

PL

W pracy został rozpatrzony problem dyskretno-ciągłego szeregowania niepodzielnych zadań na równoległych identycznych maszynach, mającego na celu minimalizację długości uszeregowania z ograniczeniami nałożonymi na zasób dyskretny i dodatkowy odnawialny zasób ciągły. Zasób ciągły, podzielny w sposób ciągły, jest przydzielany do zadań z określonych przedziałów w ilościach z góry nieznanych. Szybkość wykonania zadań zależy od przydzielonej ilości zasobu ciągłego. Rozpatrywany problem można rozwiązać dwuetapowo. W pierwszym etapie należy wygenerować wszystkie możliwe uszeregowania zadań na procesorach. Drugi etap polega na znalezieniu optymalnego uszeregowania wśród wszystkich uszeregowań z optymalnym przydziałem zasobu ciągłego. W celu wyeliminowania czasochłonnej procedury optymalnego przydziału zasobu ciągłego, rozpatrzony został problem Teta Z z dyskretyzacją zasobu ciągłego. Ponieważ Teta Z jest problemem obliczeniowo NP-trudnym, do rozwiązywania został zaproponowany algorytm uczenia populacji PLA2 należący do klasy algorytmów opartych na ewolucji populacji. Eksperymenty obliczeniowe udowodniły, że PLA2 znajduje lepsze rozwiązania niż inne znane algorytmy przeznaczone do rozwiązywania dyskretno-ciągłych problemów szeregowania.

Słowa kluczowe

EN

algorithms; PLA2

PL

algorytmy; PLA2

• Wydawca: Wydawnictwo Uniwersytetu Morskiego w Gdyni
• Czasopismo: Prace Wydziału Nawigacyjnego Akademii Morskiej w Gdyni
• Rocznik: 2008
• Tom: Z. 22
• Strony: 45--52
• Opis fizyczny: Bibliogr. 17 poz., tab.

Twórcy

autor

Jędrzejowicz P.

autor

Skakovski A.

• Gdynia Maritime University Department of Information Systems

Bibliografia

• 1. Alba E., Troya J., Analysis of Synchronous and Asynchronous Parallel Distributed Genetic Algorithms with Structured and Panmictic Islands, [In:] Jose Rolim et al., Eds., Proceedings of the 10th Symposium on Parallel and Distributed Processing, San Juan, Puerto Rico, 12-16 April 1999, USA.
• 2. Belding T.C., The Distributed Genetic Algorithm Revisited, [In:] Eshelman L.J. (ed.), Proceedings of the Sixth International Conference on Genetic Algorithms, Morgan Kaufmann, San Francisco, CA, 1995.
• 3. De Boer P.T., Kroese D.P., Mannor S., Rubinstein R.Y., A Tutorial on the Cross- -Entropy Method. Annals of Operations Research, Vol. 134(1), 2005.
• 4. Czarnowski I., Gutjahr W.J., Jędrzejowicz P., Ratajczak E., Skakovski A., Wierzbowska I., Scheduling Multiprocessor Tasks in Presence of Correlated Failures, Central European Journal of Operations Research, Vol. 11, issue 2, Luptaćik M., Wildburger UL (ed.), Physika-Verlag, A Springer-Verlag Company, Heidelberg 2003.
• 5. Glover F., Tabu search: a tutorial, Interfaces, 20, 1990.
• 6. Gordon V.S., Whitley D., Serial and Parallel Genetic Algorithms as Function Optimizers, Proceedings of the Fifth International Conference on Genetic Algorithms, Morgan Kaufmann, Forrest S. (ed.), San Mateo, CA, 1993.
• 7. Jędrzejowicz J., Jędrzejowicz P., Population–Based Approach to Multiprocessor Task Scheduling in Multistage Hybrid Flowshops Knowledge-Based Intelligent Information and Engineering Systems, [In:] Palade V., Howlett R.J., Jain L. (eds), Lecture Notes in Artificial Intelligence, Springer, Berlin, 2773, 2003.
• 8. Jędrzejowicz J., Jędrzejowicz P., PLA–Based Permutation Scheduling, Foundations of Computing and Decision Sciences, Vol. 28, 3, 2003.
• 9. Jędrzejowicz J., Jędrzejowicz P., New Upper Bounds for the Permutation Flowshop Scheduling Problem. Innovations In Applied Artificial Intelligence, [In:] Moonis A., Esposito F. (eds), Lecture Notes in Artificial Intelligence, Springer, 3533, 2005.
• 10. Jędrzejowicz P., Social Learning Algorithm as a Tool for Solving Some Difficult Scheduling Problems, Foundation of Computing and Decision Sciences, 24, 1999.
• 11. Jędrzejowicz P., Skakovski A., A Population Learning Algorithm for Discrete- -Continuous Scheduling with Continuous Resource Discretisation, Proceedings of the Sixth International Conference on Intelligent Systems Design and Applications, Yuen Chen, Ajith Abraham (eds) ISDA 2006, Special session: Nature Imitation Methods Theory and practice (NIM’06), IEEE Computer Society, Vol. II, Jinan, China 16-18 October, 2005.
• 12. Jędrzejowicz P., Czarnowski I., Skakovski A., Szreder H., Evolution-based scheduling of multiple variant and multiple processor programs, [In:] Hertzberger L.O., Sloot PMA (eds), Future Generation Computer Systems, 17 Elsevier, Netherlands, 2001.
• 13. Józefowska J., Węglarz J., On a methodology for discrete-continuous scheduling, European J. Oper. Res., 107, 2, 1998.
• 14. Józefowska J., Mika M., Różycki R., Waligóra G., Węglarz J., Solving discrete- -continuous scheduling problems by Tabu Search, Proceedings of the 4th Metaheuristics International Conference MIC’2001, Porto, Portugal, 16-20 July, 2001.
• 15. Józefowska J., Różycki R., Waligóra G., Węglarz J., Local search metaheuristics for some discrete-continuous scheduling problems, European J. Oper. Res., 107, 2, 1998.
• 16. Różycki R., Zastosowanie algorytmu genetycznego do rozwiązywania dyskretno-ciągłych problemów szeregowania, PhD dissertation, Istitute of Computing Science, Poznań University of Technology, Piotrowo 3A, 60-965, Poznań 2000.
• 17. Rubinstein R.Y., Optimization of computer simulation models with rare events, European Journal of Operations Research, 99, 1997.