خودم ی چیزایی پیدا کردم میذارم اگه کسی خواس بعدا
رويكردهاي ابتكاري براي زمانبندي:
يك روش ابتكاري يا هيورستيك در واقع يك قانون سرانگشتي است;يعني قاعده اي است كه بيشتر مبتني بر تجربه مي باشد تا مبتني بر تئوري دقيق.
به تجربه ثابت گرديده است مه روش هاي ابتكاري نيازهاي كاربر را در زمينه حل مساله براورده مي سازد .به عبارت ديگر هر چند اثبات دقيق و تضمين كافي براي اينكه يك روش ابتكاري به جواب بهينه برسد وجود ندارد,با اين حال اين روش ها كارايي خود را در دستيابي به جواب بهينه يا نزديك به بهينه نشان داده اند .
مزيت روش هاي ابتكاري,سادگي عمليات و كاهش محاسبات در انها مي باشد,به طوريكه كاربر,فاصله گرفتن از جواب بهينه را(تا حدي معقول)به ازاي كاهش محاسبات و حل سريعتر مساله قبول مي كند.همچنين روش هاي ابتكاري از جمله مهم ترين روش هايي هستند كه در حل مسائلي كه راه حلي قطعي براي انها وجود ندارد از كارايي بالايي برخوردار هستند(در اين حالت كاهش زمان حل در مقابل راه حل ارائه شده از اهميت كمتري برخوردار است .)در مسائل واقعي با ابعاد بزرگ دستيابي به جواب بهينه بسيار دشوار مي باشد مگر با بكارگيري روش هاي شمارشي مانند شاخه و كران.
اگر زمان بندي بهينه در زماني معقول بدست نيايد,دانش و تجربه سيستم بكار گرفته مي شود تا جوابي بدست ايد كه هرچند بهينه نيست وليكن از متوسط جواب ها بهتر است.
در اين قسمت ,ان دسته از روش هاي ابتكاري يا هيورستيك را بررسي مي كنيم كه بدين نحو عمل مي كنند.
همچنين لازم به ذكر است كه عمده ترين مشكل روش هاي هيوريستيك اين است كه ممكن است براي مسائل بزرگ,زمان محاسباتي بالايي روي كامپيوتر نياز داشته باشند.
روش ابتكاري”كوتاهترين زمان پردازش(SPT):“
قاعده SPT برحسب معيارهاي خاصي از عملكرد,جواب بهينه را ارائه مي دهد.در اين روش,ابتدا كارها بر حسب زمان فرايند,به ترتيب صعودي مرتب مي شوند,يعني كار با كوتاهترين زمان فرايند دراول صف قرار ميگيرد . برنامه زمانبندي كه با استفاده از اين قاعده توسعه مي يابد,متوسط زمان جريان مواد در سيستم را كمينه مي سازد.
روش ابتكاري SPT بر حسب معيارهاي ذيل,زمانبندي بهينه را براي سيستم هاي تك ماشيني ارائه مي دهد :
n/1//c(متوسط زمان تكميل را كمينه مي كند )
)n/1//wمتوسط زمان انتظار را كمينه مي كند)
n/1//L(متوسط زمان تاخير يا مغايرت را كمينه مي كند )
n/1//N[SUB]U[/SUB](متوسط كارهاي ناتمام را كمينه مي كند)
n/1//N[SUB]W[/SUB](متوسط كارهاي در انتظار ميان ماشين ها را كمينه مي كند)
كانوي و ماكسول عملكرد (SPT)را در يك سيستم mماشيني مورد بررسي قرار دادند.انها دريافتند كه در سيستم چند ماشيني قاعده ,sptمزيت خود را در بيشينه سازي خروجي كه در حالت تك ماشيني از ان برخوردار بود,همچنان حفظ كرده و حتي وجود داده هاي ناقص در مورد زمان هاي فرايند نيز اثر زيادي بر عمليات sptنخواهد داشت .
هنگام استفاده از قاعده sptبراي زمان بندي توليد در حالت چند ماشيني,زمان فرايند براي يك كار عموما به صورت مجموع زمان هاي فرايند براي ان كار روي كليه ماشين ها محاسبه مي شود.در اين سيستم كليه ماشين ها يك برنامه زمان بندي مشابه خواهند داشت.با اين وجود,كارها مي توانند روي يك ماشين,برحسب زمان فرايند براي هر كار روي ان ماشين,زمان بندي شوند .
روش ابتكاري EDD :
طبق اين روش,كارها به ترتيب موعد تحويلشان تحت عمليات قرار مي گيرند. يعني ابتدا كاري كه زودترين موعد تحويل را دارد تحت عمليات قرار مي گيرد,سپس كار بعدي با زودترين موعد تحويل در بين بقيه كارها و الي اخر.براي مساله تك ماشيني,با يك توالي به صورت ذيل حداكثر تاخير كمينه مي گردد:
d[SUB]i(1)[/SUB]<=d[SUB]i(2)[/SUB]<=d[SUB]i(3)[/SUB]<=….<=d[SUB]i

[/SUB]
به طوريكه d[SUB]i(k)[/SUB]موعد تحويل كاري است كه در رديف kام توالي كارها قرار دارد.
با اين قاعده همچنين T[SUB]max[/SUB]يعني حداكثر ديركرد را كمينه مي كند .
قاعده ديگري كه برموعد تحويل مبتني است,قاعده نرخ بحراني است كه مي تواند داراي شكل هاي متعددي باشد .
در عمومي ترين شكل,نرخ بحراني به صورت زير است:
نرخ بحراني=
بنابراین استفاهده از قاعده نرخ بحرانی نیازمند براوردی از زمان پیشبرد یا زمان صف باقیمانده برای کار مورد نیاز می باشد .کارها بر حسب نرخ نزولی شان به ترتیب نزولی به صعودی مرتب می شوند . مزیت عمده قوانین مبتنی بر زمان فرایند (مانند SPT ) کاهش واریانس مغایرت زمان تحویل و نیز کاهش تعداد کارهایی است که انجام ان ها با دیرکرد مواجه می شود.