1-1. مقدمه
زمان‌بندی یکی از پرکاربردترین مفاهیم در سیستیم‌های صنعتی و برنامه‌ریزی تولید می‌باشد. پس از ارائه مفهوم برنامه‌ریزی تولید در دهه‌ی ۱۹۷۰ تحقیقات آکادمیک زیادی در زمینه‌ی زمان‌بندی خط تولید از دهه‌ی ۱۹8۰ انجام شد.
امروزه کارخانه‌های تولیدی با توجه به نقش تولید در بازاررقابتی، خود رادر محیطی کاملاً تغییریافته با گذشت زمان می‌بینند،ازجمله مهم‌ترین تغییری که در بازار می‌توان مشاهده کرد عبارتند از:
۱- افزایش تنوع تقاضای مشتریان
۲- افزایش درک وآگاهی عمومی مشتریان نسبت به شرایط بازار.
۳- تغییر الگوهای هزینه‌ای.
۴- تغییر انتظارات اجتماعی.
۵- دشواری در تأمین منابع و هزینه‌ها.
با توجه به تغییرات نام برده در بازارهای رقابتی، شرکت‌های تولیدی سعی در تغییر استراتژی خود از تولید انبوه به سمت تولید دسته‌ای و بهنگام با هدف انعطاف‌پذیری جهت دریافت سفارشات مشتری دارند.
دراین فصل ابتدا مروری کلی بر انواع مسائل زمان‌بندی و تعریف ازمفاهیم اولیه زمان‌بندی خواهیم پرداخت سپس نگرشی بر روش‌های بهینه‌سازی چندهدفه خواهیم داشت و در ادامه به بیان مسئله‌ی مورد بحث‌مان در این تحقیق وهمچنین روش‌های حل آن خواهیم پرداخت. و در پایان این فصل به بیان اهداف- ضرورت انجام تحقیق و متدلوژی این تحقیق اشاره خواهیم کرد.
 
 
1-2.تعریف زمان‌بندی
زمان، همیشه به‌عنوان یک محدودیت مهم واساسی در مسائل بهینه‌سازی مطرح بوده است.
به عنوان تعریف کلی می‌توان زمان‌بندی را تعیین توالی یا ترتیب انجام کارها برای ارضای نیازمندی‌ها و نیل به اهداف مشخص با توجه به محدودیت‌های موجود دانست. و به طور دقیق‌تر می‌توان، زمان‌بندی را تخصیص منابع موجود در طول زمان برای اجرای مجموعه‌ای از وظایف تعریف کرد.
این تعاریف دو مفهوم کلی را در پی دارند: اول اینکه زمان‌بندی نوعی تصمیم‌گیری است که در جریان آن برنامه‌ی زمانی را تعیین می‌کنند که پیامد آن را می‌توان در تصمیم‌گیری‌های دیگر نیز استفاده کرد و از سوی دیگر مبحثی نظری است که مجموعه‌ای از اصول- مدل‌ها- روش‌ها و نتایج منطقی را در بر می‌گیرد.
1-2-1. ضرورت زمان‌بندی تولید
با توجه به پیشرفت روزافزون صنعت، منابع موجود برای پاسخ‌گویی به صنایع حالت بحرانی به خود می‌گیرند. از جمله‌ی این منابع بحرانی عبارتند از: ماشین‌آلات- نیروی انسانی و سایر تسهیلات.
زمان‌بندی روی چنین منابع بحرانی موجب ارتقاء کارایی، بهره‌وری ودر نهایت سودآوری بیشتر صنایع می‌شود. از جمله فعالیت‌هایی که در زمینه‌ی زمان‌بندی منابع انجام می‌شود عبارتند از: ترسیم نمودارها و دیاگرام‌های ساده تا کار با الگوریتم‌ها و نظریه‌های پیچیده.
یک برنامه‌ی زمان‌بندی، زمان شروع پردازش هر‌کار روی هر ماشین و زمان پایان هر کار روی هر ماشین را تعیین کرده، یعنی نتیجه‌ی فرآیند زمان‌بندی یک جدول زمانی برای کارها و ماشین‌هاست که در آن زمان شروع هر کاری باید بزرگ‌تر یا مساوی با زمان ورود آن کار به کارگاه باشد و از طرفی اگر برای هر کار موعد تحویل مقرر شده باشد، آنگاه زمان پایان آخرین فرآیند مربوط به آن سفارش نباید از موعد تحویل مقرر تجاوز کند.
1-2-2. اهداف زمان‌بندی
معمولاً اهدافی که مراکز صنعتی در زمینه‌ی زمان‌بندی فعالیت‌هایشان دنبال می‌کنند شامل دست‌یابی به موعد تحویل سفارشات (تولید بهنگام)[1] یا حداقل سازی زمان فعالیت خط تولید و یا حداکثرسازی تعداد خروجی و بهره‌وری بیشتر از خط تولید و . می‌باشند که در جدول ۱-۱ تعدادی از این اهداف و معیارها معرفی می‌شوند که گاهی اوقات تعدادی از این اهداف در تناقض با هم‌دیگر می‌باشند.
جدول ۱-۱.اهداف رایج در زمان بندی

