تعداد مراحل تولید (یک مرحله ای - چند مرحله ای)
روش تولید(سری - مونتاژ -کلی)
محدودیت ظرفیت یا منابع (محدود- نامحدود)
تعداد و شرح تقاضای هر یک از محصولات
نرخ تقاضا (یکنواخت - پویا و احتمالی)
کمبود موجودی (قابل جبران، غیر قابل جبران)
هزینه نگهداری و متغیر تولید
متغیر تصمیم گیری (تعیین زمان شروع عملیات)
مسائل زمانبندی را به کمک سه پارامتر α | β | γ دسته بندی می کنند . پارامتر α نشان دهنده محیط های کار و یا ترکیب ماشین ها است. پارامتر β بیان کننده محدودیت های مربوط به کارهاست و پارامتر γ نشان دهنده معیارهای بهینگی و اهداف مساله می باشد. در جدول ذیل برخی از محیط های کار در مسائل زمانبندی به ازای پارامتر α نشان داده شده است.
جدول ۲‑۱: نمایش برخی از محیط های مختلف کار در مسائل زمانبندی با پارامتر α
| محبط زمانبندی کارها | پارامنر α |
| مساله تک ماشینه | a =1 |
| مساله ماشین های موازی با m ماشین | a = P m |
| مساله گردش ماشین با m ماشین | a = F m |
| مساله کار کارگاهی با m ماشین | a = J m |
| مساله کارگاه باز با m ماشین | a = O m |
مدل های تک ماشینه[۳۴]
در این مسائل تنها یک ماشین موجود است و کارها نیاز به دریافت خدمت از این ماشین دارند. در هر زمان یک کار به وسیله ماشین پردازش می شود. هر کار یک زمان پردازش و یک موعد تحویل دارد و ممکن است مشخصه های دیگری مانند اولویت، بریدگی و یا زمان حمل نیز در این مساله مطرح باشد. همچنین ممکن است یک تابع جریمه[۳۵] برای کارهایی که از موعد تحویل انحراف دارند، در مدل مورد استفاده قرار بگیرد. در این مسائل متداول ترین هدف ، ترتیب دهی کارها روی ماشین به منظور حداقل کردن جریمه دیر کرد است. سیستم های تولیدی بسیاری از نوع سیستم های تولیدی تک ماشینه می باشند. به عنوان مثال، اگر در محیطی که شامل چندین ماشین است، گلوگاهی رخ دهد آنگاه توالی کارها در گلوگاه به طور کلی بیان کننده عملکرد کلی سیستم خواهد بود. در این حالت تمامی عملیات پس از زمانبندی گلوگاه زمانبندی خواهند شد. چنین رویکردی دلالت بر در نظر گرفتن مساله اصلی به صورت مساله تک ماشین دارد. مدل های تک ماشین همچنین در رویکرد های تجزیه کاربرد دارند که در آن مسائل زمانبندی در محیط های پیچیده به چندین مساله زمانبندی تک ماشین تبدیل می شوند. مدل های تک ماشین با محدودیت ها و توابع هدف مختلفی در نظرگرفته شده اند. نتایج به دست آمده منجر به ایجاد مجموعه ای از قواعد گردیده است که نتیجه آن ها ایجاد جواب بهینه در محیط های تک ماشینه می باشد. برای مثال قانون زود ترین موعد تحویل[۳۶] که کارها را به ترتیب صعودی موعد تحویل زمانبندی می کند منجر به حداقل شدن حداکثر دیرکرد در میان تمام کارها می شود. قانون کمترین زمان پردازش[۳۷] که کارها را به ترتیب صعودی زمان پردازش زمانبندی می کند منجر به حداقل شدن تعداد کارهای در انتظار پردازش می شود.
مدل های ماشین موازی[۳۸]
در این مدل ها تعدادی ماشین مشابه در دسترس بوده و کارها می تواند روی هر کدام از آن ها پردازش شود. کارها می توانند بین خود وابستگی داشته باشند، به این معنی که در یک توالی، کار بعدی نمی تواند پردازش شود مگر آن که کار قبلی کاملا پردازش شده باشد. هدف این مسائل می تواند کمینه سازی حداکثر زمان تکمیل کارها باشد. ماشین های موازی تعمیمی بر مدل های تک ماشین می باشند. بسیاری از محیط های تولیدی از چندین مرحله یا مرکز کاری تشکیل شده اند درحالی که هر یک از آن ها دارای چندین ماشین به صورت موازی می باشند. ماشین های موجود در یک مرکز کاری می توانند یکسان باشند. در این حالت هر لحظه که کار وارد سیستم شود امکان پردازش آن بر روی هر یک از ماشین های در دسترس فراهم خواهد بود. مدل های ماشین های موازی نیز مانند مدل های تک ماشین از این جهت دارای اهمیت می باشند که اگر در سیستم های تولید چند مرحله ای یک مرکز کاری خاص به صورت گلوگاه عملی کند، آنگاه زمانبندی در مرکز کاری مورد نظر تعیین کننده عملکرد کلی سیستم خواهد بود. در این صورت گلوگاه می تواند به صورت مجموعه ای از ماشین های موازی در نظر گرفته شده و به تنهایی به صورت یک مساله مجزا مورد تجزیه و تحلیل قرارگرفته شود. در بعضی از موارد ماشین های موازی ممکن است یکسان نباشند. در واقع در این حالت برخی از ماشین ها قدیمی تر از بقیه هستند و با سرعت پایین تری عمل می کنند و یا ممکن است ماشینی بهتر نگهداری شده باشد و بتواند کار را باکیفیت بالاتری انجام دهد. در این صورت برخی از کارها ممکن است بر روی هر یک از m ماشین موازی پردازش شوند درحالی که بقیه ممکن است تنها بر روی مجموعه خاصی از m ماشین پردازش کردند.
مدل های جریان کارگاهی[۳۹]
در این مدل ها کارها روی چندین ماشین در یک توالی یکسان[۴۰] پردازش می شوند. زمان پردازش هر کار روی هر ماشین ممکن است متفاوت باشد. هدف می تواند حداقل کردن زمان مورد نیاز برای تکمیل همه کارها باشد که حداکثر زمان تکمیل کارها (زمان ساخت) نامیده می شود. در بسیاری از محیط های تولیدی یا مونتاژ، کارها دارای چندین عملیات می باشند که معمولا باید بر روی چندین ماشین مختلف پردازش شوند. اگر مسیر همه کارها یکسان باشد (یعنی همه کارها ماشینهای یکسانی را در ترتیب یکسانی بازدید کنند)، چنین محیطی به عنوان محیط جریان کارگاهی در نظر گرفته می شود. در این محیط ماشین ها پشت سرهم قرارگرفته اند و هنگامی که زمان پردازش کاری بر روی ماشین خاصی تکمیل می شود وارد صف ماشین بعدی می گردد. ترتیب کارها از ماشینی به ماشین دیگر ممکن است متفاوت باشد به این سبب که کارها میان ماشین ها ممکن است دوباره مرتب شوند. با این وجود، اگر سیستم حمل ونقل مواد، کارها را از یک ماشین به ماشین بعدی منتقل کند، در این صورت توالی یکسانی از کارها در کل سیستم برقرار خواهد بود. در برخی از سیستم های جریان کارگاهی، هنگامی که کاری به پردازش بر روی ماشین خاصی نیاز نداشته باشد، از ماشین مورد نظر عبور کرده و جلوتر از کارهایی که پردازش شده اند و یا منتظر پردازش در آن مرحله هستند قرار می گیرد. برخی از سیستم های جریان کارگاهی در چنین حالتی امکان عبور کردن کار از ماشین را نمی دهند. مدل جریان کارگاهی انعطاف پذیر تعمیمی بر مدل جریان کارگاهی میباشد که از چندین مرحله به صورت سری تشکیل شده و هر مرحله دارای تعدادی ماشین به صورت موازی می باشد. کارها در هر مرحله بر روی یکی از ماشین های موازی پردازش می شوند.
این مسئله یک مدل چند ماشینی است که به صورت سری در یک کارگاه وجود دارند. فرض سری بودن ماشین آلات ، به دنبال خود فرض چند مرحله ای بودن کار ها را ایجاب می کند. این نکته بدین معناست که بین هر کار و هر یک از عملیات تشکیل دهنده فرایند آن تفاوت قائل شویم [۴۶،۴۷].
کار ها به صورت مجموعه ای از عملیات در نظر گرفته می شود که ساختار تقدمی خاص دارد، به ویژه هر یک از عملیات به جز مورد اول دقیقا یک مورد عملیات مقدم مستقیم و هر یک از عملیات بجز مورد آخر دقیقا یک مورد فعالیت موخر مستقیم دارد . این رابطه تقدم برای کار i در شکل ۲-۱ نشان داده شده است.
شکل ۲‑۱: رابطه تقذم برای n کار
مسائل جریان کارگاهی یک کلاس مشخص از مسائل زمانبندی کارگاهی هستند . که در آن n کار (i=1,..,n) وجود دارد که باید به شرح زیر روی m ماشین انجام شوند (j=1,…,m). کار A عبارت است از m عمل ، j امین عمل از هر کار باید روی ماشین j پردازش شود و زمان پردازش Pij را دارا می باشد . کار A می تواند فقط روی ماشین j شروع شود اگر عمل های آن روی ماشین (j-1) تکمیل شده باشند و اگر ماشین j بیکار باشد. زمان تکمیل شدن کار i، هنگامی است که زمان آخرین عمل Ci تکمیل شود. این مسئله در مقالات (مجلات) مشخص شده است و به صورت α|β|γ ثبت است . یک مثال از Flow Shop با سه کار و با داده های به شرح زیر را در شکل۲-۲ مشاهده می کنید :
شکل ۲‑۲: مساله ۳ کار
شکل ۲-۳ و شکل ۲-۴ دو زمانبندی امکان پذیر را برای این مثال نشان می دهند . ملاحظه میکنید که هر دو زمانبندی ترتیبی از کارهای مختلف بر روی ماشین ها هستند . برای مورد اول ما Cmax=9 و ۱۸=Ci∑ را داریم . در مورد دوم ما Cmax=8 و Ci=21∑ را داریم. ملاحظه می کنید که در نمونه اول Ci∑ نسبت به Cmax بهتر است در حالی که این در نمونه دوم بر عکس می باشد. این مثال به این نکته اشاره دارد که اسباب خیلی زیاد به تابع هدف وابسطه اند.
شکل ۲‑۳: نمونه اول زمانبندی
شکل ۲‑۴: نمونه ای دیگر از زمانبندی
در برخی از مقالات با کمی تغییر در مساله جریان کارگاهی تعاریف دیگری نیز مطرح شده، در ادامه به ارائه یکی از این تعاریف می پردازیم:
در ساخت و مونتاژ وسائل زیادی، تعدادی از عملیات در هر کار باید انجام شود. اغلب این عملیات باید در همه کارها به همان ترتیب که اشاره شده پردازش شوند. این ماشین های فرضی به صورت سری تنظیم شده اند، و محیط به عنوان جریان کارگاهی ارجاع داده شده است. با فرض زمانبندی مسائل جریان کارگاهی کلاسیک که هر کار فقط یک بار هر ماشین را ملاقات می کند گاهی اوقات در عمل نقض شده است. یک نمونه جدید از کارگاه صنعتی ، کار بازگشتی[۴۱] است که کار ماشین های معین را بیش از یک بار ملاقات می کند .
در شکل ۲-۵ قاعده جانسون برای مسئله Flow shop را مشاهده می کنید:
شکل ۲‑۵: قاعده جانسون
