Abstract
In the chapter, we consider the population learning algorithm (PLA2), earlier designed by the authors, and study how the interconnection topology and heterogeneity of the constituent modules influence its efficiency. PLA2 is a population- based approach which takes advantage of the features common to the social education system rather than to the evolutionary processes. The 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 chosen as the problem to cope with. 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. To eliminate time consuming optimal continuous resource allocation, an NP-hard problem ΘZ with continuous resource discretisation is introduced and sub-optimally solved by PLA2. The PLA2’s island design can be easily transferred to an agent system with cooperating agents.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
De Boer, P.-T., Kroese, D.P., Mannor, S., Rubinstein, R.Y.: A Tutorial on the Cross-Entropy Method. Annals of Operations Research 134(1), 19–67 (2005)
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 11(2), 163–182 (2003); Luptaćik, M., Wildburger, U.L. (eds.) Physika-Verlag, A Springer-Verlag Company, Heidelberg
Jędrzejowicz, J., Jędrzejowicz, P.: Population–Based Approach to Multiprocessor Task Scheduling in Multistage Hybrid Flowshops. In: Palade, V., Howlett, R.J., Jain, L. (eds.) KES 2003. LNCS (LNAI), vol. 2773, pp. 279–286. Springer, Heidelberg (2003)
Jędrzejowicz, J., Jędrzejowicz, P.: PLA–Based Permutation Scheduling. Foundations of Computing and Decision Sciences 28(3), 159–177 (2003)
Jędrzejowicz, J., Jędrzejowicz, P.: New Upper Bounds for the Permutation Flowshop Scheduling Problem. In: Ali, M., Esposito, F. (eds.) IEA/AIE 2005. LNCS (LNAI), vol. 3533, pp. 232–235. Springer, Heidelberg (2005)
Jędrzejowicz, P.: Social Learning Algorithm as a Tool for Solving Some Difficult Scheduling Problems. Foundation of Computing and Decision Sciences 24, 51–66 (1999)
Jędrzejowicz, P., Skakovski, A.: A Population Learning Algorithm for Discrete-Continuous Scheduling with Continuous Resource Discretisation. In: Chen, Y., Abraham, A. (eds.) 6th International Conference on Intelligent Systems Design and Applications, ISDA 2006 Special session: Nature Imitation Methods Theory and Practice (NIM 2006), October 16-18, vol. II, pp. 1153–1158. IEEE Computer Society, Jinan (2006)
Jędrzejowicz, P., Skakovski, A.: A Cross-Entropy Based Population Learning Algorithm for Discrete-Continuous Scheduling with Continuous Resource Discretisation. In: Lovrek, I., Howlett, R.J., Jain, L.C. (eds.) KES 2008, Part I. LNCS (LNAI), vol. 5177, pp. 82–89. Springer, Heidelberg (2008)
Józefowska, J., Węglarz, J.: On a methodology for discrete-continuous scheduling. European J. Oper. Res. 107(2), 338–353 (1998)
Józefowska, J., Mika, M., Różycki, R., Waligóra, G., Węglarz, J.: Solving discrete-continuous scheduling problems by Tabu Search. In: 4th Metaheuristics International Conference MIC 2001, Porto, Portugal, July 16-20, pp. 667–671 (2001)
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), 354–370 (1998)
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ń, Poland (2000)
Rubinstein, R.Y.: Optimization of computer simulation models with rare events. European Journal of Operations Research 99, 89–112 (1997)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Jędrzejowicz, P., Skakovski, A. (2013). Structure vs. Efficiency of the Cross-Entropy Based Population Learning Algorithm for Discrete-Continuous Scheduling with Continuous Resource Discretisation. In: Czarnowski, I., Jędrzejowicz, P., Kacprzyk, J. (eds) Agent-Based Optimization. Studies in Computational Intelligence, vol 456. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34097-0_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-34097-0_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-34096-3
Online ISBN: 978-3-642-34097-0
eBook Packages: EngineeringEngineering (R0)