An Improved Adaptive Genetic Algorithm for Job Scheduling Problem on Parallel Robots

Majlesi Journal of Electrical Engineering

مقاله 7، دوره 3، شماره 3، خرداد 2009، صفحه 63-70   

نوع مقاله: Review Article

شناسه دیجیتال (DOI): 10.1234/mjee.v3i3.105

نویسندگان

Gohar Vahdati^* ؛ Maryam Habibipour؛ Saeed Tousizadeh؛ Mahdi Yaghoubi

چکیده

Minimizing mean tardiness  by Job scheduling on parallel robots is very important in the scheduling domain. In this problem, there is a series of n-number independent jobs which are ready to be scheduled at the time of zero. Corresponding to each work, the processing time and duration date are determined. The aim of this approach is to find the order of jobs on the robots for minimizing the mean tardiness. This problem is in the class of NP-Hard combinational problems. Genetic algorithm is well known an effective tool for solving combinational optimization problems. In this study, an adaptive nonlinear genetic algorithm as well as two heuristic crossover and mutation operators are used. In the algorithm, there is a fitness function based on the mean tardiness. Therefore, the algorithm which can make the crossover and mutation probability adjusted adaptively and nonlinearly can avoid disadvantage such as premature convergence, low convergence speed and low stability. Experimental results demonstrate that the proposed genetic algorithm does not get stuck at a local optimum easily and yet it converges fast and is simple to implement.

کلیدواژه‌ها

Parallel Robots Scheduling؛ en؛ Genetic Algorithm؛ Mean Tardiness

مراجع

[1] Cakar, T., Koker, R., Demir, H.I., Parallel robot scheduling to minimize mean tardiness with precedence constraints using a genetic algorithm, Elsevier, Advances in Engineering Software, pp.47–54, 2008.

[2] Jun, S.Z., Ying, Z.J., A genetic algorithm based approach to intelligent optimization for scheduling dual resources with robots, Robot , pp.342-357, 2002.

[3] Kellegoz, T., Toklu, B., Wilson, J., Comparing efficiencies of genetic crossover operators for one machine total weighted tardiness problem, Elsesier, Applied Mathematics and Computation, pp.590–598, 2008.

[4] Yingjie, X., Zhentong, C., Jing Sun, An Improved Adaptive Genetic Algorithm for Job-Shop Scheduling Problem ,IEEE Third International Conference on Natural Computation , 2007.

[5] .Biskup, D.H.J., Gupta, J.N.D, Scheduling identical parallel machines to minimize totaltardiness, Elsevier, Production Economics, pp.134– 142, 2008.

[6] Koulamas, C., Decomposition and hybris simulated annealing heuristics for the parallel machine total tardiness problem, Nav Res Log , pp.109-125, 1997.

[7] Kim, K.H., Kim, D.W., Unrelated parallel machine scheduling with setup times using simulated annealing, Robot Comput Integr Manuf, pp.223-231, 2002.

[8] Armentano, V.A., Yamashita, D.S., Tabu search for scheduling on identical parallel machines to minimize mean tardiness, J Intell Manuf , pp.453-460, 2000.

[9] Azizog˘lu, M.,Kirca, O., Tardiness minimization on parallel machines, Int J Prod Econ , pp.163-168, 1998.

[10] OR-Library http://people.brunel.ac.uk/~mastjjb/jeb/info.html