زمانبندي n كار روي يك ماشين وقتيكه كارها داراي زمانهاي دسترسي و دنباله مي باشند

اصفهان : دانشگاه صنعتي اصفهان . دانشكده نساجي

زمانبندي تخصيص منابع در طول زمان براي اجراي مجموعه اي از وظايف است . مساله تك ماشين عبارت است از زمانبندي nكار بر روي يك ماشين ، طوريكه هر كار iدر زمان معين aiجهت اجرا روي ماشين آماده مي باشد، به اين معني كه تا قبل از زمان aiقابل دسترسي نيست و همچنين به اندازه diزمان لازم است تا آن كار انجام گيرد. از طرفي پس از اتمام كار iروي ماشين به اندازه qiزمان لازم است تا كار مربوطه تمام شده تلقي گردد. در اين مساله هدف كمينه كردن زمان پايان تمامي كارها يعني دامنه عمليات مي باشد. اولين راه حل كارا براي حل بهينه اين مساله توسط محققي بنام "كارلي ير" در سال 1982 ارائه شده است . راه حل ارائه شده دراين پايان نامه كه به زبان ++ Turbo Cكد شده است ، برمبناي توسعه در الگوريتم Schrageبا استفاده از ساختمان Heapمي باشد. سپس مساله با توجه به الگوريتم ارائه شده توسط كارلي ير به روش شاخه و كرانه حل شده است . اين راه حل عملا" از درجه nlognمي باشد، كه اين برنامه با تعداد زيادي كار(400 كار) تست شده است . مي توان از راه حل شده بعنوان يك راه حل كارا براي حل بهينه مساله Jop Shopاستفاده نمود. همچنين در الگوريتمهاي ابتكاري، مي توان از حل مساله تك ماشيني جهت يافتن يك جواب خوب براي مساله Job Shopاستفاده كرد

8648

مهندسي نساجي

دانشگاه صنعتي اصفهان

[محمد] قانع

محمدرضا زماني