مقایسه کارایی روش های "سیستم کلونی مورچگان" و "برنامه ریزی خطی" در مدل سازی مسأله زمان- بندی تولید جریانی

الموضوعات :

Said Esfandyari ¹ , Ali Morovati Sharif Abadi ² , Seyed Habibolah Mirghafouri ³ , Hamid Reza Kadkhodazadeh ⁴

1 - M.A in Management, Jahad Daneshgahi Higher Education Institute, Yazd Branch
2 - Assistant Professor, University of Yazd, Yazd, Iran
3 - Associate Professor, University of Yazd, Yazd, Iran
4 - M.A in Management, Jahad Daneshgahi Higher Education Institute, Yazd Branch

تاريخ الإرسال : 21 الإثنين , ربيع الثاني, 1439 تاريخ التأكيد : 21 الإثنين , ربيع الثاني, 1439 تاريخ الإصدار : 12 الأربعاء , رجب, 1434

الکلمات المفتاحية: linear programming, برنامه ریزی خطی, زمان بندی, تولید جریانی, الگوریتم سیستم مورچگان, Flow shop scheduling, Ant colony system algorithm,

ملخص المقالة :

هر چند که برنامه ریزی خطی در دنیای واقع کاربردهای زیادی دارد، اما در برخورد با مسائل پیچیده و سخت عدم کارایی خود را نشان داده است. با پیشرفت علم و رویارویی با مشکلات مختلف، تمایل به حل مسائل در حجم زیاد در زمان کوتاه بیشتر شده است. روش های ابتکاری و فوق ابتکاری جدیدترین دستاورد برنامه ریزی غیرخطی در حل این گونه مسائل هستند. یکی از حوزه هایی که نیاز به برنامه ریزی در حجم بالا دارد زمان بندی تولید در مسائل سخت می باشد. این مقاله به مدل سازی و مقایسه دو روش برنامه ریزی خطی و الگوریتم سیستم مورچگان در زمان بندی تولید جریانی منعطف با توجه به متغیرهای تعداد ماشین و سفارش پرداخته است؛ مبنای مقایسه در این پژوهش شاخص های زمان پردازش، تعداد محدودیت، بهینگی و حجم حافظه اشغال شده مربوط به اعداد تصادفی می باشد. در این مقاله از روش پژوهششبه آزمایشی استفاده شده است، ابزار آزمایش به ترتیب نرم افزارهای سی شارپ و لینگو برای الگوریتم مورچگان و برنامه ریزی خطی است. نتایج به دست آمده نشان می دهد که مدل برنامه ریزی خطی درتعداد ماشین و سفارش پایین کارایی بالاتری دارد، اما با افزایش ماشین و سفارش با توجه به شاخص های در نظر گرفته شده، الگوریتم سیستم مورچگان کارایی بالاتر خود را نشان می دهد.

المصادر:

1-   Artigues, C., & Gendreau M., & Rousseau, L.M., Vergnaud A. (2009). Solving an integrated employee timetabling and job-shop scheduling problem via hybrid branch-and-bound. Computers & Operations Research, 36(8), 2330 – 2340.

2-   Balseiro, S.R., & Loiseau, I., & Ramonet J. (2011). An Ant Colony algorithm hybridized with insertion heuristics for the Time Dependent Vehicle Routing Problem with Time Windows. Computers & Operations Research, 38(2), 954–966.

3-   Brucker, P. (2007). Scheduling Algorithms, 15(1), Heidelberg.

4-   Dannenbring, D. G. (1977). An evaluation of flowshop sequencing heuristics. Management Science, 23(11), 1174–1182.

5-   Dorigo, M., & Gambardella, L. M. (1997). Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transaction on Evolutionary Computation, 1(1), 53-63.

6-   Dorigo, M., & Di Caro, G. (1999). The ant colony optimization meta-heuristic. In D.Corne, M. Dorigo, & F. Glover (Eds.), New ideas in optimization .London, UK: McGraw-Hill, 11-32.

7-   Ebadi, A., Moslehi, G. (2011). Mathematical models for preemptive shop scheduling problems. Computers & Operations Research, 39(7), 1605-1614

