ارزیابی الگوریتم های زمانبندی تولید کارگاهی انعطاف پذیر و مقایسه آنها با الگوریتم ژنتیک دوبخشی

نویسندگان

دانشگاه سمنان

چکیده

در این مقاله مساله زمانبندی تولید کارگاهی انعطاف پذیر مورد بررسی قرار گرفته است، که بسط یافته مساله زمانبندی تولید کارگاهی می‌باشد. اهداف مساله کمینه کردن حداکثر زمان تکمیل آخرین سفارش(Cmax ) و ماکزیمم بارکاری ماشین (Wm) یعنی ماکزیمم بار کاری در هر ماشین و بارکاری کل (WT) بار کاری کل برای تمام ماشینها است. این مساله جز مسائل NP-hard می‌باشد، بنابراین بدست آوردن جواب بهینه در زمان معقول امکان پذیر نیست، به همین منظور یک الگوریتم ژنتیک پیشنهادی به نام الگوریتم ژنتیک دو بخشی برای حل مساله ارائه شده است. برای بررسی کارایی الگوریتم پیشنهادی از دو مجموعه داده محک استفاده شده است و با الگوریتم های مقاله های اخیر مورد مقایسه قرار گرفته است. نتایج محاسباتی نشان می‌دهد که الگوریتم ژنتیک دو بخشی کارایی موثر برای حل مساله زمانبندی تولید کارگاهی انعطاف پذیر را دارد.

کلیدواژه‌ها

عنوان مقاله [English]

Evaluating flexible job shop algorithms and comparison with 2 part genetic algorithm

نویسندگان [English]

  • Mohammad Ali Beheshtinia
  • niloofar ghazi
چکیده [English]

This paper consider flexible jobshop scheduling problem with minimizing maximum completion time of orders(Cmax), maximum workload of machines(Wmax) and total workloads (WT). The problem is known as Np-Hard. So finding the optimal solution in a reasonable time is impossible. A genetic algorithm named 2 part genetic algorithm is proposed for solving the problem. For evaluating the problem, we used 2 test data sets and proposed genetic algorithm is compared with other algorithms in the literature. Results show proposed genetic algorithm has higher performance for solving the problem in comparison with other algorithms.

کلیدواژه‌ها [English]

  • scheduling
  • Flexible job shop
  • Genetic algorithm
  • Choromosome
  • Sequencing

مراجع

 
[1] Pinedo, M.(2002)."Scheduling: Theory, Algorithms and Systems". Prentice-Hall, Englewood Cliffs, NJ.
[2]Roshanaei, V., Naderi, B., Jolai, F., Khalili, M. (2009). " A variable neighborhood search for job shop scheduling with set-up times to minimize makespan". Future Generation Computer Systems, Vol. 25, pp. 654-661.
[3] Ombuki, B., Ventresca, M.(2004)."Local search genetic algorithms for the job shop scheduling problem". Applied Intelligence, Vol. 21, pp. 99-109.
[4] Bagheri, A., Zandieh M., Mahdavi I., Yazdani M.(2010). "An artificial immune algorithm for the flexible job-shop scheduling problem". Future Generation Computer Systems, Vol. 26, pp. 533-541.
[5] Brucker, P., Schile, R. (1990). "Job-shop scheduling with multi-purpose machines". Computing, Vol. 45, pp.369–375.
[6] Kacem, I., Hammadi, S., Borne, P. (2002). "Pareto-optimality approach for flexible job-shop scheduling problems: Hybridization of evolutionary algorithms and fuzzy logic". Mathematics and Computers in Simulation, Vol. 60, pp. 245–276.
[7] Brandimarte, P.(1993). "Routing and scheduling in a flexible job shop by taboo search". Annals of operations Research, Vol. 41, pp. 157-183.
[8] Kacem, I., Hammadi, S., Borne, P.(2002). "Approach by localization and multi objective evolutionary optimization for flexible job-shop scheduling problems". IEEE Transactions on Systems, Man, and Cybernetics, Vol. 32, pp. 1-13.
[9] Xia, W., Wu, Z.(2005). "An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problem". Computers and Industrial Engineering, Vol. 48, pp. 409-425.
 [10] Chen, H., Ihlow, J., Lehmann, C.(1999). "A genetic algorithm for flexible Job-shop scheduling", IEEE International Conference on Robotics and Automation, Detroit,pp.1120-1125.
