Open Access Open Access  Restricted Access Subscription or Fee Access

An Evolutionary Approach for Job Scheduling in a Multiprocessor Architecture

K. Deeba, K. Thanushkodi

Abstract


This paper proposes a genetic algorithm optimization approach to solve job scheduling problems in a multiprocessor architecture. Job scheduling problem (JSP) is an extremely difficult hard problem because it requires a large combinatorial search space and also precedence constraints between the processes considered. Efficient assignment and scheduling of tasks is of high importance in the effective utilization of multiprocessor systems. With regard to this kind of JSP problem, a genetic algorithm based approach is utilized. In this approach, the chromosomes are encoded and the population size is devised for the optimized goal of scheduling problem. Then the fitness function is formulated. Next, utilizing the genetic algorithm operators to prevent the premature convergence, a best or satisfactory scheduling path can be determined. The execution results using the devised algorithms in certain multiprocessor architecture are given in the paper.


Keywords


Finishing time, Genetic Algorithm, Job scheduling problem, Multiprocessor Architecture, Waiting time

Full Text:

PDF

References


M. R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the theory of NP completeness, San Francisco, CA, W.H. Freeman, 1979.

L. Mitten, ‘Branch and Bound Method: general formulation and properties’, operational Research, 18, P.P. 24-34, 1970.

T.L.Adam , K.M. Chandy, and J.R. Dicson, “ A Comparison of List Schedules for Parallel Processing Systems”, Communication of the ACM, Vol.17,pp.685-690, December 1974.

C.Y. Lee, J.J. Hwang, Y. C. Chow, and F. D. Anger,” Multiprocessor Scheduling with Interprocessor Communication Delays,” Operations Research Letters, Vol. 7, No.3,pp.141-147, June 1998.

S.Selvakumar and C.S. R. Murthy, “ Scheduling Precedence Constrained Task Graphs with Non- Negligible Intertask Communication onto Multiprocessors,” IEEE Trans. On Parallel and Distributed Computing, Vol, 5.No.3, pp. 328-336, March 1994.

T. Yang and A. Gerasoulis, “ List Scheduling with and without Communication Delays,” Parallel Computing, 19, pp. 1321-1344, 1993.

J. Baxter and J.H. Patel, “ The LAST Algorithm: A Heuristic- Based Static Task Allocation Algorithm,” 1989 International Conference on parallel Processing, Vol.2, pp.217-222, 1989.

G.C. Sih and E.A. Lee, “ Scheduling to Account for Interprocessor Communication Within Interconnection- Constrained Processor Network,” 1990 International Conference on Parallel Processing, Vol.1, pp.9-17,1990.

M.Y. Wu and D. D. Gajski, “ Hypertool: A Programming Aid for Message_Passing Systems,” IEEE Trans on Parallel and Distributed Computing, Vol.1, No.3, pp.330-343, July 1990.

S.N.Sivanandam and S.N. Deepa, “Introduction to Genetic Algorithm”, Springer verlog , 2007.

D.E. Goldberg(1989), Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley.

Gur Mosheiov, Uri Yovel, “ Comments on “Flow shop and open shop scheduling with a critical machine and two operations per job”, European Journal of Operational Research(Elsevier), 2004.

Gur Mosheiov, Daniel Oron, “ Open- shop batch scheduling with identical jobs”, European Journal of Operational Research(Elsevier), 2006.

Zhou, M., Sun, S. d. “ Genetic algorithms: theory and application” National Defense Industry Press, Beijing, China, pp. 130-138., 1999.


Refbacks

  • There are currently no refbacks.