الگوریتم های تقریبی مسئله گسسته مبادله زمان - هزینه

قیمت: 38,000 تومان

دانلود رایگان مقاله

خرید ترجمه مقاله

عنوان فارسی

الگوریتم های تقریبی مسئله گسسته مبادله زمان - هزینه

عنوان لاتین

APPROXIMATION ALGORITHMS FOR THE DISCRETE TIME-COST TRADEOFF PROBLEM

با توجه به ارتباط عملی آشکار آن، مسئله مبادله زمان-هزینه توجه بسیاری از محققان را طی چهل سال گذشته به خود جلب کرده است. در حالی که مسئله خطی مبادله زمان-هزینه را می توان به صورت چند جمله ای زمانی حل کرد، نوع گسسته آن با نام NP سخت شناخته شده است. ما در حال حاضر برای اولین بار از الگوریتم های تقریبی برای مسئله گسسته تبادل زمان-هزینه استفاده کرده ايم. به طور خاص، با توجه به بودجه ثابت ما مسئله پیدا کردن کوتاه ترین برنامه برای یک پروژه را در نظر گرفته ايم. ما یک الگوریتم تقریبی با نسبت عملکرد 3/2 را برای کلاس پروژه هايی که در آن تمام مدت زمان های امکان پذیر فعالیت ها یا 0، 1، و یا 2 هستند را ارائه کرديم. ما نتيجه خود را توسط الگوریتم های تقریبی با تضمین عملکرد O (ورود L)، که در آن L نسبت حداکثر مدت زمان هر فعالیت به حداقل مدت زمان غیر صفر هر گونه فعالیت است گسترش داديم. در نهایت، ما در مورد الگوریتم های تقریبی دو معياری بحث کرده ايم که برنامه ای را برای یک مهلت داده شده و یا بودجه طوری محاسبه می کنند که هر دو مدت زمان پروژه و هزینه در یک ضریب ثابت از مدت زمان و هزینه برنامه بهینه برای مهلت داده شده و یا بودجه قرار دارند.

Due to its obvious practical relevance, the Time-Cost Tradeoff Problem has attracted the attention of many researchers over the last forty years. While the Linear Time-Cost Tradeoff Problem can be solved in polynomial time, its discrete variant is known to be NP-hard. We present the first approximation algorithms for the Discrete Time-Cost Tradeoff Problem. Specifically, given a fixed budget we consider the problem of finding a shortest schedule for a project. We give an approximation algorithm with performance ratio 3/2 for the class of projects where all feasible durations of activities are either 0, 1, or 2. We extend our result by giving approximation algorithms with performance guarantee O(log l ) , where l is the ratio of the maximum duration of any activity to the minimum nonzero duration of any activity. Finally, we discuss bicriteria approximation algorithms which compute schedules for a given deadline or budget such that both project duration and cost are within a constant factor of the duration and cost of an optimum schedule for the given deadline or budget