زمان­بندی[1]، فرایند تخصیص منابع به فعالیت­ها با درنظر گرفتن دوره­های زمانی مربوط به آنها به منظور بهینه­سازی یک یا چند هدف می­باشد. این فرایند به عنوان یک فرایند تصمیم­گیری مبنای کار بسیاری از صنایع تولیدی و خدماتی محسوب می­شود. زمان­بندی کارای فعالیت­ها زمینه­ساز بهبود عملکرد سیستم­های تولیدی می­باشد و ضرورتی برای بقا در فضای رقابتی بازار به ­شمار می­آید.

تئوری زمان­بندی در ارتباط با مدل­های ریاضی است که فرایند زمان­بندی را تشریح می­کنند. چشم­انداز تئوریک یک نگرش کمی برای بدست آوردن ساختار مسائل در چهارچوب مدل­های ریاضی به­دست می­دهد که این امر با تشریح منابع و فعالیت­ها و تبدیل اهداف تصمیم­گیری به یک تابع­ هدف، صورت می­پذیرد. عمل زمانبندی در یک سازمان از مدل ها و روش های ریاضی و یا روش های ابتکاری برای تخصیص منابع محدود به کارهای در حال جریان استفاده می کند. اهمیت توالی ماشین های موازی، با هدف متمرکز بر دیرکرد از آن جهت مورد توجه است که در محیط کسب و کار حاضر، رقابت شرکت های تولیدی از طریق قابلیت آنها برای پاسخگویی سریع به تغییرات سریع در زمینه تجارتی و تولید محصولات با کیفیت بالاتر و هزینه های کمتر تعیین می شود. در نتیجه، منابع، فعالیت­ها و توابع هدف عناصر کلیدی مدل­های زمان­بندی محسوب می­شوند.

منابع بر حسب قابلیت­های کمی و کیفی خود مشخص می­شوند، بطوریکه هر مدل نشان­ دهنده نوع و میزان منابع بکار رفته در آن می­باشد. از سوی دیگر، فعالیت­ها بر حسب اطلاعاتی از قبیل منابع مورد نیاز، مدت زمان انجام، زمان آغاز و زمان پایان آنها توصیف می­شوند. توابع هدف نیز دربرگیرنده هزینه­های سیستم برای اجرای تصمیمات مربوط به تخصیص منابع به فعالیت­ها می­باشند. تصمیمات عمده در فرایند زمان­بندی شامل بهره­برداری کارا از منابع، پاسخگویی سریع به تقاضا و انطباق دقیق زمان­های تحویل با موعد­های تحویل تعیین­شده می­شوند. شرکت های تولیدی در تلاش هستند تا این قابلیت ها را از طریق اتوماسیون و مفاهیم خلاق مانند تولید به موقع[2] (JIT) ،

 پاسخگوی سریع[3] (QR) ، تکنولوژی گروهی[4] (GT) و مدیریت کیفیت جامع[5] (TQM) بدست آورند[58].

این مفاهیم ( برای مثال JIT و GT ) به بسیاری از شرکت ها در بدست آوردن سود اقتصادی کمک کرده است. در سیسستم های JIT کار نباید نه زودتر و نه دیرتر تکمیل شود، که به مسائل زمانبندی با هزینه های زودکرد و دیرکرد و تخصیص موعدهای تحویل منجر می شود. در یک بازار رقابتی دیرکرد کارها با توجه به موعد تحویل آنها یک مقیاس عملکرد بسیار مهم برای محیط های تولید متنوع است.

مسائل با تعیین موعد تحویل در 25 سال گذشته بعلت روشهای جدید مدیریت مانند مفاهیم JIT مورد توجه بسیار قرار گرفته است. چنگ که کمک زیادی به مسائل زمانبندی و تخصیص موعد تحویل کرد بیان می کند که تکمیل یک کار زودتر از موعد تحویل به معنی تحمیل هزینه های نگهداری موجودی غیر ضروری است ، در حالیکه تکمیل یک کار دیرتر از موعد تحویل منجر به جریمه های قراردادی و از دست دادن اعتبار مشتری می شود[33].

