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

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

نویسندگان

1 دانشگاه صنعتی نوشیروانی بابل

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

چکیده

 مسأله زمانبندی در محیط جریان کارگاهی انعطاف­پذیر شامل تعیین توالی در یک مسأله جریان کارگاهی می­باشد که در هر مرحله حداقل یک یا چند ماشین موازی غیرمشابه وجود دارد. تابع هدف مسأله کمینه­سازی حداکثر زمان تکمیل کارها می­باشد. برای حل این مسأله از روش آزادسازی لاگرانژین استفاده‌شده است. برای حل زیرمسأله­های تولیدشده با استفاده از روش آزادسازی لاگرانژین نیز از دو رویکرد ساده­سازی زیرمسأله­ها و توسعه قوانین چیرگی استفاده‌شده است. نتایج نشان می­دهد که هر دو روش می­توانند به جواب­های نزدیک به بهینه در زمان­های نسبتاً معقول دست پیدا کنند ولی تفاوت معناداری با یکدیگر ندارند. همچنین روش ساده­سازی زیرمسأله‌ها در مدت زمان کوتاه­تری می­تواند به جواب­های مورد نظر دست یابند.

کلیدواژه‌ها

موضوعات


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

Developing a Lagrangian Relaxation Method for Flexible Flowshop Scheduling Problem

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

  • Ebrahim Asadi Gangraj 1
  • Nasim Nahavandi 2
1 Babol University of Technology
2 Tarbiat Modares University
چکیده [English]

Flexible flow shop scheduling problem (FFS) with unrelated parallel machines contains sequencing in flow shop where, at any stage, there exists one or more unrelated parallel machines. The objective consists of minimizing the maximum completion time. A new Lagrangian relaxation (LR) method is developed to solve the candidate problem. To solve the sub-problems in LR, we use two approaches such as, simplicity of sub-problems and dominance rules. The results show that the both approaches can achieve the near-optimal solution in reasonable time; but there is no significant difference between them. On the other side, simplicity of sub-problems can achieve the solution in reasonable time.

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

  • Flow Shop
  • Makespan
  • Lagrangian Relaxation
  • Dominance Rules
[1]   Quadt, D., Kuhn, H. (2007). A taxonomy of flexible flow line scheduling procedures. European Journal of Operational Research, 178:686–698.
[2]   Shahvaria, O., Salmasi, N., Logendran, L., Abbasi, B. (2012). An efficient tabu search algorithm for flexible flow shop sequence-dependent group scheduling problems, International Journal of Production Research, 50(15): 4237–4254.
[3]   Wittrock, R.J. (1988). An Adaptable Scheduling Algorithm for Flexible Flow Lines. Operations Research, 36: 445–453.
[4]   Agnetis, L., Pacifici, A., Rossi, F., Lucertini, M., Nicoletti, S., Nicolo, F. (1997). Scheduling of Flexible Flow Shop in an Automobile Assembly Plant. European Journal of Operation Research, 97(2):348–362.
[5]   Adler, L., Fraiman, N., Kobacker, E., Pinedo, M., Plotnicoff, J.C., Wu, T.P. (1993). BPSS: a Scheduling Support System for the Packaging Industry. Operations Research, 41: 641–648.
[6]   Moursli, O., Pochet, Y. (2000). A branch-and-bound algorithm for the hybrid flowshop, International Journal of Production Economics, 64: 113–25.
[7]   Yang Y., Kreipl, S., Pinedo, M. (2000). Heuristics for minimizing total weighted tardiness in flexible flowshops, Journal of Scheduling, 3: 71–88.
[8]   Fattahi, P., Hosseini, S.M.H., Jolai, F., Tavakkoli-Moghaddam, R. (2014). A branch and bound algorithm for hybrid flow shop scheduling problem with setup time and assembly operations, Applied Mathematical Modelling, 38: 119–134;
[9]   Riane, F., Artibas, A., Elmaghraby, S.E. (1998). A hybrid three stage flow shop problem: efficient heuristics to minimize makespan, European Journal of Operations Research, 109: 321–329.
[10]    Linn, R., Zhang., W. (1999) Hybrid flow shop scheduling: a survey, Computers and Industrial Engineering, 37: 57–61.
[11]    Tang, L., Xuan, H., Liu, J. (2006). A new Lagrangian relaxation algorithm for hybrid flowshop scheduling to minimize total weighted completion time, Computers & Operations Research 33: 3344–3359
[12]    Liu, G.D., Luh, P.B. (1997). Scheduling permutation flow shops using the Lagrangian relaxation technique. Annals of Operations Research, 70: 171–89.
[13]    Luh, P.B., Hoitomt, D.J. (1993). Scheduling of manufacturing systems using the Lagrangian relaxation technique, IEEE Transaction on Automatic Control, 38(7): 1066–1079.
[14]    Chang, S.C., Liao, D.Y., Hsieh, F.S (1991). Scheduling flexible flow shops of no setup cost by a lagrangian relaxation and network flow approach, Interactional Conference on Robotics and Automation.
[15]    Irohara, T. (2010). Lagrangian relaxation algorithms for hybrid flow-shop scheduling problems with limited buffers. Biomedical Soft Computing and Human Sciences, 15(1): 21-28.
[16]    Sun, X., Noble, J.S. (1999). An Approach to Job Shop Scheduling with Sequence-Dependent Setups. Journal of Manufacturing Systems, 18(6).
[17]    Liu, C.Y., Chang, S.C. (2000). Scheduling Flexible Flow Shops with Sequence-Dependent Setup Effects, IEEE transaction on robotics and automation, 16(4): 408-419.
[18]    Nahavandi, N., Asadi Gangraj, E. (2014). A New Lower Bound for Flexible Flow Shop Problem with unrelated parallel machines, International Journal of Industrial Engineering & Production Research, 25(1): 65-70.
[19]    Salmasi, N., Logendran, L., Skandari, M.R. (2010). Total flow time minimization in a flowshop sequence-dependent group scheduling problem, Computers & Operations Research 37: 199 – 212.