حل مسئله های برنامه ریزی در AI

حل مسئله های برنامه ریزی در AI

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

می توانیم روش مسیر بحرانی (CPM) را در این گراف به کار ببریم تا زمان شروع و پایان هر فعالیت را تعیین کنیم. مسیری در گراف که یک برنامه ریزی با ترتیب جزیی را نشان می دهد، یک دنباله مرتب خطی از فعالیت ها است که از start  شروع و به Finish ختم می شود.

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

کمیت LS – ES را شناوری یک فعالیت گویند. زمان های ES و LS برای تمام فعالیت ها یک زمان بندی را برای مسئله تشکیل می دهند.

فرمول های زیر، تعریف ES و LS را مشخص می کنند و بعنوان طرح کلی الگوریتم برنامه ریزی پویا برای محاسبه آنها عمل می کنند. A و B فعالیت هستند و A < B به معنای این است که A قبل از B اجرا می شود:

ES(Start) = 0

ES(B) = max _{AES(A) + Duration(A)}

LS(Finish) = ES(Finish)

LS(A) = min_B>A LS(B) – duration(A).

در این فرمول با صفرکردن ES(Start) شروع می کنیم. سپس به محض اینکه به فعالیتی مثل B رسیدیم که برای تمام فعالیت های بلافاصله قبل از B مقادیر، ES آنها مشخص شده اند، ES(B) را برابر با ماکزیمم زودترین زمانهای خاتمه فعالیت های بلافاصله قبل از B قرار می دهیم که زودترین زمان خاتمه یک فعالیت برابر با زودترین زمان شروع به اضافه مدت آن فعالیت است. این فرایند آنقدر تکرار می شود تا به هر ES مقداری نسبت داده شود. مقادیر LS به طریق مشابه محاسبه می شود، ولی باید از فعالیت Finish به عقب برگشت.

پیچیدگی الگوریتم مسیر بحرانی فقط O(Nb) است که N برابر با تعداد فعالیت ها و b حداکثر ضریب انشعاب به یا از فعالیت است. بنابراین با توجه به ترتیب جزیی روی فعالیت ها و عدم وجود محدودیت های منابع، یافتن کمترین مدت زمان بندی بسیار آسان است.

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