ی است که در بهینه سازی ترکیبیاتی18 و مدل سازی تصادفی با آن ها روبرو هستیم. مشکلات اجرایی از نوع کاملا متفاوتی هستند. این مشکلات ممکن است به دقت مدلی که برای تحلیل مساله زمانبندی حقیقی از آن استفاده شده و نیز اعتبار داده های ورودی مورد نیاز بستگی داشته باشند.
زمانبندی در پالایشگاه نفت
یک پالایشگاه نفت خام به اپراتورهای تمام وقت در روز و هفته نیاز داشته و ضروری است که با یک سیستم سه شیفته، که در آن اپراتورها همیشه حداقل دو روز متوالی تعطیلی دارند و هر سومین آخر هفته را تعطیل می باشند، کار کند. زمانبندی برای سه ماه در یک بازه زمانی بسط می یابد و لذا هر کارمند می تواند برای روزهای تعطیل و شیفت کاری برنامه ریزی کند. در واقع وجود یک برنامه زمانبندی شفاف و منصفانه برای کارکنان ضروری است.
کارخانه تولید پاکت کاغذی
کارخانه ای که پاکت کاغذی برای سیمان، ذغال چوب، غذای حیوانات و … تولید می کند را در نظر بگیرید. مواد اولیه برای چنین عملیاتی رول های کاغذ هستند. فرآیند تولید، شامل سه مرحله است: چاپ لگو، چسباندن لبه های کاغذ و دوختن یک یا هر دو انتهای پاکت. هر مرحله شامل تعدادی ماشین است که لزوما مشابه نیستند. ماشین ها در هر مرحله ممکن است از نظر سرعت عمل، تعداد رنگی که می توانند چاپ کنند یا اندازه پاکتی که می توانند تولید کنند، متفاوتند. هر سفارش تولید، در بر گیرنده مقدار معینی از یک پاکت خاص است که باید در موعد مقرر تولید و ارسال شوند. زمان فرآیند برای عملیاتهای مختلف، با اندازه سفارش متناسب است. تحویل دیرتر از موعد، جریمه ای به شکل از دست دادن اعتبار را در بر دارد که مقدار این جریمه به اهمیت سفارش یا مشتری و میزان تاخیر در تحویل بستگی دارد. یکی از اهداف سیستم زمانبندی به حداقل رساندن مجموع این جرائم است.
زمانی که تولید یک ماشین از یک نوع پاکت به نوع دیگر پاکت، تغییر می کند، به یک آماده سازی احتیاج دارد. طول زمان آماده سازی روی ماشین به شباهت های بین دو سفارش متوالی بستگی دارد (تعداد رنگ های مشترک، تفاوت در اندازه پاکت ها و …). یک هدف مهم سیستم زمانبندی، به حداقل رساندن زمان کل صرف شده برای آماده سازی است.
کارخانه تولید تجهیزات لامپ های صنعتی
یک تولید کننده تجهیزات لامپ های صنعتی از خط مونتاژ کنترل شده ای به وسیله اپراتورها استفاده می کند. بر اساس تولید معمول که در راستای خط مونتاژ در جریان است، اپراتورها یک مجموعه تعریف شده از وظایف را دارا می باشند. برای هر تولید شرکت امیدوار به استفاده از زمانهای از پیش تعیین شده ای برای توسعه ایستگاه های کاری19 و تخصیص وظایف به این ایستگاه
شکل ‏26: مساله سه کار و سه ماشین
در شکل 2-7 نمودار گانت50 بر طبق ماشین و در شکل 2-8 نمودار گانت بر اساس کارها را مشاهده می کنید:
شکل ‏27: نمودار گانت بر طبق ماشین
شکل ‏28: نمودار گانت بر اساس کار
در حل مساله از تکنیکی که در شکل 2-9 مشاهده می کنید استفاده شده است.
شکل ‏29: تکنیک بکار برده شده برای مسائل Job shop
مدل های کارگاه باز51
مدل های کارگاه باز شبیه به مسائل کار کارگاهی هستند با این تفاوت که یک کار ممکن است بر روی ماشین ها، با هر توالی دلخواهی پردازش شود. به عبارت دیگر، هیچ توالی وابسته به عملیاتی وجود ندارد که یک کار از آن پیروی کند و هر کار از هر ماشین فقط یک بار میگذرد. معیار مورد نظر در این مسائل معمولا کمینه سازی حداکثر زمان تکمیل کارها می باشد.
مسئله زمانبندی کارگاه باز یک مسئله زمانبندی رایج و معمولی است و در عرصه مهندسی کاربرد دارد. در برخی از موارد صنعتی، زمانبندی کارگاه باز می تواند مسئله زمانبندی بزرگی مثل ساخت هواپیما را انجام دهد. در موارد این چنین، ارزش زمان سرمایه52 نقش مهمی در تعیین زمان ثابت دارد [18،19،21،24].
مسئله زمانبندی کارگاه باز یک مسئله زمانبندی مهم و جهانی است و این مسئله به طور وسیع در صنعت کاربرد دارد. مسئله زمانبندی کارگاه باز جزء مسائل سخت است. مسئله زمانبندی کارگاه باز شبیه به مسئله زمانبندی کار کارگاهی است با این تفاوت که در هر کار هیچ نوع اولویتی بین فرایند یا عملیات هر کار وجود ندارد. در مسئله زمانبندی کارگاه باز فضای راه حل به طور قابل ملاحظهای بزرگتر از مسئله زمانبندی کار کارگاهی است و به نظر می رسد که در کتاب ها و مقالات به آن کمتر توجه شده است. شرح مسئله زمانبندی کارگاه باز توسط گراهام و همکارانش بدین صورت باشد: یک تعداد کار به تعداد n (J1,J2, … , Jn) وجود دارد که روی یک سلسله ماشین به تعداد m (M1,M2, … , Mm) قابل پردازش است، هر کار متشکل از mعملیات ( m=1 to j ) میباشد که هر کدام باید روی یک ماشین متفاوت برای یک زمان مشخص شده پردازش شوند. عملیات هر کار می تواند در هر ماشینی پردازش شود ولی در هر زمان نهایتا یک عمل روی هر ماشین می تواند پردازش شود، و یک عمل از هر کار می تواند در یک زمان پردازش شود [26،39،40،63،65].
هدف مسئله زمانبندی کارگاه باز بدست آوردن یک ترکیب امکان پذیر از سفارشات ماشین و کار تعیین شده است که زمان کلی اتمام کارها در کمترین زمان ممکن باشد. در ادامه به بیان چندین مثال که جز مسائل کارگاه باز می باشد می پردازیم:
تعمیر کردن هواپیماهای بزرگ، که نیاز به تعمیر موتور و سیستم الکتریکی دارد. این دو وظیفه ممکن است به هر ترتیبی انجام شود ولی این غیر ممکن است که این دو کار را با هم انجام دهیم. یا در مثالی دیگر یک گاراژ اتومبیل بزرگ با فروشگاه های اختصاصی را در نظر بگیرید . یک وسیله نقلیه ممکن است به کار های زیر نیاز داشته باشد: تعمیر انباره لوله اگزوز، میزان کردن چرخها و تنظیم موتور. سه عمل از یک کار ممکن است در هر ترتیبی به وجود بیایند. به هر حال، مغازههای سیستم اگزوز، میزان کردن چرخ ها، و تنظیم موتور درساختمانهای مختلف هستند، و بنابراین انجام دو عمل در یک زمان امکان پذیر نیست، در مسئله زمانبندی کارگاه باز، ما فرض می کنیم که چندین کار از این قبیل کار ها و چندین وسیله نقلیه که نیاز به تعمیر دارند را داریم، موارد دیگر می تواند شامل: کنترل کیفیت مرکزی، انتساب کلاس، معاینه فنی خودرو، و مخابره ماهواره ای و بسیاری از موارد دیگر را می تواند شامل شود.
مدل های کارگاه وابسته53
همان کار کارگاهی است که ترتیب پردازش یک یا چند کار بستگی به پردازش سایر کارها دارد. معیار مورد نظر در این مدل ها معمولا کمینه سازی حداکثر زمان تکمیل کارها است.
مدل های پردازش دسته ای54
در این مدل ها کارها به صورت دسته ای پردازش شده و هر دسته نیاز به زمان پردازش معین دارد. ممکن است برای تعداد کارهایی که می توانند در یک زمان پردازش شوند، محدودیت ظرفیت نیز داشته باشد. یک اجاق آشپزی با حجم محدود مثالی برای پردازش دسته ای می باشد.
مدل های خط مونتاژ
در مسائل مربوط به این مدل ها، کار از یک توالی معین عملیات عبور می کند و هدف تعریف ایستگاه های کاری و تخصیص وظایف به این ایستگاه ها به منظور به دست آوردن یک سطح تولید معین و کاراست.
مدل های خط مونتاژ ترکیبی
در این مدل ها کارها بر روی یک خط مونتاژ پردازش می شوند تا محصولات مشابه (نه یکسان) با نیازمندی ها و زمان های پردازش مختلف تولید شوند.
البته باید اشاره کرد که تقسیم بندی بالا کاملا تمامی کلاس های مدل های زمانبندی از جمله زمانبندی نیروی انسانی و غیره را در بر نمی گیرد ولی می تواند دید مناسبی را به صورت کلی از کلاس های مختلف مدل های زمانبندی ارائه نماید.
محدودیت های زمانبندی
پردازش کارها دارای ویژگی های متفاوت بسیاری می باشد و معمولا مقید به محدودیت های ویژه است. به عنوان مثال در جدول ذیل برخی از محدودیت های مربوط به کارها در مسائل زمانبندی به ازای پارامتر β نشان داده شده است.
جدول ‏22: نمایش بعضی از محدودیت های مسائل زمانبندی با پارامتر β
محدودیت مربوطه
پارامتر β
محدودیت زمان ترخیص کار j ام
rj
مجاز بودن انقطاع کارها
prmp
محدودیت تقدم و تاخر در توالی
prec
محدودیت در دسترس نبودن ماشین ها
brkdwn
محدود بودن ظرفیت موجودی نیم ساخته
block
محدودیت مجاز نبودن موجودی نیم ساخته
no wait
مجاز بودن انجام مجدد یک کار توسط یک ماشین
recrc
در ادامه به بعضی از مهمترین محدودیت های موجود در مسائل زمانبندی اشاره می شود.
بریدگی: اغلب در طی زمان پردازش یک کار، وجود برخی از رویدادها منجر به قطع کار در حال پردازش به نفع کار دیگری می شود. مانند هنگامی که سفارشی با اولویت بالا وارد سیستم میشود. انواع مختلفی از بریدگی وجود دارد. بر اساس یک نوع از آن، کار از نقطه ای که قطع شده، ادامه می یابد، به عبارت دیگر بخشی از کارها در یک زمان و بخشی دیگر در زمانی دیگر انجام می پذیرد. بر اساس نوع دیگری از بریدگی، یک کار قطع می گردد و مجددا از نو شروع می شود.
محدودیت های زمان انتظار: در بسیاری از سیستم های تولیدی مقدار فضای موجود کمتر از کارهای منتظر پردازش بر روی یک ماشین می باشد. محدودیت فضای انبار در سیستم های جریان کارگاهی می تواند سبب انسداد گردد.
محدودیت حمل و نقل مواد55: سیستم های مونتاژ پیشرفته اغلب دارای سیستم های حمل و نقل مواد می باشند که در آن کارها از یک ماشین به ماشین دیگری منتقل می شوند. هنگامی که مراکز کاری از سطح اتوماسیون بالایی برخوردار باشند(برای مثال سیستم های روباتیک)، زمان های پردازش قطعی بوده و تغییر نمی کنند و در نتیجه سیستم حمل و نقل مواد نیز اتوماتیک خواهند بود. هنگامی که کارها به صورت دستی در مراکز کاری پردازش شوند گام سیستم حمل و نقل قابل تنظیم خواهد بود به سبب این که گام بستگی به زمان پردازش کارها دارد. سیستم حمل و نقل مواد منجر به وابستگی شدید میان زمان آغاز پردازش و زمان تکمیل پیش نیازهای کار مورد نظر می شود. علاوه بر این، حضور سیستم حمل و نقل فضای بافرها را محدود ساخته ولی به دنبال آن میزان موجودی نیم ساخته را کاهش می دهد.
زمان های آماده سازی به توالی56: برخی نویسندگان این محدودیت را به مدل های پردازش دستهای ارجاع می دهند. هر کار ممکن است به یک دسته تعلق داشته باشد. اگر کار های یک دسته یکی بعد از دیگری پردازش شوند، آماده سازی اضافی وجود ندارد. از طرف دیگر، اگر یک دسته متفاوت از کارها پردازش شود، یک هزینه آماده سازی وجود خواهد داشت. هر کار یک موعد تحویل دارد و ما می خواهیم کارها را برای کمینه سازی جریمه دیرکرد کل، زمانبندی کنیم. اگر مدت زمان آماده سازی یک کار علاوه بر وابسته بودن به ماشین، به کاری که بلافاصله قبل از آن تکمیل شده است نیز وابسته باشد، زمان آماده سازی وابسته به توالی در نظر گرفته خواهد شد. برای مثال عملیات ر نگ اغلب به تغییر رویه نیازمند می باشد. هر زمانی که رنگ جدیدی مورد استفاده قرار می گیرد، وسایل رنگ باید تمیز شوند. زمان تمیز کردن بستگی به رنگی که اخیرا استفاده شده است و همچنین رنگی که قرار است استفاده شود دارد. در عمل بهترین توالی، آن است که از رنگ های روشن به رنگ های تاریک حرکت کند، به این سبب فرآیند تمیز کردن ساده تر خواهد بود.
معیارهای ارز یابی عملکرد
جدول 2-3 بعضی از معیارهای به کار رفته در مسائل زمانبندی به ازای پارامتر γ نشان داده شده است.
جدول ‏23: نمایش بعضی از معیارهای به کار رفته در مسائل زمانبندی با پارامتر 
معیار
پارامتر 
حداکثر زمان تکمیل کارها
C max
حداکثر دیرکرد
L max
مجموع وزنی زمان تکمیل کارها
w j C j
مجموع وزنی زمان های جریان

این مطلب رو هم توصیه می کنم بخونین:   دانلود پایان نامه ارشد با موضوعevaluation، Technology
دسته‌ها: No category

دیدگاهتان را بنویسید