Open Access Open Access  Restricted Access Subscription or Fee Access

A Parallel Implementation to Schedule A Video Sequence by A Parallel Genetic Evolution Algorithm Approach

S. V. Sudha, K. Thanushkodi


The problem of scheduling a set of dependent or independent tasks to be processed in a parallel fashion is one of the most challenging problems in parallel computing. The goal of a scheduler is to assign tasks to available processors such that precedence requirements between tasks are satisfied and the overall length of time required to execute the entire program, the schedule length or make span is minimized. A Parallel Genetic Algorithm Approach has been developed to the problem of task scheduling. GA is competitive in terms of solution quality if it has sufficient resources to perform its search. The Job taken for the Scheduling is the Detection of a Moving Object in a Video Sequence. The Moving Object Segmentation is suitable for real time content-based multimedia communication systems. First a background registration technique is used toconstruct as reliable background image from the accumulated frame difference information. The moving object region is then separated from the background region by comparing the current frame with the constructed background image. The implementation is optimized using parallel processing and achieved on a personal computer with a 3. 0 GHZ Pentium IV Processor. Good segmentation performance is demonstrated by the simulation results.


Background Registration, Moving Object Segmentation, Genetic Algorithm, Parallel Genetic Algorithm, fitness function.

Full Text:



Sikaro, ”The MPEG –4 Video Standard Verification Model, ” IEEE Trans Circuits Syst. Video Technol. Vol 7, pp 19-31, Feb 1997.

F. Nack and A. T. Lindsay, ” Everything you want to know about MPEG –7: part-2, ” IEEE Multimedia, Vol. 6, pp 64- 73, Dec 1999.

P. Salembier and F. Marques, ” Region – based representation of image and video: segmentation tools for multimedia services, IEEE Trans Circuits Syst, Video Technol, Vol 9, pp 1147-1169, Dec 1999.

Edwin. S. H. Hou, Nirwan Ansari, Hong Ren, ” A Genetic Algorithm for Multiprocessor Scheduling “, IEEE Transactions on Parallel and Distributed Systems, Vol 5 no 2, Feb 1994

J . Holland, Adaptation in Natural and Artificial Systems, Aann Arbor, MI: University of Michigan Press, 1975.

T. Aach, A. Kaup and R. Mester, ”Statistical model- based change detection in moving video, ”Signal Processing, Vol 31, pp 165-180, Mar 1993.

Annie s. Wu, Han Yu, Shiyuan Jin, Kuo-Chi Lin and Guy schiavone, ” An incremental Genetic Algorithm Approach to Multiprocessor Scheduling “, IEEE Transactions on parallel and Sep 2004.

Benjamin S. Macey and Albert Y. Zomaya, ” APerformance Evaluation of CP List Scheduling Heuristics for communication Intensive Task Graphs “, Parallel Computing Research Laboratory.

Mau –Tsuen Yang, Rangachar Kasturi and Anand Sivasubramaniam, ”A Pipeline Based Approach For Scheduling Video Processing Algorithm on NOW, ” IEEE Transactions on parallel and distributed System s, Vol 14,no 2 Feb 2003.

GOLDBERG D. E., Genetic algorithms in search, optimization, and machine learning. Addison-Wesley, Reading, MA, 1989.

M Nowostawski, R Poli, Parallel Genetic Algorithm Taxonomy, - 3rd International Conference on Knowledge- Based Intelligent Information Engineering Systems 1999.

AJ Page, TJ Naughton Dynamic task scheduling using genetic algorithms for heterogeneous distributed computing, - Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS’05).

M Golub, S Kasapovic Scheduling Multiprocessor Tasks with Genetic Algorithms, - Applied Informatics- Proceedings- 2002.

Tao Yang and Apostolos Gerasoulis, “DSC: Scheduling Parallel Tasks on an Unbounded Number of Processors”, IEEE Transactions on Parallel and Distributed Systems, Vol. 5, No. 9, pp. 951-967, Sep. 1994.

M. Maheswaran, S. Ali, H. J. Siegel, D. Hensgen, and R. F. Freund. Dynamic mapping of a class of independent tasks onto heterogeneous computing systems. Journal of Parallel and Distributed Computing, 59(2): 107–131, November 1999.

Y. Zomaya, M. Clements, and S. Olariu. A framework for reinforcement-based scheduling in parallel processor systems. IEEE Transactions on Parallel and Distributed Systems, 9(3): 249–260, March 1998.

E. Hou, N. Ansari, and H. Ren. A genetic algorithm for multiprocessor scheduling. IEEE Transactions on Parallel and Distributed Systems, 5(2): 113–120, February 1994.

Y. Zomaya and Y. -H. Teh. Observations on using genetic algorithms for dynamic load-balancing. IEEE Transactions on Parallel and Distributed Systems, 12(9): 899–911, September 2001.

Ahmad, Y. -K. Kwok, I. Ahmad, and M. Dhodhi. Scheduling parallel programs using genetic algorithms. In A. Y. Zomaya, F. Ercal, and S. Olariu, editors, Solutions to Parallel and Distributed Computing Problems, chapter 9, pages 231–254. John Wiley and Sons, New York,USA, 2001.

Y. Zomaya, C. Ward, and B. Macey. Genetic scheduling for parallel processor systems: comparative studies and performance issues. IEEE Transactions on Parallel and Distributed Systems, 10(8): 795–812, August 1999.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.