بخشی از مقاله
چکیده
زمانبندي عمل تعیین اولویتها و یا مرتب نمودن فعالیتها براي برآورده نمودن الزامات مشخص، محدودیتها و یا اهداف است. امروزه تغییرات محیطی سازمان ها را وادار ساخته تا پیوسته به منظور سازگاري با محیط به دنبال بهترین راهکارها و رویه ها باشند. یکی از راههاي کسب این وضعیت تاکید بر برنامه ریزي مناسب جهت کمینه کردن جریمه دیرکردها و زود کرد ها هنگام انجام فعالیت می باشد.
مساله کارگاه باز یکی از مسائل کلاسیک زمانبندي است .در این مساله هر یک از کارها توسط تمامی ماشین ها یا برخی از آنها پردازش میشوند به طوري که هیچ محدودیتی در زمینه توالی پردازش کارها به روي ماشین ها وجود ندارد. در این مطالعه یک مدل ریاضی براي حل مسئله مورد نظر پیشنهاد میشود و همچنین چگونگی تبدیل تابع جریمه غیر خطی به قطعه قطعه خطی شرح داده میشود. داده ها با استفاده از نرم افزار بهینه سازي اعتبار سنجی شده اند.
.1مقدمه
زمان بندي به معنی تخصیص تعدادي منابع محدود به مجموعه اي محدود از کار ها در طول زمان می باشد .در واقع زمان بندي یک تابع تصمیم گیري است که یک یا چند هدف را بهینه سازي می کند. در زمان بندي دو مفهوم اصلی منابع و کار ها حالت هاي مختلفی می توانند داشته باشند، به طور مثال منابع قابل دسترسی در یک کارگاه صنعتی، یک فرودگاه پر ترافیک، یک پروژه ساختمانی و یا یک محیط اینترنت با دستگاه هاي مختلف محاسباتی می تواند به ترتیب عبارت از ماشین هاي صنعتی ازورودي پایانه هاي پرواز و هواپیماهاي مختلف، مهندسین ساختمانی قبیل دستگاه هاي تراش و تکنسین ها و کارگران و بالاخره تعداد و ظرفیت هاي خطوط انتقال داده هاي کامپیوتري براي دریافت و ارسال پیام ها باشد، به همین ترتیب کار ها در چهار محیط مختلف فوق می تواند به ترتیب عملیات مختلف ماشین کاري، پرواز ها و مراحل مختلف اجراي عملیات ساختمانی و بالاخره اجراي برنامه هاي مختلف کامپیوتري تعریف گردند.
البته ممکن است کار ها داراي اولویت مختلفی باشند، به عنوان مثال از اولویت زود ترین زمان ممکن براي شروع یک کار و یا موعد تحویل یک کار می توان نام برد .تابع هدف یک مساله زمان بندي هم می تواند موارد مختلفی را در برگیرد ، به عنوان مثال تابع هدف می تواند به صورت حداقل کردن زمان اتمام آخرین کار و یا حداقل کردن تعداد کارهایی که داراي تاخیر بعد از موعد باشند، در نظر گرفته شود.
مساله کارگاه باز یکی از مسائل کلاسیک زمانبندي است .در این مساله هر یک از کارها توسط تمامی ماشین ها یا برخی از آنها پردازش میشوند به طوري که هیچ محدودیتی در زمینه توالی پردازش کارها به روي ماشین ها وجود ندارد .در واقع در مساله کارگاه باز تعدادي ماشین و تعدادي کار وجود دارد به نوعی که هر کار داراي تعدادي عملیات میباشد و هر عملیات باید به روي یک ماشین مشخص پردازش شود. اما نکته مهمی که این مساله را از مساله کارکارگاهی متمایز میکند این است که در این مساله ترتیب عملیاتهاي یک کار از پیش تعیین شده نیست. در سالهاي اخیر، کاربرد مدلهاي ریاضی براي حل بهینه مسایل زمانبندي توجه بسیاري از محققین را به خود جلب کرده است .
بسیاري از تحقیقات در زمینه ي مدلسازي کارکارگاهی و جریان کارگاهی تک ماشینه بوده است و فرمول بندي مساله زمانبندي کارگاه باز کمتر مورد توجه محققین قرار گرفته است. برخی از محققین الگوریتم هاي مختلفی براي فرمول بندي این مساله استفاده کرده اند. هانگ و همکاران یک الگوریتم کلونی زنبور عسل براي مساله کارگاه باز ارائه کرده اند، نویسنده مدعی شده است که این روش براي کمینه سازي مجموع زمان حل براي رسیدن به بهینگی روشی کارآمد است.[
پناهی و همکاران در مطالعه خود روش هاي مرسوم زمانبندي را ناکارآمد میدانند و از الگوریتم کلونی مورچگان براي حل مساله زمانبندي کارگاه باز استفاده کرده اند
یکی از روش هاي حل دقیق در مسائل زمانبندي استفاده از روش شمارشی الگوریتم شاخه و کران است لذا برخی از نویسندگان مانند لیا الگوریتم شاخه و کران براي حل مساله کارگاه باز استفاده کرده اند.
2.1 مجموع وزن دار دیرکرد ها
امروزه تغییرات محیطی سازمان ها را وادار ساخته تا پیوسته به منظور سازگاري با محیط به دنبال بهترین راهکارها و رویه ها باشند. یکی از راههاي کسب این وضعیت تاکید بر برنامه ریزي مناسب جهت کمینه کردن جریمه دیرکردها فعالیت می باشد. جریمه که به عنوان دیرکرد کارها در نظر گرفته می-شود ممکن است براي کارهاي مختلف متفاوت باشد ، بنابراین براي کارها وزن در نظر گرفته میشود. در برخی از مطالعات در زمینه مسائل کارگاهی کمینه کردن مجموع وزندار دیر کرد ها به عنوان یک هدف مشاهده میگردد، هر کدام از نویسندگان در مطالعات خود در زمینه کارکارگاهی، تک ماشینه و جریان کارگاهی به بررسی حداقل سازي میانگین زمان هاي تکمیل و میانگین مقادیروزن دار دیرکرد کارها به طور همزمان پرداختند. ژو و همکاران در مطالعه خود با استفاده از ترکیب یک روش اکتشافی و اگوریتم ژنتیک به حداقل سازي دیر کر هاي داراي وزن در مساله کار کار گاهی پرداخته اند به طوري که مدعی شده اند استفاده از ترکیب دو روش اکتشافی و ژنتیک کارامد تر از هر یک از روش ها به تنهایی میباشد.
نوري درویش و توکلی مقدم مساله5]کارگاه باز را با هدف کمینه کردن مجموع وزن دار دیر کرد ها بررسی کرده اند در این مطالعه نویسندگان از توالی وابسته به زمان راه اندازي استفاده نموده اند
یانگ و همکاران در مساله جریان کاري انعطاف پذیر به استفاده و مقایسه سه روش حل پرداخته است. ابتدا مساله را به یک سري از زیر برنامه هاي تک مرحله اي تجزیه و سپس از یک الگوریتم جستجو ممنوع براي حل مساله جریان کاري انعطاف پذیر استفاده نموده اند ، نهایتا از الگوریتمی ترکیبی که از ترکیب دو مورد اول می باشد مساله را حل و با یکدیگر مقایسه نموده اند.
بستمن و همکاران نیز در مطالعه خود در ارتباط با مساله جریان کاري با هدف کمینه کردن دیرکرد هاي داراي وزن از الگوریتم مورچگان بهره برده اند.
در برنامه ریزي سیستم هاي تولیدي در مسائلی که زمان ها یا هزینه هاي آماده سازي نه تنها وابسته به زمانی هست که قرار است کار روي آن پردازش شود، بلکه وابسته به کاري که اخیرا تمام شده است نیز هستند، با عنوان زمان آماده سازي وابسته به توالی شناخته شده میباشند. رنجبر و زاده یک مسئله کار گاه باز بدون وقفه را با استفاده از یک روش اکتشافی بررسی کرده اند و مدعی شده اند که روش هاي اکتشافی براي حل مساله کارگاه باز بدون وقفه موثر است
.2 بیان مساله
زمانبندي عمل تعیین اولویتها و یا مرتب نمودن فعالیتها براي برآورده نمودن الزامات مشخص، محدودیتها و یا اهداف است. امروزه یکی از مسایل مهم مورد بحث در بهینه سازي موضوع زمانبندي است که به تخصیص منابع در طول زمان براي اجراي مجموعه اي از وظایف در شرایط مختلف میپردازد .مساله کارگاه باز یکی از مسائل کلاسیک زمانبندي است .
در این مساله هر یک از کارها توسط تمامی ماشین ها یا برخی از آنها پردازش میشوند به طوري که هیچ محدودیتی در زمینه توالی پردازش کارها به روي ماشین ها وجود ندارد .در واقع در مساله کارگاه باز تعدادي ماشین و تعدادي کار وجود دارد به نوعی که هر کار داراي تعدادي عملیات میباشد و هر عملیات باید به روي یک ماشین مشخص پردازش شود، اما نکته مهمی که این مساله را از مساله کارکارگاهی متمایز میکند این است که در این مساله ترتیب عملیاتهاي یک کار از پیش تعیین شده نیست. جریمه که به عنوان دیرکرد کارها در نظر گرفته میشود ممکن است براي کارهاي مختلف متفاوت باشد ، بنابراین براي کارها وزن در نظر گرفته میشود.
1.2 مفروضات مساله
- کارها با هر توالی دلخواه روي ماشین ها پردازش میشوند.
- هر کار در هر زمان حداکثر به روي یک ماشین پردازش می شود.
- هر ماشین در هر لحظه حداکثر یک کار را میتواند پردازش کند.
- وقفه اندازي در کارها مجاز نمیباشد بدین معنی که اگر کاري وارد ماشینی شد تا پایان پردازش در ماشین میماند وجدا نمیشود.
- زمان آماده سازي کارها مستقل از زمان پردازش و وابسته به ماشین تخصیص داده شده است.
- زمان جداسازي کار از ماشین مستقل از زمان پردازش و وابسته به کار بعدي است که روي آن ماشین پردازشخواهد شد.
- براي هرکار موعد تحویل کار در نظر گرفته شده است.
- تمامی ماشینها در زمان صفر در دسترس میباشند.
- براي هر کار یک وزن به عنوان معیار اهمیت قرار داده شده است.
2.2 بیان ریاضی مساله
: r اندیس مربوط به بازه {1,2,3,4,5}
: n تعداد ماشین ها{1,2,…,n}
: m تعداد کار ها{0,1,2,…,n}
:l ,i اندیس ماشینها - - l, i ∈{1,2,…n}
: j ,h اندیس کارها - j ,h ∈{0,1,2,…,n} -
اندیس ها
پارامترهاي مساله نیز به شرح زیر است:
: P مدت زمان پردازش کار روي ماشین
: d موعد تحویل کار
