مسئله زمان­بندی جریان کاری^[1] (FSS) بدین صورت است که مجموعه­ای از کارها وجود دارد که بایستی بر روی مجموعه­ای­ از ماشین­ها پردازش شوند. در این مسئله m ماشین به صورت سری پشت سر هم قرار دارند که هر یک از کارها باید به ترتیب بر روی این ماشین­ها پردازش شوند. ترتیب پردازش کارها به گونه­ای است که ابتدا بایستی بر روی ماشین شماره 1، سپس بر روی ماشین شماره 2 و در نهایت بر روی ماشین آخر m پردازش شود. هر یک از کارها بایستی عمل پردازشی خود را بر روی هر یک از ماشین­های پردازشی جهت تکمیل کار به اتمام برساند.

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

مسئله جريان کاري غیرجايگشتي بدون بيکاري^[3] (NNPFSP) توسعه ای از مسئله در حالت جایگشتی است. در حالت جايگشتي ترتيب پردازش کارها بر همه ماشين ها يکسان است اما در حالت غير جايگشتي ترتيب پردازش کارها بر روي هر يک از ماشين ها مي تواند متفاوت باشد. حالت جايگشتي محدوديتي است که در آن خروج کالا از انبارهاي مياني بر اساس قاعده FIFO يا به عبارتي زودترين ورود و زودترين خروج مي باشد که اين فرض باعث مي شود تا کارها با يک ترتيب مشابه بر روي هر يک از ماشين ها پردازش شوند. اما در حالت غير جايگشتي چنين محدوديتي وجود ندارد و ترتيب پردازش کارها بر روي ماشين­ها مي­تواند متفاوت باشد.

مسئله مورد بررسی طبق نماد گذاری گراهام و همکاران به صورت نمایش داده می­شود. تابع هدف در نظر گرفته شده برای مسئله مورد بررسی، کمینه سازی بیشینه زمان تکمیل کارها بر روی ماشین­ها در نظر گرفته شده است.

از جمله مهمترین فرضیات در نظر گرفته شده برای مسئله می­توان به موارد زیر اشاره کرد:

ü مدت زمان بيکاری ماشین آلات برابر با صفر در نظر گرفته شده است.

ü حالت غیر جایگشتی برای پردازش کارها بر روی ماشین­ها در نظر گرفته شده است.

ü همزمان دو عمل از يک کار قابل انجام نيست.

ü انقطاع^[4]وجود ندارد، يعني يک کار تا زمان تکميل شدن پردازش خود بر روي ماشين مربوطه باقي مي‌ماند.

ü در هنگام انجام کارها انصراف^[5] وجود ندارد، بدین معنی که اگر یک عملیات از کاری مورد پردازش قرار گرفت، عملیات­های بعدی کار نیز حتماً می بایستی پردازش شوند.

ü مدت زمان پردازش هر کار مستقل از ترتيب انجام کارها است.

ü مدت زمان آماده سازي^[6] مستقل از ترتيب انجام کارها است و در مدت زمان پردازش کارها در نظر گرفته شده است.

ü مدت زمان حمل و نقل بين ماشين‌ها ناچيز است.

ü هر ماشين بیش از یک کار را به طور همزمان پردازش نمی­کند.

ü محدوديت‌هاي فني شناخته شده‌اند و تغيير ناپذیرند.

ü حالت تصادفي وجود ندارد. بدين معنی که زمان‌هاي پردازش، زمان‌هاي آماده سازي، زمان‌هاي ورود قطعات و تعدادکارها مقاديری قطعي دارند.

ü ماشين‌ها در دوره برنامه‌ريزي پيوسته در دسترس هستند.

این مساله برای اولین بار توسط نویسنده سایت مدلسازی و حل شده است. جهت اطلاع بیشتر در تماس باشید.

[1] Flow Shop Scheduling

[2]No-idle Permutation Flow Shop Problem (NPFSP)

[3]No-idle Non-Permutation Flow Shop Problem (NNPFSP)

[4] Preemption

[5] Cancellation

[6] Setup Time