توصيفگر ها :
توسعه الگوريتم , كارلي ير , زمانبندي , آدامز , شمارشي , شاخه , كرانه , ژنتيك , boJ pohS , جاكسون , كانالهاي انفصالي , كار , ماشين , گره فعال
چكيده فارسي :
مساله زمانبندي nكار مستقل برروي mماشين بگونه اي كه هركار داراي ترتيب عملياتي متفاوتي باشد، اصطلاحا" به مساله Job Shopمعروف مي باشد و مي توان گفت كه يك حالت كلي از زمانبندي عمليات روي ماشينهاست . در حقيقت بسياري از مسايل زمانبندي حالتهاي ساده شده اي از اين مساله محسوب مي گردند. اين مساله از نوع پيچيده تركيبي مي باشد و روشهاي متعددي براي حل آن ارائه شده است . در اين تحقيق روش كارلي ير كه يكي از بهترين روشهاي موجود جهت بدست آوردن جواب بهينه اين مساله مي باشد، مورد بررسي قرار گرفته و توسعه داده مي شود. روش كارلي ير در واقع يك روش شاخه و كرانه مي باشد كه روي شبكه هاي انفصالي و مساله تك ماشين پايه گذاري شده است . دراين روش حد پايين با استفاده از مساله تك ماشين بدست آورده مي شود و پيشنهاداتي كه براساس مساله تك ماشين تنظيم شده اند، به منظور تعيين جهت نمودن كمانهاي انفصالي بكار مي روند. يك حد بالا جهت حذف شاخه هاي زائد و نيز يك روش ابتكاري جهت شاخه زدن درخت استفاده مي شود. در ضمن نحوه جستجوي درخت بصورت پشته مي باشد. روش كارلي ير بر روش تكامل يافته با استفاده از زبان برنامه نويسي Cكد شده و بوسيله مسائل تصادفي مورد آزمون قرار گرفته اند. نتايج آزمونها حاكي از آن است كه ساختار روش كارلي ير به تعداد كمانهاي انفصالي و كارايي پيشنهادات وابسته است ، به اين معني كه هرچه تعداد كمانهاي انفصالي كمتر و يا هرچه كارايي پيشنهادات بيشتر باشد، آنگاه كارايي اين روش به مراتب افزايش مي يابد.