Notation
discription
C max
Maximum completion time
F max
Maximum flow time
L max
Maximum lateness
T max
Maximum tardiness
E max
Maximu earliness
 
Total completion time
 
Total weighted completion time
 
Total flow time
 
Total weighted flow time
 
Total tardiness
 
Total weighted tardiness
 
Number of tardy job
 
Total weighted number of tardy job
 
1-2-3.تعریف برخی از مفاهیم اولیه در زمان‌بندی
زمان پردازش عملیات: ( )
با توجه به موضوع تحقیق ما که در مورد زمان‌بندی یک ماشین با قابلیت پردازش دسته‌ای از کارها است و کارها متعلق به خانواده‌های متفاوت می‌باشند، زمان پردازش به‌صورت زیر تعریف می‌شود:
زمان پردازش کار jام متعلق به خانواده‌ی iام که در دسته‌ی نوبت kام پردازش می‌شود=
زمان دسترسی به کار (rj):
زمان ورود یک کار به کارگاه برای دریافت سرویس از ماشین که این زمان در واقع زودترین زمان ممکن برای ارائه سرویس به کار مدنظر توسط ماشین می‌باشد.
موعد تحویل(dj):
زمانی که تولیدکننده متعهد است تا به مشتری سرویس منظوره را ارائه کند. ارائه خدمت به مشتری پس از موعد تحویل برای تولید‌کننده جرایمی را به دنبال دارد.
زمان تکمیل کار(cj):
زمانی که آخرین فرآیند پردازش روی کار j انجام می‌شود یعنی بعد از این زمان کار j آماده‌ی تحویل به مشتری است.
مدت جریان ساخت (fj):مدت زمانی که کار jام در داخل سیستم تولید قرار دارد که از رابطه ی زیر بدست می‌آید.  fj = cj – rj
تأخیر(Lj): فاصله‌ی بین زمان تحویل یک کار و موعد تحویل آن را تأخیر می‌نامند که از رابطه‌ی Lj=cj-dj بدست می آید که اگر مقداری مثبت باشد نشان از دیرکرد و اگر منفی باشد نشان از زودکرد تحویل می‌باشد.
دیرکرد (Tj): دیرکرد کار j  از رابطه‌ی روبرو بدست می‌آید:
یعنی اگر زمان تکمیل بعد از موعد تحویل کاری باشد دیرکرد در واقع همان تأخیر است در غیر این صورت مقدار صفر را می‌گیرد.
زودکرد (Ej): یعنی اگر زمان تکمیل قبل از موعد تحویل کاری باشد زودکرد در واقع قدرمطلق تأخیر است در غیر این صورت مقدار صفر را می‌گیرد.
1-3.ضرورت بررسی مسائل و روش‌های بهینه‌سازی چند هدفه
بسیاری از مسائل دنیای واقع، به صورت بهینه سازی چند هدف به‌طور همزمان می‌باشند زیرا متغیرها و اهداف متضاد به‌طور واقعی در ذات این مسائل می‌باشند، یعنی بهبود در یکی از اهداف موجب بدتر شدن در هدف دیگر خواهد شد. بهینه‌سازی این‌گونه مسائل کاملاً متفاوت با مسائل تک‌هدفه خواهد بود یعنی الگوریتم‌های بهینه‌سازی تک‌هدفه، یک حل بهینه را با توجه به تک هدف موجود بدست می‌آورند درحالی‌که درمسائل چندهدفه (با وجود چند هدف متضاد) قادر به بدست آوردن یک حل بهینه مجزا نخواهیم بود، بنابراین طبیعی است که باید به دنبال مجموعه‌ای از حل‌های غلبه نشده مؤثر با توجه به فضای حل برای این نوع از مسائل باشیم تا در اختیار تصمیم گیرنده قرار داده تا با توجه به معیارها و استدلال‌های خود بتواند از میان حل‌های نامغلوب متناهی که در اختیار دارد یک حل متناسب با معیارهایش را انتخاب کند.
 
 
1-3-1.تعاریف مرتبط با مسائل چند هدفه
مدل چند هدفه:
یک مسئله تصمیم‌گیری چندهدفه در حالت کلی به زبان ریاضیات به‌صورت زیر تعریف می شود:
s,t: xϵs
یعنی در فضایی شدنی x هر حل x دارای n ارزش به ازای n هدف خواهد بود که با مقایسه‌ی این مقادیر بدست آمده از اهداف می‌تواند رابطه‌های مغلوب و نامغلوب رابرا‌ی حل‌های مختلف تعریف کرد.
مجموعه‌ی حل‌های نامغلوب[2]:
برای یک مسئله Min سازی، حل x، حل y را غلبه می‌کند اگر و فقط اگر:
بنابراین مجموعه‌ی حل‌های نامغلوب بهینه به مجموعه‌ای از حل‌ها گفته می‌شوند که خود حل‌های دیگر را غلبه می‌کنند ولی توسط هیچ حلی غلبه نمی‌شوند. در شکل ۱-۱  دایره‌های تیره مجموعه‌ی حل‌های نامغلوب بهینه‌اند.[3]
 
شکل ۱-۱.مجموعه حلهای نامغلوب بهینه