طراحی مدل ریاضی چندهدفه زمان‌بندی در سیستم تولیدی کارگاهی و حل آن با استفاده از روش فراابتکاری شبیه سازی تبریدی

نوع مقاله : مقاله پژوهشی

نویسندگان

1 کارشناس ارشد، دانشگاه تربیت مدرس.

2 استاد، دانشگاه تربیت مدرس.

3 دکتری، دانشگاه تربیت مدرس.

چکیده

سیستم تولید «کارگاهی» سیستمی مناسب برای تولید قطعات است و زمان­بندی «کارگاهی» یکی از مؤثرترین شاخص‌های افزایش بهره‌وری این سیستم­‌ها است. در حل مدل‌­های ریاضی زمانبندی کارگاهی دو هدف، کمینه‌­کردن بیش­ترین زمان ساخت و کمینه­‌کردن جمع وزنی جریمه‌های زودکرد و دیرکرد کارها (WSET) مدنظر قرار می‌­گیرد. در این پژوهش مدل ریاضی جدیدی برای رسیدن به هر دو هدف اشاره­‌شده به­طور هم­زمان از طریق برنامه­‌ریزی آرمانی (GP) ارائه شده است. مسائل زمان­بندی سیستم‌­های تولید کارگاهی از نظر پیچیدگی محاسباتی جز مسائل «حل‌­نشدنی چند جمله‌­ای سخت» قرار می­گیرند، بنابراین در این مقاله از روش فراابتکاری شبیه­‌سازی تبریدی برای حل مدل استفاده شده است. به طور معمول در روش‌­های فراابتکاری از ساختار جواب تک­ارائه‌ای (خانواده قطعات یا قطعات هر خانواده) استفاده می­‌شود که باعث کوچک­ترشدن فضای جواب می‌­شود؛ اما در این پژوهش برای  تعیین ساختار جواب دو­ارائه‌ای از روش تولید همسایگی ترکیبی، جابه­‌جایی جهت­دار (DIS) در خانواده قطعات و جابه­‌جایی تصادفی (RIS) در قطعات هر خانواده، استفاده شده است. نتایج حل مدل آرمانی زمان­بندی کارگاهی با روش شبیه‌­سازی تبریدی، کارایی مدل طراحی شده در دست­یابی به آرمان‌­های مورد نظر را نشان می‌­دهد.

کلیدواژه‌ها

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

Designing a Multi Objective Job Shop Scheduling Model and Solving it by Simulated Annealing

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

  • Hassan Rahimi 1
  • Adel Azar 2
  • Abbas Rezaei Pandari 3
1 MS, Tarbiat Modares University.
2 Professor, Tarbiat Modares University.
3 Ph.D., Tarbiat Modares University.
چکیده [English]

Jobshop manufacturing system is a suitable system for economical manufacturing of parts family and Jobshop scheduling is completely efficient in successfully running in improvement of productivity of system. The jobshop scheduling model has multiple objectives: Minimizing makes pan (Cmax) and Minimizing the Weighted Sum of Earliness and Tardiness penalties (WSET). In this study to achieve these objectives at the same time, Goal Programming (GP) has being used. This model from as computational point of view is NP-Hard, so in this paper we apply the Simulated Annealing (SA) meta-heuristic approach for solve it. One array structure of solution (family parts or parts in family) is used in common methods that lead to decrease of solution space, but in this study hybrid selection of neighborhood structures has been used for determaine the structure of solution; Directed Interchange Scheme (DIS) and Random Interchange Scheme (RIS). The results of research indicate solving goal programming model of Job shop Scheduling by SA is efficient to achieve goals of model.

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

  • Job Shop Scheduling
  • Simulated Annealing
  • Goal Programming
  • Hybrid Selection of Neighborhood

مراجع

