چکیده:
مسائ عملی زمانبندی معمولا تصمیمگیرنده را وادار به در نیر گرفتن تعداد زیادی از معیارها قب از اتخارتصمیم می نمایند. این تحیید یک مسئله زمانبندی تک ماشین را مورد بررسی قرار می دهد که هدف در آنحداق کردن ترکیبی از دو معیار دیرکرد ک و واریانا زمان انتیار می باشد به حوری که زمان بیکاری درماشین مجاز نیست. حداق کردن دیرکرد ک همیشه به عنوان یک معیار عملکرد مهم در سیستم های عملی،که می توان با استفاده از آن از تحمی هزینههای جریمه دیرکرد اجتناب نمود، مطرح می باشد و واریانا زمانانتیار نیز یک معیار مهم در پیادهسازی کیفیت هدمات ) QoS ( در بسیاری از سیستم ها می باشد. هر کدام ازاین دو معیار از نوع NP-hard می باشند و بنابراین ترکیب هطی آن ها نیز NP-hard هواهد بود. برای اینمسئله الگوریتمی ژنتیک حراحی شده که از ساهتار معمول آن استفاده می کند. دو نوع جمعیت هیوریستیک وتصادفی برای جمعیت اولیه و دو نوع تابع برازش در الگوریتم به کار رفته است. کارایی الگوریتم ژنتیک ارائهشده به وسیله تست روی تعداد زیادی از مسائ نشان داده می شود
Actual scheduling problems may necessitate the decision maker to consider a variety of criteria prior to make any decision. This research considers a single machine scheduling problem، with the objective of minimizing a combination of total tardiness and waiting time variance criteria in which the idle time is not allowed. Minimizing total tardiness is always regarded as one of the most important performance criteria in practical systems to avoid penalty costs of tardiness and waiting time variance is an important criterion in establishing Quality of Service (QoS) in many systems. Each of these criteria is known to be NP-hard and therefore the linear combination of them will be NP-hard as well. For this problem، we developed a genetic algorithm by utilizing its general structure. Two types of heuristic and random initial population and two distinct fitness functions are applied to genetic algorithms. The GA is shown experimentally to perform well by testing on various instances.
خلاصه ماشینی:
"کوکسالان ٧ و بوراک ٨ (٢٠٠٣) تحقیقی روی استفاده از الگوریتم ژنتیک برای حل مسائل دو هدفه انجام و دو مسئله ، حداقل کردن زمان در جریان ساخت و تعداد کارهای دارای دیرکرد و همچنین ، حداقل کردن زمان در 1 Fry 2 Potts 3 Koulamas 4 Han 5 Su 6 Tien 7 Köksalan 8 Burak جریان ساخت و حداکثر زودکرد را بررسی و الگوریتمی ژنتیک برای حل این مسائل ارائه کردند.
مدل ریاضی مسئله به صورت زیر می باشد: minZ1 = Ʃkn=1mαx{(Ʃin=1 ƩJk=1XiJPi- Ʃin=1Xikdi),0} (1) 2 minZ2 =1Ʃkn=1(W[k] -1Ʃkn=1 W[k]) (2) n n W[k] = 0 if k = 1 (3) W[k] = Ʃin=1ƩJk-11XiJPi if k ≠ 1 (4) Ʃin=1XiJ = 1 Aj (5) ƩJn=1XiJ = 1 Ai (6) XiJ E {0,1} (7) Z١ : دیر کرد کل Z٢ : واریانس زمان انتظار [W]k : زمان انتظار کاری که در توالی k ام قرار می گیرد di : موعد تحویل کار i ام Pi : زمان پردازش کار i ام XiJ : متغیر تخصیص کار i ام به توالی j ام ( اگر کار i ام به توالی j ام اختصاص یابد ١ و در غیر این صورت صفر خواهد بود) همان طور که در بخش قبل اشاره شد برای مسائل دسته اول (١٥ ,١٠ ,٥= n) انحراف نتایج الگوریتم های طراحی شده از نتایج بهینه بدست میآید.
(1 + Z2*opt)[ (8) لازم به ذکر است که در این مدل Zopt١ و Zopt٢ به ترتیب نشان دهنده مقادیر بهینه برای توابع دیرکرد کل و واریانس زمان انتظار هستند که برای هر مسئله از مسائل دسته اول ، از قبل و به صورت مجزا توسط نرم افزار LINGO بدست آمده است ."