حل مساله زمانبندی جریان کارگاهی برگشت پذیر بدون وقفه

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

نویسندگان

1 دانشجوی دکترا مهندسی صنایع دانشگاه تربیت مدرس تهران

2 دانشیار، دانشکده مهندسی صنایع و سیستم‌ها، دانشگاه تربیت مدرس، تهران.

3 فارغ التحصیل کارشناسی ارشد مهندسی صنایع- صنایع

چکیده

در این مقاله زمانبندی مساله جریان کارگاهی برگشت­پذیر بدون وقفه با هدف کمینه­سازی حداکثر زمان تکمیل کارها بررسی می­شود. محیط های جریان کارگاهی برگشت­پذیر به نوعی چیدمان جریان کارگاهی گفته می­شود که در آن حداقل یک کار می­بایست یک یا چند مرحله را بیش از یکبار ملاقات کند. در مسائل جریان کارگاهی بدون وقفه مراحل انجام یک کار بر روی ماشین ها از ابتدا تا انتها بدون وقفه انجام می­شوند. ادغام هردوی این خصوصیات در بسیاری از صنایع مانند صنایع رباتیک دارد کاربرد دارد که در ادبیات بصورت مجزا مورد بررسی قرار نگرفته است. در این مقاله برای مساله زمانبندی جریان کارگاهی برگشت­پذیر بدون وقفه مدل ریاضی ارائه شده است. برای مسایل با ابعاد کوچک نتایج حاصل از نرم­افزار GAMS با نتایج حاصل از الگوریتم­های ژنتیک و شبیه­سازی تبرید مقایسه گردیده است و برای ابعاد بزرگ نتایج حاصل از الگوریتم­های ژنتیک و شبیه­سازی تبرید با یکدیگر مقایسه گردیده­اند. نتایج محاسباتی نشان داد که در کل الگوریتم SA نسبت به GA، از لحاظ بدست آوردن جواب بهینه یا نزدیک به بهینه الگوریتمی کاراتر می‌باشد. 

کلیدواژه‌ها

موضوعات

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

Solving Re-entrant No-wait Flow Shop Scheduling Problem

نویسنده [English]

  • MohammadReza Amin-Naseri 2
2 Department of Industrial Engineering, Tarbiat Modares University, Tehran, Iran.
چکیده [English]

In this study we consider the production environment of re-entrant flow-shop (RFS) with the objective of minimizing make span of the jobs. In a RFS, at least one job should visit at least one of the machines more than once. In a no-wait flow shop-scheduling problem, when the process of a specific job begins on the first machine, it should constantly be processed without waiting in the line of any machine until its processing is completed on the last one. Integration of the properties of both of these environments, which is applied in many industries such as robotic industries, is not investigated separately. In the paper, we present a simulated annealing (SA) and a genetic algorithm (GA) based on heuristics for the problem. First, we develop the mathematical model for the problem, and then we present the suggested algorithms. For small scale, results of GA and SA are compared to GAMS. For large-scale problems, results of GA and SA are compared to each other. Computational results show that both SA ad GA algorithms perform properly but totally, SA is likely to turn out well in finding better solutions especially in large-scale problems.     

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

  • Re-entrant Flow shop
  • No-wait Flow shop
  • Genetic Algorithm
  • Simulated Annealing

مراجع

[1]     Hall, N.G., Sriskandarajah, C., (1996). “A survey of machine scheduling problems with blocking and no-wait in process”, Operations Research, 44: 510-525.
[2]     Aldowaisan, T., Allahverdi, Ali., (2003). “New  heuristics for no-wait flowshops to minimize makespan”, Computers & Operations Research, 30: 1219–1231.
[3]     Gupta, J.N.D., Strusevich, V.A., Zwaneveld, CM., (1997). “Two-stage no-wait scheduling models with setup and removal times separated”, Compute Operation Research, 24: 1025–1031.
[4]     Choi, S.W., Kim, Y.D. (2008). “Minimizing  makespan on an -machine re-entrant flowshop”, Computers & Operations Research, 35: 1684-1696.
[5]     Chen, J.S., Pan, J.C.H., Lin, C.M., (2008). “A hybrid genetic algorithm for the re-entrant flow-shop scheduling problem”, Expert Systems with Applications, 34: 570-577.
[6]     Jing, C., Tang, G., Qian, X., (2008). “Heuristic algorithms for two machine re-entrant flow shop”, Theoretical Computer Science, 400: 137-143.
[7]     Huang, R.H., Yu, S.C., Kuo, C.W., (2014). “Reentrant two-stage multiprocessor flow shop scheduling with due windows”, The International
Journal of Advanced Manufacturing Technology, 71: 1263-1276.
[8]     Li, Z.C., Qian, B., Hu, R., Zhang, C.S., Li, K., (2013). “A self-adaptive hybrid population-based incremental learning algorithm for M-machine reentrant permutation flow-shop scheduling”, Intelligent Computing Theories, 7995: 8-20.
[9]     Jing, C., Huang, W., Tang, G., (2011).  “Minimizing total completion time for re-entrant flow shop scheduling problems”, Theoretical Computer Science, 412: 6712-6719.
[10] Choi, S.W., Kim, Y.D., (2009). “Minimizing total tardiness on a two-machine re-entrant flow shop”, European Journal of Operational Research, 199: 375-384.
[11] Pan, J.C.H., Chen, J.S., (2003). “Minimizing  makespan in reentrant permutation flow-shops”, Journal of Operational Research Society, 57: 642- 653.
[12] Adressi, A., Hassanpour, S., Azizi, V., (2016). “Solving group scheduling problem in no-wait flexible flowshop with random machine breakdown”, Decision Science Letters, 5(1): 157-168.
[13] Graham, R.L., Lawler, E.L., Lenstra, J.K., Kan, A.R., (1979). “Optimization and approximation in deterministic sequencing and scheduling: a survey”, Annals of discrete mathematics, 5: 287-326.
نشریه پژوهش های مهندسی صنایع در سیستم های تولید
دوره 4، شماره 9
ویژه نامه یازدهمین و دوازهمین کنفرانس بین المللی مهندسی صنایع
اسفند 1395
صفحه 271-279

فایل ها

هم رسانی

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

آمار