Abstract
Machine scheduling problems belong to the most difficult deterministic combinatorial optimization problems. Since most scheduling problems are NP-hard, it is impossible to find the optimal schedule in reasonable time. In this paper, we consider a flow-shop scheduling problem with multiprocessor tasks. A parallel genetic algorithm using multithreaded programming technique is developed to obtain a quick but good solution to the problem. The performance of the parallel genetic algorithm under various conditions and parameters are studied and presented.
Chapter PDF
Similar content being viewed by others
References
Blazewicz J., Drabowski M., Weglarz J.: Scheduling Multiprocessor Tasks to Minimize Schedule Length, IEEE Trans. Computers C-35/5 (1986) 389–393
Brucker P.: Scheduling Algorithms, Springer, Berlin (1995)
Cantoni V., Ferretti M.: Pyramidal Architectures for Computer Vision, Plennium Press, New York (1994)
Chen C.L., Vempati V.S., Aljaber N.: An Application of Genetic Algorithms for Flow Shop Problems, European Journal of Operational Research 80 (1995) 389–396
Chipperfield A., Fleming P.: Parallel Genetic Algorithms, In: Zomaya, A.Y. (ed.): Parallel and Distributed Computing Handbook, McGraw-Hill (1996)
Dorndorf U., Pesch E.: Evolution Based Learning in a Job Shop Scheduling Environment, Comp. Opns. Res. 22 (1995) 25–40
Drozdowski M.: Scheduling Multiprocessor Tasks-An Overview, European Journal of Operational Research 94 (1996) 215–230
Ercan M.F., Fung Y.F.: The Design and Evaluation of a Multiprocessor System for Computer Vision, Microprocessors and Microsystems 24 (2000) 365–377
Gupta J.N.D., Hariri A.M.A., Potts C.N.: Scheduling a Two-stage Hybrid Flow Shop with Parallel Machines at the First Stage, Ann. Oper. Res. 69 (1997) 171–191
Holland H.: Adaptation in Natural and Artificial Systems. Ann Arbor, The University of Michigan Press (1975)
Krawczyk H., Kubale M.: An Approximation Algorithm for Diagnostic Test Scheduling in Multicomputer Systems, IEEE Trans. Comput. 34/9 (1985) 869–872
Lloyd E.L.: Concurrent Task Systems. Opns Res. 29 (1981) 189–201
Murata T., Ishibuchi H., Tanaka H.: Genetic Algorithms for Flowshop Scheduling, Comp. Ind. Engng, 30 (1996) 1061–1071
Oguz C., Ercan M.F., Cheng T.C.E., Fung Y.F.: Multiprocessor Task Scheduling in Multi Layer Computer Systems, in print European Journal of Operations Research.
Reeves C.R.: A Genetic Algorithm for Flowshop Sequencing, Comp. Opns. Res. 22 (1995) 5–13
Scala M. L., Bose A., Tylavsky J., Chai J. S.: A Highly Parallel Method for Transient Stability Analysis, IEEE Trans. Power Systems 5 (1990) 1439–1446
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Oguz, C., Fung, YF., Ercan, M.F., Qi, X.T. (2003). Parallel Genetic Algorithm for a Flow-Shop Problem with Multiprocessor Tasks. In: Sloot, P.M.A., Abramson, D., Bogdanov, A.V., Gorbachev, Y.E., Dongarra, J.J., Zomaya, A.Y. (eds) Computational Science — ICCS 2003. ICCS 2003. Lecture Notes in Computer Science, vol 2659. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44863-2_54
Download citation
DOI: https://doi.org/10.1007/3-540-44863-2_54
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40196-4
Online ISBN: 978-3-540-44863-1
eBook Packages: Springer Book Archive