1-1 روش‌هاي حل

روش‌هاي حل مسئله رامي‌توان به دو دسته کلي روش­هاي بهينه‌سازي و روش­هاي تقريبي تقسيم کرد. روش‌هاي بهينه‌سازي[1] منجر به پيدا کردن جواب بهينه مسئله مي‌شوند اما در مقابل در روش‌هاي تقريبي[2] جواب بدست آمده جوابي بهينه يا نزديک به بهينه مي‌باشد.

1-1-1 روش‌هاي بهينه‌سازي

در روش‌هاي بهينه‌سازي يا دقيق زمان مورد نياز براي حل با افزايش خطي ابعاد مسئله به‌صورت نمايي يا به‌صورت چند جمله‌اي با درجات خيلي بالا افزايش پيدا مي‌کند. اين افزايش زمان حل براي مسئله FJSP از شدت بيشتري برخوردار مي‌باشد. از جمله روش‌هاي بهينه‌سازي مي‌توان به موارد زير اشاره نمود:

• الگوريتم­هاي کارا[3]: الگوريتم­هاي کارا مسئله داده شده را به‌صورت بهينه در يک زمان چند جمله‌اي با توجه به ابعاد مسئله حل مي‌کنند. اين روش‌ها به سادگي جواب بهينه مسئله را از داده‌هاي اوليه و با به کار‌گيري مجموعه‌اي از قوانين ساده بدست مي­آورند.
• فرمول­بندي­هاي رياضي[4]: بسياري از محققان تاييد کرده‌اند که مسائل زمان­بندي مي‌توانند توسط روش‌هاي برنامه ريزي رياضي به‌صورت بهينه حل شوند. از جمله برنامه ريزي رياضي­هاي متداول براي حل مسئله FJSPمي­توان به برنامه­ريزي خطي عدد صحيح مختلط[5] (MILP) و برنامه­ريزي غيرخطي عدد صحيح مختلط[6] (MINLP) اشاره نمود.
• روش شاخه و کران[7]: يک روش مفيد براي حل مسئله استراتژي شمارش محدود جواب است که شاخه و کران ناميده مي‌شود. اين روش شامل دو مرحله اساسي مي‌باشد؛ شاخه[8] که عبارت است از تقسيم يک مسئله بزرگ به دو يا چند مسئله فرعي، و ديگري کران[9] مي‌باشد که محاسبه يک کران پايين براي جواب بهينه هر مسئله فرعي است. اين روش در نهايت منجر به پيدا کردن جواب بهينه مسئله در زماني کمتر از روش رياضي خواهد شد.

1-1-2 روش‌هاي تقريبي

روش‌هاي تقريبي براي مسائل با ابعاد بزرگ مناسب هستند. اگرچه اين روش‌ها رسيدن به جواب بهينه را تضمين نمي‌کنند، اما قادر به پيدا کردن جواب نزديک به بهينه در يک زمان محاسباتي متوسط را دارا مي‌باشند. از جمله روش‌هاي تقريبي مي‌توان به موارد زير اشاره نمود:

قوانين ارسال

قوانين ارسال به علت به‌کارگيري آسان و زمان محاسباتي کم يکي از روش‌هاي رايج براي حل سريع مسائل زمان‌بندي هستند. در اين روش از بين عمل‌هاي باقي مانده براي زمان­بندي بر روي يک ماشين عملي انتخاب مي‌شود که داراي بالاترين اولويت نسبت به بقيه است.

روش ابتکاري انتقال ايستگاه گلوگاه

روش SBH اولين بار توسط آدامز و همکاران در سال 1988 براي مسئله JSP توسعه داده شد که يکي از رويکردهاي ابتکاري موفق در مسئله JSP است. اين روش مسئله را به چندين زير مسئله تک ماشينه تجزيه مي‌کند و زمان‌بندي نهايي را با ثابت نگه‌داشتن تک تک ماشين‌ها بدست مي‌آورد. در اين روش در هر تکرار يک ماشين گلوگاه (بحراني) از بين ماشين‌هايي که هنوز زمان‌بندي نشده‌اند انتخاب شده و سپس زمان‌بندي اين ماشين با ثابت نگه‌داشتن کمان‌هاي فصلي[14] در گراف فصلي[15]انجام مي‌شود. 

هوش مصنوعي

هوش مصنوعي شاخه‌اي از علوم كامپيوتر است. هوش مصنوعي كامپيوترها را قادر مي‌سازد تا قابليت هوشمندانه انسان‌ها نظير ادراك، يادگيري، حل مسائل هوشمند، استدلال و... را داشته باشند. از روش­هاي هوش مصنوعي که براي حل مسئله بکار مي­روند مي­توان به شبکه­هاي عصبي[17]، سيستم­هاي خبره[18] و ارضاي محدوديت[19] اشاره نمود.

[1] optimization methods

[2] approximation methods

[3] efficient algorithms

[4] mathematical formulations

[5]Mixed IntegerLinear Programming (MILP)

[6]Mixed Integer Non-Linear Programming (MINLP)

[7] branch and bound techniques

[8]branch

[9]bound

[10] dispatching rules

[11] Shifting Bottleneck Heuristic(SBH)

[12] Artificial Intelligence (AI)

[13] local search methods and meta-heuristics

[14]conjuctive graph

[15]Disjunctive graph

[16]critical machine

[17]neural network

[18]expert system

[19]constraint satisfaction

روش‌هاي جستجوي محلي و فرا ابتکاري

از جمله روش­هاي جستجوي محلي و فرا ابتکاري براي حل مسئله مي‌توان به موارد زير اشاره کرد:

[1] Local Search (LS)

[2] Beam Search(BS)

[3] greedy random search

[4] Variable Neighborhood Search(VNS)

[5] Tabu Search(TS)

[6] Simulated Annealing(SA)

[7] Genetic Algorithm(GA)

[8]Particle Swarm Optimization(PSO)

[9] Ant Colony Optimization(ACO)