در مسئله JSP هر کار هر کدام از ماشين‌ها را تنها يک بار ملاقات مي­کند اما اين فرض در برخي از محيط­هاي توليدي نقض مي‌شود و کار ممکن است يک ماشين خاص را بيش از يک‌بار ملاقات کند. چنين مسئله­اي به مسئله زمان‌بندي کارکارگاهي برگشتي[1](RJSP) معروف مي‌باشد. مسئله RJSP در بسياري از صنايع توليدي به خصوص در صنايع با فناوري مدرن کاربرد دارد به عنوان مثال مي‌توان به صنايع ساخت تخته‌هاي مدار چاپي، ميکرو پردازنده‌ها، چيپ هاي حافظه، ريز کنترل کننده­ها و ديگر وسايل نيمه رسانا اشاره نمود

[1]Reentrant Job Shop scheduling Problem(RJSP)

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

هر ماشين در مسئله JSPرا مي‌توان با جريان­هاي ورود و خروج کار که در شکل 2- 1 نشان داده شده، مشخص کرد. همان‌طور که در شکل مشاهده مي­شود، ورودي به يک ماشين مي‌تواند کارهاي جديد باشند که اولين عمل پردازشي خود را بر روي ماشين انجام مي‌دهند و يا اينکه کارهاي نيمه ساخته‌اي باشند که چندين عمل پردازشي خود را به اتمام رسانده­ و سپس جهت پردازش وارد اين ماشين مي­شود. خروجي ماشين­ها نيز مي‌تواند، کارهاي تکميل شده باشد و يا به عبارت ديگر يک کار آخرين عمل پردازشي خود را بر روي ماشين انجام مي­دهد و يا اينکه يک کار نيمه ساخته مي‌باشد که يک يا چند عمل پردازشي آن باقي مانده است.

شکل 2- 1: گردش کار يک ماشين در محيط کارکارگاهي

فرضيات عمومي مسئله JSPبه شرح زير است :

• ماشين‌ها توانايي پردازش تنها يک کار را در هر لحظه دارند.
• انقطاع[1]وجود ندارد، يعني يک کار تا زمان تکميل شدن پردازش خود بر روي ماشين مربوطه باقي مي‌ماند.
• انصراف[2] وجود ندارد، بدين معني که اگر يک عمل از کاري پردازش شد، عمل­هاي بعدي کار نيز حتماً بايد پردازش شود.
• همه کارها در زمان صفر در دسترس و ماشين‌ها بيکار مي‌باشند.
• هر کار داراي مسير پردازش از پيش تعيين شده است و مسير پردازش جانشين براي آن‌ها وجود ندارد.
• محدوديت‌هاي تکنولوژيکي از پيش شناخته شده و تغيير ناپذير هستند.
• موجودي در جريان ساخت[3](WIP)به‌صورت نامحدود در نظر گرفته مي­شود.
• زمان آماده سازي[4] در زمان پردازش دخالت داده مي­شود.
• زمان پردازش عمل­ها مستقل از توالي کارها بر روي ماشين­ها مي‌باشد.
• زمان حمل و نقل بين ماشين‌ها در مقايسه با زمان پردازش ناديده گرفته مي­شود.
• تاريخ تحويل براي هر کار ثابت مي‌باشد و بعد از ورود به کارگاه غير قابل تغيير است.
• جريمه ديرکرد براي کارهايي که بعد از تاريخ تحويل کارگاه را ترک مي‌کنند، در نظر گرفته مي‌شود.
• حالت تصادفي وجود ندارد. بدين معني که زمان‌هاي پردازش، زمان‌هاي آماده سازي، زمان‌هاي ورود قطعات و تعداد کارها مقاديري قطعي دارند.
• ماشين‌ها در دوره برنامه‌ريزي پيوسته در دسترس هستند.
• از هر نوع ماشين تنها يکي موجود است.
• ماشين‌ها ممکن است بيکاري[5] داشته باشند.

اين فرضيات در اکثر مسائل JSP در نظر گرفته مي­شوند، با نقض هر يک از فرضيات بالا يک مسئله جديد از حالت کلاسيک به وجود خواهد آمد.

مسئله JSP در بسياري از صنايع توليدي که هر مشتري داراي سفارش يکتا و منحصر به فرد و داراي پارامترهاي خاص خود مي­باشد، کاربرد دارد. از ديگر کاربردهاي اين مسئله در صنايع توليدي و خدماتي مي‌توان به اين موارد اشاره کرد: توليد ريزتراشه‌هاي ويفر[6]در صنعت توليد نيمه‌هادي[7]، مراجعه بيماران به بيمارستان، مراجعه کنندگان يک اداره و خط مونتاژ توليد محصولات سفارشي.

[1] preemption

[2] cancellation

[3] Work In Process(WIP)

[4] setup time

[5] idle

[6] wafer(يک لايه سيليکوني که بر روي آن مدارهاي مجتمع جهت ايجاد يک تراشه قرار مي­گيرند)

[7] semiconductors fabrication facilities

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

نظريه زمان‌بندي اصولاً با مدل‌هاي زمان‌بندي سروکار دارد. اين نظريه بين زمان‌بندي و توسعه مدل‌هاي آن رابطه برقرار مي‌کند و به طور پيوسته آن‌ها را با مسائل نظري و عملي محک مي‌زند. اين نظريه همچنين شامل شيوه‌هاي متنوع و مختلفي است که در حل مسائل زمان‌بندي مفيد واقع مي‌شود. انتخاب شيوه مناسب به پيچيدگي مسئله، طبيعت مدل، انتخاب معيار کارايي و عوامل ديگر بستگي دارد.

در نظريه زمان‌بندي دو نوع محدوديت امکان پذيري در مسائل ظاهر مي‌شود. محدوديت‌ در دسترس‌پذيري منابع و محدوديت تکنولوژيکي که بايد ترتيب انجام کارها را در نظر بگيرد. هر جواب در مسئله زمان‌بندي به منزله يافتن راه حلي امکان‌پذير براي اين دو نوع محدوديت مي‌باشد، به طوري که حل هر مسئله زمان‌بندي پاسخي به اين دو سوال است: (1) کدام منبع براي انجام هر وظيفه تخصيص داده خواهد شد؟ (2) هر وظيفه چه وقت انجام خواهد شد؟ به عبارت ديگر، جوهره مسائل زمان‌بندي به تصميم گيري در مورد تخصيص منابع و توالي عمليات منحصر مي‌شود.

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

[1]scheduling

[2] Henry Gantt