[11] Zhang,H., Gen, M. (2005). Multistage-based genetic algorithm for flexible job-shop scheduling problem, Journal of Complexity International, Vol. 11, 223-232.
[12] Ong, Z.X., Tay, J.C., Kwoh, C.K.(2005). "Applying the Clonal Selection Principle to Find Flexible Job-Shop Schedules", in: LNCS, Vol. 3627, pp. 442-455.
[13] Pezzella, F., Morganti, G., Ciaschetti, G.(2008). "A genetic algorithm for the flexible jobshop scheduling problem". Computers and Operations Research, Vol. 35 (10), pp. 3202-3212.
[14] Gao, J., Sun, L., Gen, M.(2008). "A hybrid genetic and variable neighborhood descent for flexible job shop scheduling problems", Computers and Operations Research, Vol. 35 (9), pp. 2892-2907.
[15] Fattahi, P., Saidi Mehrabad, M., Jolai, F.(2007). "Mathematical modeling and heuristic approaches to flexible job shop scheduling problems". Journal of Intelligent Manufacturing, Vol. 18 (3), pp. 331-342.
[16] Yuan, Y. , Xu, H. (2013). A hybrid harmony search algorithm for the flexible job shop scheduling problem. Applied Soft Computing,Volume 13, Issue 7, Pages 3259–3272.
[17] Yuan, Y. , Xu, H. (2013). An integrated search heuristic for large-scale flexible job shop scheduling problems. Computers & Operations Research, Volume 40, Issue 12, Pages 2864–2877.
[18] Wang, L., Wang, S., Xu, Y., Zhou, G., & Liu, M. (2012). A bi-population based estimation of distribution algorithm for the flexible job-shop scheduling problem. Computers & Industrial Engineering, 62(4), 917–926.
[19]Thammano, A., Phu-ang, A.(2013). A Hybrid Artificial Bee Colony Algorithm with Local Search for Flexible Job-Shop Scheduling Problem. Procedia Computer Science 20 ,Pages 96 – 101.
[20] Teekeng, W., Thammano,A. (2012). Modified Genetic Algorithm for Flexible Job-Shop Scheduling Problems. Procedia Computer Science 12,Pages 122 – 128.
[21] Ak, B., Koc, E.(2012). A guide for genetic algorithm based on parallel machine scheduling
and flexible job-shop scheduling. Procedia - Social and Behavioral Sciences 62, Pages 817 – 823.
[22] Zejko, W., Hejducki, Z., Uchro´nski, M., Wodecki,M.(2012). Solving the Flexible Job Shop Problem on Multi-GPU. Procedia Computer Science 9, Pages 2020 – 2023.
[23] Ho, N. B., Tay, J. C., Edmund, M., Lai, K. (2007). "An effective architecture for learning and evolving flexible job shop schedules". European Journal of Operational Research, Vol. 179, pp. 316–333.
[24] Mesghouni, K., Hammadi, S., Borne, P. (1997). "Evolution programs for job-shop scheduling". In Proceedings of the IEEE international conference on computational cybernetics and simulation ,Vol. 1, pp. 720–725.
[25] Shahryar, R., Hamid, R. T., Magdy, M. A. S. (2007). "A novel population initialization method for accelerating evolutionary algorithms". Computers and Mathematics with Application, Vol. 53, pp. 1605–1614.
 [26] Jia, H.Z., Nee, A.Y.C., Fuh, J.Y.H., Zhang, Y.F.(2003). "A modified genetic algorithm for distributed
scheduling problems". International Journal of Intelligent Manufacturing, Vol. 14, pp. 351-362.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
مدل سازی در مهندسی
دوره 13، شماره 40
فروردین 1394
صفحه 1-16

فایل ها

سابقه مقاله

  • تاریخ دریافت: 09 بهمن 1395
  • تاریخ بازنگری: 27 شهریور 1396
  • تاریخ پذیرش: 09 بهمن 1395

هم رسانی

ارجاع به این مقاله

آمار