بطور جالب توجه هدف مسئله حداقل دیرکرد و زودکرد[6] (ET) کاملا با سیاست کنترل تولید JIT مطابقت دارد.مسئله ماشین های موازی از دو دیدگاه تئوری و عملی دارای اهمیت می باشند. از دیدگاه تئوری به این خاطر که تعمیمی از حالت تک ماشینه می باشد و از دیدگاه عملی به این جهت که در دنیای واقعی بسیارمعمول است مورد توجه قرار گرفته شده است.

مسئله به کارگیری ماشین های موازی از آنجا مورد توجه است که اگر زمانبندی روی یک ماشین منجر به هزینه زیادی شود ممکن است در نظر گرفتن ماشین های بیشتر سبب کاهش هزینه شود. ضمن این که مقدار دیرکرد یا زودکرد نیز می تواند با افزایش تعداد ماشین ها کاهش یابد. در این شرایط هزینه به کارگیری ماشین یا نگهداری ماشین اضافه می شود که با حل مسئله بهینه سازی می توان تعیین کرد چه ماشین هایی به کار گرفته شوند و کدام کارها با چه توالی روی این ماشین ها انجام شود.

در عمل، زمانبندی ها با استفاده از الگوریتم های زمانبندی یا قوانین بر پایه دانش ایجاد می شوند. الگوریتم های زمانبندی ، زمانبندی را توسعه می دهد که یک معیار اندازه گیری مانند حداقل کردن انحراف موعد تحویل، حداقل جریمه دیرکرد یا حداقل حداکثر دیرکرد را بهینه می کند. انگیزه بسیاری از توسعه­ها و پیشرفت­های علمی در حوزه زمان­بندی برخاسته از محیط­های صنعتی است و به­طور طبیعی در بیان مفاهیم زمان­بندی از واژه­های بکار رفته در صنعت استفاده می­شود. به­ همین خاطر منابع با عنوان ماشین به­کار می­روند و به هر کدام از فعالیت­ها، کار اطلاق می­شود بطوریکه کارها اغلب به وسیله مجموعه­ای از ماشین­ها در ایستگاه­های مختلف کاری با توالی مشخص پردازش می­شوند.

بطور کلی، مسائل زمان­بندی به صورت مسائل بهینه­سازی محدودیت­دار بیان می­شوند که در آنها به بررسی تصمیمات مربوط به تخصیص ماشین­ها وتوالی پردازش کارها پرداخته می­شود. درحالتی که تنها یک ماشین موجود است، تعیین توالی پردازش کارها یک برنامه زمانی کامل را تشکیل می­دهد. مسائل تک­ماشینه با وجود سادگی ذاتی، سنگ­بنای درک فراگیر مفاهیم زمان­بندی را تشکیل می­دهند. درمقابل، زمان­بندی مسائل چند­ماشینه شامل سیستم­های موازی، سیستم­های متوالی و سیستم­های ترکیبی می­باشد. در سیستم­های موازی، هر یک از کارها با انجام یک عملیات همانند مسائل تک­ماشینه بر روی یکی از ماشین­های موازی موجود پردازش می­شوند و به­ دنبال آن تخصیص ماشین­ها به­ کارها موضوعیت پیدا می­کند. این درحالی است که در سیستم های متوالی و ترکیبی، کارها با انجام چند عملیات بر روی ماشین­ها پردازش می­شوند و مسائل مربوطه ساختار نسبتا پیچیده­تری را تجربه می­کنند.

در این تحقیق، به بررسی مسئله زمان­بندی ماشین­های موازی نامرتبط[7] به عنوان دسته مهمی از مسائل زمان­بندی که دارای اهمیت فراوان از نقطه­نظر تئوری و تجربی است، پرداخته می­شود. مسائل ماشین­های موازی نامرتبط حالت عمومیت­یافته مسائل تک­ماشینه و حالت خاصی از مسائل ماشین­های متوالی منعطف محسوب می­شوند. تکنیک­های به­کار رفته در بهینه­سازی این نوع مسائل با اعمال رویه­های ترکیبی در مسائل زمان­بندی پیچیده­تر استفاده می­شوند. در بخش­های آتی این فصل، شرح تفصیلی مسئله مورد بررسی این تحقیق ارائه می­شود.

[1] Scheduling

[2] Just In Time

[3] Quick Response

[4] Group Technology

[5] Total Quality Management

[6] Earliness-Tardiness

[7] Unrelated Parallel Machine Scheduling