بکارگیری رویه جستجوی تصادفی تطابقی حریصانه برای زمانبندی مسئله جریان کارگاهی بدون صف های میانی با استفاده از تبدیل به مسئله فروشنده دوره گرد
الموضوعات :
Javad Behnamian
1
(Assistant Professor, Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran)
Ronak Mohammadi
2
(Ms, Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University,)
Omid Rezaei
3
(Department of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, Iran)
تاريخ الإرسال : 22 الإثنين , رمضان, 1437
تاريخ التأكيد : 09 الأربعاء , صفر, 1438
تاريخ الإصدار : 11 السبت , ربيع الأول, 1438
الکلمات المفتاحية:
Scheduling,
GRASP,
زمانبندی,
الگوریتم جستجوی تصادفی تطابقی حریصانه,
جریان کارگاهی بدون صف های میانی,
مسئله فروشنده دوره گرد,
Flow shop without intermediate queues,
TSP,
ملخص المقالة :
هدف از این مقاله یافتن توالی بهینه به منظور کمینه کردن فاصله زمانی ساخت برای مسئله زمانبندی جریان کارگاهی بدون صفهای میانی میباشد. مسائل زمانبندی بدون انتظار در آن دسته از محیطهای تولیدی رخ میدهد که در آن یک کار میبایست از آغاز تا پایان بر روی یک ماشین یا چند ماشین بدون وقفه پردازش شود. از آنجایی که ساختار این مسئله شباهت بسیاری با مسئله فروشنده دورهگرد دارد، در تحقیق حاضر از یک رویکرد جدید جهت بدست آوردن دیرکردها کمک گرفته شده به گونه ای که با هدف یافتن توالی بهینه عملیاتی که کمترین فاصله زمانی ساخت را داراست از ماتریس دیرکردهای بدست آمده از مسئله فروشنده دورهگرد استفاده شده است. همچنین از الگوریتم جستجوی تصادفی تطابقی حریصانه برای حل مسئله تعیین توالی جریان کارگاهی بدون صفهای میانی استفاده و کارایی آن پس از تعیین پارامتر از طریق روش فاکتوریل، با الگوریتم کلونی مورچگان مقایسه شده است.
المصادر:
Aldowaisan, T., & Allahverdi, A. (1998). Total flowtime in no-wait flowshops with separated setup times. Computers & Operations Research. 25(9), 757-765.
Baker, K.R., Trietsch, D. (2009). Principles of Sequencing and Scheduling, Wiley.
Bertolissi, E. (2000). Heuristic algorithm for scheduling in the no-wait flow-shop.
Feo, T.A., & Resende, M. G. (1995). Greedy randomized adaptive search procedures. Journal of global optimization. 6(2), 109-133.
Festa, P. (2003). Greedy randomized adaptive search procedures. AIROnews, 7(4), 7-11.
Gupta, J. N., & Stafford E. F. (2006). Flowshop scheduling research after five decades. European Journal of Operational Research. 169(3), 699-711.
Hahsler, M., & Hornik, H. (2009). Introduction toTSP - infrastructure for the traveling salespersonproblem. Journal of Statistical Software. 23, 1–21.
Hall, N. G., & Sriskandarajah, C. (1996). A survey of machine scheduling problems with blocking and no-wait in process. Operations research. 44(3), 510-525.
Hejazi, S. R., & Saghafian, S. (2005). Flowshop-scheduling problems with make span criterion: a review. International Journal of Production Research. 43(14), 2895-2929.
Jaillet, P. (1988). A priori solution of a traveling salesman problem in which a random subset of the customers are visited. Operations Research, 36(6). 929-936.
Jayaswal, S. (2008). A comparative study of tabu search and simulated annealing for traveling salesman problem. Department of Management Sciences, University of Waterloo. Project Report.
Johnson, D.S., & McGeoch, L. A. (1997). The traveling salesman problem: A case study in local optimization. Local search in combinatorial optimization. 1, 215-310.
Layeb, A., Ammi, M., & Chikhi, S. (2013). A GRASP Algorithm Based on New Randomized Heuristic for Vehicle Routing Problem. CIT. Journal of Computing and Information Technology. 21(1), 35-46.
Li, X, Wang, Q, & Wu, C. (2008). Heuristic for no-wait flow shops with make span minimization. International Journal of Production Research. 46(9), 2519-2530.
Pan, Q. K., Wang, L., Tasgetiren, M. F., & Zhao, B. H. (2008). A hybrid discrete particle swarm optimization algorithm for the no-wait flow shop scheduling problem with makespan criterion. The International Journal of Advanced Manufacturing Technology. 38(3-4), 337-347.
Papadimitriou, C. H., & Kanellakis, P. C. (1980). Flowshop scheduling with limited temporary storage. Journal of the ACM. 27(3), 533-549.
Rajendran, C., & Chaudhuri, D. (1990). Heuristic algorithms for continuous flow‐shop problem. Naval Research Logistics. 37(5), 695-705.
Reddi, S. S., & Ramamoorthy, C. V. (1972). On the flow-shop sequencing problem with no wait in process. Operational Research Quarterly. 323-331.
Selen, W.J., & Hott, D.D. (1986). A new formulation and solution of the flow shop scheduling problem with no in process waiting. Applied Mathematical Modeling. 10, 246-248.
Tseng, L.Y., & Lin, Y.T.(2010). A hybrid genetic algorithm for no-wait flowshop scheduling problem. International Journal of Production Economics. 128(1), 144–152.
Xie, J., Xing, W., Liu, Z., & Dong, J. (2004). Minimum deviation algorithm for two-stageno-wait flow shops with parallel machines. Computers & Mathematics with Applications. 47(12), 1857-1863.
_||_
Aldowaisan, T., & Allahverdi, A. (1998). Total flowtime in no-wait flowshops with separated setup times. Computers & Operations Research. 25(9), 757-765.
Baker, K.R., Trietsch, D. (2009). Principles of Sequencing and Scheduling, Wiley.
Bertolissi, E. (2000). Heuristic algorithm for scheduling in the no-wait flow-shop.
Feo, T.A., & Resende, M. G. (1995). Greedy randomized adaptive search procedures. Journal of global optimization. 6(2), 109-133.
Festa, P. (2003). Greedy randomized adaptive search procedures. AIROnews, 7(4), 7-11.
Gupta, J. N., & Stafford E. F. (2006). Flowshop scheduling research after five decades. European Journal of Operational Research. 169(3), 699-711.
Hahsler, M., & Hornik, H. (2009). Introduction toTSP - infrastructure for the traveling salespersonproblem. Journal of Statistical Software. 23, 1–21.
Hall, N. G., & Sriskandarajah, C. (1996). A survey of machine scheduling problems with blocking and no-wait in process. Operations research. 44(3), 510-525.
Hejazi, S. R., & Saghafian, S. (2005). Flowshop-scheduling problems with make span criterion: a review. International Journal of Production Research. 43(14), 2895-2929.
Jaillet, P. (1988). A priori solution of a traveling salesman problem in which a random subset of the customers are visited. Operations Research, 36(6). 929-936.
Jayaswal, S. (2008). A comparative study of tabu search and simulated annealing for traveling salesman problem. Department of Management Sciences, University of Waterloo. Project Report.
Johnson, D.S., & McGeoch, L. A. (1997). The traveling salesman problem: A case study in local optimization. Local search in combinatorial optimization. 1, 215-310.
Layeb, A., Ammi, M., & Chikhi, S. (2013). A GRASP Algorithm Based on New Randomized Heuristic for Vehicle Routing Problem. CIT. Journal of Computing and Information Technology. 21(1), 35-46.
Li, X, Wang, Q, & Wu, C. (2008). Heuristic for no-wait flow shops with make span minimization. International Journal of Production Research. 46(9), 2519-2530.
Pan, Q. K., Wang, L., Tasgetiren, M. F., & Zhao, B. H. (2008). A hybrid discrete particle swarm optimization algorithm for the no-wait flow shop scheduling problem with makespan criterion. The International Journal of Advanced Manufacturing Technology. 38(3-4), 337-347.
Papadimitriou, C. H., & Kanellakis, P. C. (1980). Flowshop scheduling with limited temporary storage. Journal of the ACM. 27(3), 533-549.
Rajendran, C., & Chaudhuri, D. (1990). Heuristic algorithms for continuous flow‐shop problem. Naval Research Logistics. 37(5), 695-705.
Reddi, S. S., & Ramamoorthy, C. V. (1972). On the flow-shop sequencing problem with no wait in process. Operational Research Quarterly. 323-331.
Selen, W.J., & Hott, D.D. (1986). A new formulation and solution of the flow shop scheduling problem with no in process waiting. Applied Mathematical Modeling. 10, 246-248.
Tseng, L.Y., & Lin, Y.T.(2010). A hybrid genetic algorithm for no-wait flowshop scheduling problem. International Journal of Production Economics. 128(1), 144–152.
Xie, J., Xing, W., Liu, Z., & Dong, J. (2004). Minimum deviation algorithm for two-stageno-wait flow shops with parallel machines. Computers & Mathematics with Applications. 47(12), 1857-1863.
