بخشی از مقاله
چکیده
زمانبندي در واقع به تخصیص منابع در طول زمان براي اجراي مجموعه اي از کارها در وضعیتهاي مختلف می پردازد. از آنجا که محیط کارگاه باز3 در بسیاري از محیطهاي دنیاي واقعی رخ می دهد، ارائه مدل مناسب و دقیق کمک بزرگی به مدیران و صنعتگران خواهد نمود. بیان داده هاي دقیق در مسائل زمانبنديعموماً دور از تصور است. در این پژوهش، کاربرد و توسعه یک الگوریتم ژنتیک را براي مسأله زمانبندي کارگاه باز مورد بررسی قرار داده سپس الگوریتم جدیدي با استفاده از الگوریتمهاي پیشین معرفی می شود که باعث افزایش سرعت اجراي الگوریتم ژنتیک شده و منجر به دستیابی به پاسخهاي بهتر براي این مسأله می شود. سپس نتایج این الگوریتم ژنتیک پیشنهادي و کارایی آن مشخص می شود. نتایج نشان می دهد که الگوریتم پیشنهادي قابلیت یافتن یک راه حل مطلوب را براي اکثر مسائل داشته اما یک کسر ناقص کوچک در مسائل آزمایشی بزرگتر و پیچیده تر وجود دارد . از آنجاییکه مسأله زمانبندي کارگاه باز، از جمله مسائل NP Hard بشمار می رود، نیاز به استفاده از الگوریتمهاي هوشمند جهت حل آن قطعی است. هدف از ارائه الگوریتم ژنتیک پیشنهادي بدست آوردن یک ترکیب امکانپذیر از ماشینها و کارها بوده تا زمان تکمیل کل برنامه کاهش یابد.
کلمات کلیدي: مسأله زمانبندي کارگاهی، مسأله زمانبندي کارگاه باز، الگوریتم ژنتیک، الگوریتم جستجوي ممنوعه، جستجوي محلی.
.1 مقدمه
در جهان رقابتی امروز استفاده از سیستم ها، رویکردها و تکنیک هاي کار آمد و مؤثر که موجب افزایش بهره وري در یک واحد تولیدي یا خدماتی می گردد، ضرورتی براي بقاء در فضاي بازار است. یکی از این روشها، زمانبندي می باشد. زمانبندي یک فرآیند تصمیم گیري است که نقش مهمی را در اکثر صنایع تولیدي و خدماتی ایفا می کند. زمانبندي در تدارکات، تولید، حمل و نقل، توزیع، پردازش اطلاعات و ارتباطات کاربرد دارد. مسأله زمانبندي کارگاهی یکی از مشهورتر ین و پیچیده ترین مسائل زمانبندياست که پیدا کردن جو اب بهینه براي آن از مرتبه NP-Hard است .[1] هدف مسائل برنامه ریزي کارگاهی، تخصیص mماشین به n کار می باشد. مسأله زمان بندي کارگاهی با مجموعه اي از کارها J {J1 , J 2 ,..., J n } و مجموعه اي از منابعR {R1, R 2,..., R n} نمایش داده می شود. هر کار Ji شامل مجموعه اي از فعالیت ها 1{T,T2,... ,T n } T که باید بین زمانآماده4 و زمان انجام5 انجام شوند. انجام هر فعالیت Ti نیازمند استفاده از مجموعه منابع R ik R در فاصله زمانی - - d ik میباشد. زمان شروع stik براي فعالیت Tki از موقعی است که شروع به استفاده از منابع Rik بکند .[2]
۲. مسأله زما ندی رگاه باز٦
مسأله زمانبندي کارگاه باز یک مسأله زمانبندي مهم و جهانی است و این مسأله به طور وسیع در صنعت کاربرد دارد. مسأله زمانبندي کارگاه باز جزء مسائل NP-hard است. در یک مسئله زمانبندي در محیط کارگاه باز m ماشین و n کار در نظر گرفته می شوند که هر کار حداکثر می تواند شامل m عملیات باشد. هر عملیات بایستی بر روي یک ماشین با زمان پردازش معین انجام شود .[3]مسأله زمانبندي کارگاه باز در ارتباط با زمانبندي مجموعه اي از کارها روي مجموعه اي از ماشین ها به منظور اطمینان از پردازش کارها در مدت زمان منطقی می باشد به گونه اي که اهداف مورد نظر بهینه گردند.این مسأله با مجموعه اي از فعالیت ها مواجه است که در انجام آنها لزومی به رعایت ترتیب خاصی وجود ندارد . بنابراین فضاي حل در مسائل زمانبندي کارگاه باز به طور قابل ملاحظه اي از فضاي جواب مسائل زمانبندي دیگر بزرگ تر است. به نظر می رسد محققان توجه کمتري نسبت به مسائل کارگاه باز داشته اند. بنابراین مسائل زمانبندي در محیط کارگاه باز به عنوان مسائلی مهم و جامع در سطح جهانی مطرح می باشند.برخی ویژگی هاي مسأله کارگاه باز به شرح زیر است :[3]
• کارها با هر توالی دلخواه روي ماشین ها پردازش می شوند.
• هر کار در هر زمان می تواند حداکثر روي یک ماشین پردازش شود.
• هر ماشین در هر لحظه حداکثر یک کار را می تواند پردازش کند.
• زمان پردازش هر عملیاتلزوماً برابر نیست.
•وقفه اندازي در کارها مجاز نمی باشد.
•زمان جداسازي کار از ماشین، مستقل از زمان پردازش و وابسته به کار بعدي است که روي آن ماشین پردازش می شود.
• عدم دسترسی به ماشین ها در یک یا چند بازه زمانی از قبل پیش بینی شده مجاز می باشد.
• تمامی زمانهاي پردازش، آماده سازي، مؤعد تحویل و اهمیت کارها به صورت بازه هاي در نظر گرفته شده است.
•تمامی ماشین ها در ابتدا در دسترس می باشند.
هدف مسأله زمانبندي کارگاه باز بدست آوردن یک ترکیب امکان پذیر از ماشین ها و کارها بوده که زمان کلی اتمام کارها7 کمترین زمان ممکن باشد.
۳. مرور ادبیات گذشته
هرچند در گذشته توجه کمتري نسبت به مسائل کارگاه باز شده اما به نظر می رسد در سال هاي اخیر، مسائل زمان بندي کارگاه باز مورد توجه محققان بسیاري قرار گرفته است. با این حال، مسائل کارگاه باز در مقایسه با سایر مسائل زمان بندي ها سهم بسیار کمتري را به خود اختصاص داده اند.ژانگ و همکاران [4] الگوریتم ژنتیک پیوندي را براي حل مسأله زمانبندي کارگاه باز با هدف کمینه سازي زمان تکمیل کل برنامه ارائه دادند. این الگوریتم ترکیبی از روال بهبود یافته محلی بر اساس جستجوي ممنوع8 در داخل الگوریتم ژنتیک پایه است.نادري و همکاران [5] مسأله زمانبندي کارگاه باز را با هدف کمینه سازي زمان تکمیل کل برنامه مورد مطالعه قرار دادند. آن ها توانستند با ارائه چهار تئوري جهت برطرف کردن اشکالات موجود در روش نمایش لیست جایگشتی9 از لحاظ تولید جوابهاي تکراري، فضاي جواب مسائل کارگاه باز را به طور قابل ملا حظه اي کاهش دهند.
در نهایت آن ها چهار الگوریتم ابتکاري10 سازنده را براي مسائل فوق پیشنهاد دادند.براسل و همکاران [6] مسأله زمانبندي کارگاه باز را مورد بررسی قرار دادند به طوري که متوسط زمان کار در جریان ساخت یا به طور معادل مجموع زمانهاي تکمیل کارها کمینه شود. آنها الگوریتمهاي سازنده متفاوتی را براي مسأله فوق ارائه دادند و کیفیت جوابها را به وسیله حد پایین11 بدست آمده از مسأله کارگاه باز در حالت بریدگی مجاز و نیز بوسیله برآورد متناوب از میانگین کار در جریان ساخت مورد ارزیابی قرار دادند.ماتا [7] دو مدل برنامه ریزي عدد صحیح مختلط که یکی از آنها بر مبناي زمان و دیگري بر مبناي توالی است را براي مسأله کارگاه باز چند پردازنده اي یکسان موازي در حالتی که زمانهاي پردازش فقط وابسته به مراحل می باشند ارائه داده و پیچیدگی آن