1. Abdi, K. M., Abbasi, B. & Dolat Abadi A. (2010). A Simulated Annealing Algorithm for Multi Objective Flexible Job Shop Scheduling With Overlapping In Operations.Journal of Industrial Engineering, 5, 17-28.
2. Ali, M. M., Torn, A. & Viitanen, S. (2002).A direct search Variant of the simulated annealing algorithm for optimization involving continuous variables. Computer and Operations Research, 29, 87-102
3. Bagheri, A., & Zandieh, M., Mahdavi, I., Yazdani, M. (2010). An artificial immune algorithm for the flexible job-shop scheduling problem. Future Gener. Comput. Syst. 26, 533–541.
7. Baker, K. (1990). Scheduling Groups of Jobs in the Two-Machine Flow Shop. Mathematical, Computers and Modeling, 13(3), 29- 36.
8. Fattahi, P., Saidi, M., Jolai, F. (2007). Mathematical modeling and heuristic approaches to flexible job shop scheduling problems. J. Intel. Manuf. 18, 331–342.
9. Frazier, G.V. (1996). An Evaluation of Group Scheduling Heuristics in a Flow-line Manufacturing Cell. International Journal of Production Research, 34(4), 959- 976.
10. GAO, L., Li, X., Wen, X., Lu, C., & Wen, F. (2015). A hybrid algorithm based on a new neighborhood structure evaluation method for job shop scheduling problem. Computers & Industrial Engineering, 88, 417-429.
11. Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1(2), 117–129.
12. Groover, M.P. (2008). Automation, Production Systems, and Computer-Integrated Manufacturing, Prentice Hall.
13. Kaplanoğlu, V. (2016). An object-oriented approach for multi-objective flexible job-shop scheduling problem. Expert Systems with Applications, 45, 71-84.
14. Khan, W.A., Raouf, A., Cheng, K. (2011). Virtual Manufacturing. Retrieved from http://www.springer.com/978-0-85729-185-1
15. Kirkpartick, S., Gelatt, C.D.Jr. & Vecchi, M.P. (1983). Science, 220, 4598, 671.
16. Krishna, K., Ganeshan, K., & Janaki Ram, D. (1995). Distributed Simulated Anneasling Algorithms for job shop scheduling.IEEE TRANSACTION ON SYSTEMS, MAN, AND CYBERNETICS, 25(7).
17. Krishnamoorthy, B. & Kamath, M. (2000). Scheduling in a Cellular Manufacturing Environment. A Review of Recent Research, Engineering Valuation and Cost Analysis, 2, 409-423.
18. Logendran, R., Mai, L., Talkington, D. (1995). Combined Heuristics for Bi-level Group Scheduling, Problems. International Journal Production Economics, 38, 133- 145.
19. Mahmoodi, F., Dooley, K. J. & Starr, P. J. (1990). An Investigation of Dynamic Group Scheduling, Heuristics in a Job shop Manufacturing Cell. International Journal of Production Research, 28(9), 1695-1711.
20. Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., Teller, E. (1953). Journal of Chemical Physics, 21, 1087.
21. Miltenburg. J. (2008).Setting manufacturing strategy for a factory-wiithin-a- factory. International Journal of Production Economics, 113, 307- 323.
22. Naderi, B., Fatemi Ghomi, S.M.T., Aminnayeri, M., Zandieh, M. (2011). Scheduling open shops with parallel machines to minimize total completion time. J. Comput. Appl. Math. 235, 1275–1287.
23. Shahsavari-Pour, N., & Ghasemishabankareh, B. (2013). A novel hybrid meta-heuristic algorithm for solving multi objective flexible job shop scheduling. Journal of Manufacturing Systems, 32(4), 771-780.
24. Schaller, J. E. (2001). A New Lower Bound for the Flow Shop Group Scheduling Problem. Computers and Industrial Engineering, 41, 151-161.
25. Shafer, S. M., & Charnes, J. M. (1995). A simulation analysis of factors influencing loading practices in cellular manufacturing. International Journal of Production Research, 33(1), 279–290.
26. Shih, W.L., Chien, Y.H., Chung, C.L, Kuo-Ching Ying (2012). Minimizing Total Flow Time in Permutation Flowshop Enviromnt. International Journal of Innovative Computing, 8(10), 6599-6612.
27. Skorin - Kapov, J., & Vakharia, A. J. (1993). Scheduling a Flow – line Manufacturing Cell: a Taboo. Search Approach, International Journal of Production Research, 31(7), 1721-1734.
28. Sridhar, J., & Rajendran, C. (1993). Scheduling in a Cellular manufacturing System: A simulated annealing Approach. International Journal of Production Research, 31(12), 2927-2945.
29. Solimanpur, M., Vrat, P., & Shankar, R. (2004). A heuristic to minimize makespan of cell scheduling problem. International journal of production economics, 88(3), 231-241.
30. Suer, G. A., Saiz, M., & Gonzalez, W. (1999). Evaluation of manufacturing cell loading rules for independent cells. International Journal of Production Research, 37(15), 3445–3468.
31. Vahit, K. (2015). An object-oriented approach for multi-objective flexible job-shop scheduling problem. Expert Systems with Applications. 45, 71-84.
32. Wilhelm, M.R., & Ward, T.L. (1987). Solving Quadratic Assignment Problem by Simulated Annealing. IIE Transactions, 19, 109-119.
33. Xia, W., & Wu, Z. (2005). An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Computers & Industrial Engineering, 48(2), 409-425.
34. Xingong, Z., Yong, W. (2015). Single-machine scheduling CON/SLK due window assignment problems with sum-of-processed times based learning effect. Applied Mathematics and Computation. 250, 628–635.
35. Yang, W. H. (2002). Group scheduling in a two-stage flowshop. Journal of the Operational Research Society, 53(12), 1367-1373.
36. Zhang, G., Shao, X., Li, P., &GAO, L. (2009). An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem. Computers & Industrial Engineering, 56(4), 1309-1318.
37. Zhang, R., Wu, C. (2011). A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardiness objective. Computers & Operations Research. 38, 854-867.
38. Zhang, R. (2013). A Simulated Annealing-based Heuristic Algorithm for Job Shop Scheduling to Minimize Lateness. International Journal of Advanced Robotic Systems. 10, 214.

فایل ها

هم رسانی

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

آمار