چكيده
چكيده
زمانبندي تخصيص منابع در طول زمان براي اجراي مجموعه اي از وظايف است. زمانبندي آني نوعي برنامه¬ريزي است كه در آن هيچ اطلاعاتي در مورد كارهايي كه به كارگاه مي¬رسند، تا زمان ورود موجود نمي¬باشد. در اكثر برنامه¬ريزي¬ها وجود حق انقطاع باعث بهبود جواب مورد نظر مي¬گردد ولي حق انقطاع مورد نظر در تمام مسائل به صورت ساده نيست. فرآيند ساخت جكت¬هاي مورد نياز سكوهاي نفت و گاز را در نظر بگيريد. براي ساخت اين جكت¬ها، آهن¬هايي خريداري مي¬شود كه سطحي آن با زنگ آهن پوشيده شده¬است. اين زنگ آهن، مخصوصاً در هواي مرطوب باعث خوردگي و فرسودگي آهن مي¬شود و مي¬تواند عمر آن را تا 30% كاهش دهد. براي جلوگيري از خوردگي آهن بايد سطح آن با رنگ ضد زنگ پوشيده شود ولي قبل رنگ زدن بايد آهن زنگ زدايي گردد. با استفاده از عمليات سند بلاست ، فشار هواي شديد خرده¬هاي فشرده شن را روي سطح آهن مي¬دمد و زنگ زدايي صورت مي¬گيرد. پس از آن تا مدت زمان خاصي( حدود 10 ساعت) بايد عمليات رنگ كردن پايان يابد در غير اين صورت آهن¬ها دوباره زنگ مي¬زنند و عمليات سند بلاست بايد دوباره صورت گيرد كه خود نوعي جريمه است. به اين نوع جريمه كه به مدت زمان خاصي وابسته است، جريمه تركيبي مي¬گوييم.
در اين پايان نامه ابتدا مروري بر مدل¬هاي انقطاع در شرايط برنامه¬ريزي آني شامل انقطاع با حافظه و انقطاع بدون حافظه همراه با جريمه ساده صورت مي¬گيرد. در ادامه به معرفي جريمه تركيبي مي¬پردازيم و بيان ضرورت اين نوع جريمه مي¬پردازيم. سپس شرايط اعمال اين نوع جريمه در حالت¬هاي انقطاع با حافظه و بي حافظه را بررسي مي¬نماييم.
با توجه به NP-hard بودن مسأله، الگوريتم ابتكاري براي حل آن پيشنهاد گرديده و در غالب مثالي توضيح داده شده است. در نهايت اعتبارسنجي الگوريتم، با مقايسه با الگوريتم حريصانه و با استفاده از مثال¬هاي عددي تصادفي در ابعاد متفاوت صورت گرفته است.
واژه‌هاي كليدي:زمانبندي آني، انقطاع فعاليت¬ها، جريمه تركيبي، بازه زماني مجاز.
Keywords: Online scheduling, Preemption, Compound penalty, Permitted time frame