8-   Gicquel, C. & Hege, L. & Minoux, M., & van Canneyt W. (2012). A discrete time exact solution approach for a complex hybrid flow-shop scheduling problem with limited-wait constraints. Computers & Operations Research, 39629–636.

9-   Gupta, J. N. D. (1971). An improved combinatorial algorithm for the flowshop scheduling problem. Operations Research, 19, 1753–1758.

10-    Huang, Y.M., & Lin J.C. (2010).  A new bee colony optimization algorithm with idle-time-based filtering scheme for open shop-scheduling problems. Expert Systems with Applications, 38(5), 5438-5447.

11-    Johnson, S. M. (1954). Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1(1), 61–68.

12-    Leung, C.W., & Wong T.N., & Mak K.L., & Fung R.Y.K. (2010). Integrated process planning and scheduling by an agent-based ant colony optimization. Computers & Industrial Engineering, 59(1), 166–180.

13-    Lin, H. T., & Lee, H. T., & Pan, W.J. (2008). Heuristics for scheduling in a no-wait open shop with movable dedicated machines. Int. J. Production Economics, 111, 368–377.

14-    Mehregan MR. (2002). Performance evaluation of organizations using quantitative data envelopment analysis. Tehran: Tehran University, 147-53.

15-    Mohamadi, A., & Jamalnia, A. (2007). Ant colony and its application in preventive maintainance. shahed university.

16-    Momeni, M. (2011). New topic in operation research. Tehran. Tehran University.

17-    Nasiri, F., & Ebrahimi, A. (2009). Evaluation of ant colony for solving defects and export overruns. Twenty- fourth international conferences on electricity. 

18-    Neto, T. & Filho, G. (2011). An Ant Colony Optimization approach to a permutational flow shop scheduling problem with outsourcing allowed. Computers & Operations Research, 38(9), 1-19.

19-    Onder Bozdogan, A., & Efe, M. (2011). Improved assignment with ant colony optimization for multi-target tracking. Expert Systems with Applications, 38(8), 9172-9178.

20-    Pinedo, M. (2005). Planning and Scheduling in Manufacturing and Services .Springer, 5(1), 10-17.

21-    Pinedo, M. (2009). Planning and Scheduling in Manufacturing and Services Second Edition. Springer, New York, Verlag.

22-    Santos, L., & Coutinho-Rodrigues, J. (2010) .Current J.R. An improved ant colony optimization based algorithm for the capacitated arc routing problem. Transportation Research Part, 44(4), 246–266.

23-    Schluter, M., & Egea, J.A., & Banga, J.R. (2009). Extended ant colony optimization for non-convex mixed integer nonlinear programming. Computers & Operations Research, 36(7), 2217 – 2229.

24-    Sepehri, M.M., & Rahimi moghadam, M. (2007). Ant colony and its application. farhang menhaj puplication.Tarbiyat modares university.

25-    Shil, H. Z., & XuG, J. (2004) .Ant Colony Optimization Algorithm with Random Perturbation behavior to the Problem of Optimal Unit Commitment with Probabilistic Spinning Reserve Determination. Elsevier Electric, Power Systems Research. 69, 295-303.

26-    Wang, Y., & Xie, J. (2000).Ant Colony Optimization for Multicast Routing. The 2000 IEEE Asian Pacific Conference on Circuits and Systems, IEEE Apcc as 2000, 54-57.

27-    Widmer, M., & Hertz, A. (1989). A new heuristic method for the flowshop sequencing problem. European Journal of Operational Research, 41(2), 186–193.

28-    Xiangyong Li, M.F., & Baki, Y.P. (2011). Flow shop scheduling to minimize the total completion time with a permanently present operator: Models and ant colony optimization metaheuristic. Computers & Operations Research 38(1), 152–164.

29-    Xing, L.N, & Chen, Y.W., & Wang, P. & Zhao, Q.S., & Xiong, J. A. (2010). Knowledge-Based Ant Colony Optimization for Flexible Job Shop Scheduling Problems. Applied Soft Computing, 10(3), 888–896.

30-    Yagmahan, B., & Mutlu, Y. M. (2010). A multi-objective ant colony system algorithm for flow shop scheduling problem. Expert Systems with Applications 37(2), 1361–1368.