-مقایسه اثر انواع عملگرهای الگوریتم ژنتیک بر مجموع دیرکردها در مسئله فلوشاپ

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

نویسندگان

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

2 کارشناس ارشد، آمار اقتصادی و اجتماعی دانشکده علوم ریاضی دانشگاه صنعتی اصفهان، اصفهان، ایران.

چکیده

مسئله زمانبندی فلوشاپ (FSSP) با هدف کمینه کردن مجموع دیرکردها، از جمله مسائل مشکل یا NP-hard است که تاکنون مقالات زیادی درباره آن نوشته شده است. در این خصوص به روش‌های فراابتکاری از جمله روش الگوریتم ژنتیک نیز توجه شایانی شده است. تعیین پارامترهای الگوریتم‌های فراابتکاری نیز از جمله موضوعات مهمی است که پژوهش‌های زیادی را به خود اختصاص داده است. در همین راستا، این مقاله به بررسی اثر انواع عملگرهای تقاطعی و جهشی الگوریتم ژنتیک با هدف کمینه کردن مجموع دیرکردها در مسئله فلوشاپ جایگشتی می‌پردازد تا مشخص شود که کدام یک از آن‌ها برای استفاده در این مسئله مناسب‌تر است. نتایج عددی بدست آمده حاکی از آن است که از بین عملگرهای تقاطعی متداول، عملگرهای یک نقطه‌ای و دو نقطه‌ای نوع یک و از بین عملگرهای جهشی، عملگر جابجاییِ مجاور در اغلب موارد بهترین مقدار برای مسئله مذکور هستند.

کلیدواژه‌ها

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

Comparison of the Effect of Various Types of Genetic Algorithm Operators on the Total Amount of Tardiness in Flow Shop Problem

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

  • Morteza Rasti Barzoki 1
  • Sajjad Raeisi 2
1 Assistant Prof., Department of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan, Iran.
2 Msc. in Applied Statistics, Department of Mathematical Sciences, Isfahan University of Technology, Isfahan, Iran.
چکیده [English]

Flow Shop Scheduling Problem (FSSP) with the objective of minimizing total amount of tardiness is an NP-hard problem and many articles has been written about it. In this context, great attention has been paide to metahuristic techniques such as genetic algorithm. Additionally determination of the paraemeters of the algorithms is an important subject in the research area that many researches have been allocated to it. The purpose of this paper is to investigate the effect of crossover and mutation operators of the genetic algorithm on the objective of minimizing total amount of tardiness in permutation FSSP in order to determine more suitable ones to be applied in the problem. The obtained numerical results indicate that in most cases among common crossover operators,using the one point and two point (first version) operators and among mutation operators,applying the adjacent exchange gives the best value for the mentioned problem.

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

  • Analysis of Variance (ANOVA)
  • Design of Experiments (DOE)
  • Flow Shop Scheduling Problem (FSSP)
  • Genetic algorithm
  • Total Amount of Tardiness

مراجع

Armentano, Vinícius A. & Ronconi, Débora P. (1999). Tabu search for total tardiness minimization in flowshop scheduling problems. Computers & Operations Research, 26 (3): 219-235.
Chung, C., Flynn, J. & Kirca, O¨. (2005). A branch and bound algorithm to minimize the total tardiness for m-machine permutation flowshop problems. European Journal of Operational Research.
Du, J. & Leung, J. Y. T. (1990). Minimizing total tardiness on one processor is NP-Hard. Mathematics of Operations Research, 15: 483-495.
Hirakawa, Y. (1999). A quick optimal algorithm for sequencing on one machine to minimize total tardiness. International Journal of Production Economics, 60–61: 549–555.
Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. USA, MI, Ann Arbor: The University of Michigan Press.
Holsenback, J. & Russell, R. (1992). A heuristic algorithm for sequencing on one machine to minimize total tardiness. Journal of Operational Research Society, 43: 53-62.
Kim, Y.D. (1993). A new branch and bound algorithm for minimizing mean tardiness in 2-machine flowshops. Computers and Operations Research, 20: 391–401.
Kim, Y.D. (1995). Minimizing tardiness in permutation flowshops. European Journal of Operational Research, 85: 541–555.
Koulamas, C. (1994). The total tardiness problem: review and extensions. Operations Research, 42: 1025-1040.
Lawler, E. (1997). A pseudo-polynomial algorithm for sequencing jobs to minimize total tardiness. Annals of Discrete Mathematics, 1: 331–342.
Nearchou, A.C. (2004). The effect of various operators on the genetic search for large scheduling problems. International Journal Production Economics, 88: 191–203.
Pinedo, M. (2002). Scheduling: Theory, Algorithms and Systems, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall.
Potts, C.N. & Van Wassenhove, L.N. (1982). A decomposition algorithm for the single machine total tardiness problem. Operations Research Letters, 26: 177-182.
Russell, R. & Holsenback, J. (1997). Evaluation of leading heuristics for the single machine tardiness problem. European Journal of Operational Research, 96: 538-545.
Sen, T., Dileepan, P. & Gupta J. (1989). The two-machine flowshop scheduling problem with total tardiness. Computers and Operations Research, 16: 333–340.
Szwarc, W. & Mukhopadhyay, S. (1996). Decomposition of the single machine total tardiness problem. Operations Research Letters, 19: 243–250.
Szwarc, W., Della Croce, F. & Grosso, A. (1999). Solution of the single machine total tardiness problem. Journal of Scheduling, 2: 55-71.
Tansel, B., Kara, B. & Sabuncuoglu, I. (2001). An efficient algorithm for the single machine total tardiness problem. IIE Transactions, 33: 661–674.
ارسال نظر در مورد این مقاله
CAPTCHA Image

فایل ها

هم رسانی

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

آمار