حل مسئلۀ كارگاه جريان جايگشتي به وسيله تنظيمات درايه‌هاي ستوني در ماتريس زمان هاي پردازش

مسئله كارگاه جرياني جايگشتي يكي از مسائل مهم و به روز تحقيق در عمليات گسسته است. در اين مقاله آلگوريتم ابتكاري جديدي با استفاده از تنظيم درايه‌هاي ستوني ماتريس زمان‌ها براي حل مسئله كارگاه جرياني جايگشتي پيشنهاد مي‌شود. n كار روي m ماشين با زمان‌هاي قطعي پردازش مي‌شوند و هدف اصلي مي‌نيمم كردن زمان كل تكميل كارهاست. مسئله، در زمان چندجمله‌اي قابل حل نيست. مانند بيشتر روش‌هاي ابتكاري حل مسئله، ابتدا ترتيب اوليه مناسبي از دنباله كارها پيدا مي‌شود. براي اين منظور ماتريس چنان ساخته مي‌شود كه هر k ij نشان‌دهنده اندازه مناسب بودن جاي سطر قديم ام در مكان جديد ام باشد. سپس قضيه بلمن، اسوگبو و نابشيما مورد استفاده قرار مي‌گيرد. روش ارائه شده با آلگوريتم NEH كه بهترين روش شناخته و موجود است مقايسه مي‌شود. مقايسه روي مسائل محك و استاندارد تيلارد انجام مي‌گيرد. نتايج محاسباتي نشان مي‌دهند آلگوريتم ابتكاري بهتر از بعضي روش‌هاي پيشنهاد شده قبلي مي‌باشد و نسبت به بقيه در تعدادي از مثال‌هاي تيلارد برتر است. به عنوان نتيجه آلگوريتم ابتكاري تقريباً به خوبي NEH و اميدبخش مي‌باشد. بر اساس ساختار ارائه شده، آلگوريتم ابتكاري پيشنهادي مي‌تواند به خوبي نقش يك روش فراابتكاري را ايفا كند.