دانلود رایگان ترجمه مقاله کمینه کردن هزینه وزنی دیرکرد منبع در برنامه ریزی پروژه – هینداوی 2017

مقاله انگلیسی رایگان

ترجمه فارسی رایگان 

فهرست مقاله:

چکیده
1. مقدمه
2. توصیف مسئله
3. الگوریتم شاخه و کران برای RCPSP-TWRTPC
A. پیش پردازش
B. جفت های منفصل از فعالیت ها
C. مشخصات کران بالای اولیه
C. مشخصات کران بالای اولیه
E. انشعاب
F. اصول تسلط
G. بستن گره های عملی و به روز رسانی کران بالا
H. انتخاب گره برای انشعاب
4. تجزیه و تحلیل تجربی
5. نتیجه گیری ها

بخشی از ترجمه فارسی مقاله:

چکیده
در بسیاری از پروژه ها، منابع در طول چرخه عمر پروژه برای مدت زمان محدود در دسترس هستند و دسترس نگه داشتن آنها بعد از آن, منجر به برخی از هزینه های دیرکرد می شود. به حداقل رساندن هزینه دیرکرد منبع یک هدف مورد نظر در برنامه ریزی این پروژه ها است. در این راستا، ما یک مسئله برنامه ریزی پروژه را مطالعه می نماییم که مسئله برنامه ریزی پروژه با منبع محدود، حداقل کردن مجموع هزینه جریمه دیرکرد وزنی منبع (RCPSP-TWRTPC) نامیده می شود. در این مسئله، این پروژه منوط به منابع تجدید پذیر است، هر یک از منابع تجدید پذیر برای مدت زمان محدود در طول چرخه عمر پروژه در دسترس هستند و حفظ منابع برای هر دوره اضافی به برخی از هزینه های جریمه دیرکرد منجر می شود. ما یک الگوریتم شاخه و کران را برای حل دقیق این مسئله معرفی می کنیم و از چند محدوده، تفکر، و اصول تسلط در الگوریتم خود برای کوتاه شدن فرآیند شمارش استفاده می کنیم. ما به پارامترهای موثر بر درجه دشواری RCPSP-TWRTPC اشاره می کنیم، مجموعه های گسترده ای از موارد نمونه را برای این مسئله تولید می کنیم و تجزیه و تحلیل تجربی جامعی را با استفاده از الگوریتم های سفارشی و همچنین حل کننده CPLEX انجام می دهیم. ما رفتار این الگوریتم را با توجه به تغییرات در درجه سختی نمونه ها تجزیه و تحلیل می کنیم و عملکرد آن را برای موارد مختلف با حل کننده CPLEX مقایسه می کنیم. نتایج, کارآیی الگوریتم را نشان می دهند.

1. مقدمه
مسائل برنامه ریزی پروژه محدود در منبع به طور گسترده ای در نوشته های آزاد مورد مطالعه قرار گرفته اند. معیارهای مختلف در این مسائل مورد مطالعه قرار گرفته اند. به حداقل رساندن طول پروژه, یکی از پرمطالعه ترین اهداف است که در مسئله برنامه ریزی پروژه محدود در منبع (RCPSP) هدف گذاری شده است. به حداقل رساندن دیرکرد منبع, هدف دیگری است که بسیار کمتر در نوشته ها مطالعه شده است. این هدف در مقاله حاضر مورد مطالعه قرار گرفته است.
به حداقل رساندن دیرکرد منبع, یک هدف فراگیر در موارد عملی برنامه ریزی پروژه است. در بسیاری از پروژه ها، منابع برای دوره محدود از چرخه عمر پروژه در دسترس هستند و در دسترس نگه داشتن آنها پس از دوره های مربوط به این موضوع به مقدار هزینه دیرکرد نیاز دارد. منابع تجدیدپذیر که از خارج از پروژه اجاره می شوند و یا آنهایی که در بین پروژه های مختلف مشترک هستند معمولا تحت این شرایط قرار می گیرند. همچنین این منابع می توانند زمان های آماده داشته باشند، به عنوان مثال، آنها ممکن است در آغاز پروژه آماده نباشند. به حداقل رساندن هزینه دیرکرد منبع, یک هدف مورد نظر در برنامه ریزی این پروژه ها است.
در این مقاله, ما یک گسترش از مسئله RCPSP را مطالعه می کنیم که مسئله برنامه ریزی پروژه محدود در منبع، حداقل کردن مجموع هزینه جریمه دیرکرد وزنی منبع (RCPSP-TWRTPC) نامیده می شود [1]. در این مسئله, این پروژه منوط به منابع تجدیدپذیر است. هر منابع تجدید پذیر برای مدت زمان محدود در طول چرخه عمر پروژه در دسترس است و حفظ منابع برای دوره های اضافی به مقداری هزینه جریمه دیرکرد منجر می شود. هدف, به حداقل رساندن هزینه کلی جریمه دیرکرد منبع است. ما الگوریتم شاخه و کران برای حل دقیق مسئله را معرفی می کنیم. ساختار انشعاب سازی در این الگوریتم, شبیه به روش درخت اولویت است که یک رویکرد اساسی برای حل مسئله RCPSP است [2]. ما از چند محدوده، تفکر، و اصول تسلط برای الگوریتم خود به منظور کوتاه شدن فرآیند شمارش استفاده می کنیم. عملکرد الگوریتم از نظر عددی مورد بررسی قرار گرفت. نتایج, کارآیی الگوریتم را نشان می دهد.
نوشته ها در مسئله RCPSP به دهه 1960 باز می گردد [3]. این مسئله در مقالاتی چون [4]، [5] و [6] مورد مطالعه قرار گرفته است. با توجه به این واقعیت که این مسئله سخت-NP است [7]، بسیاری از این تلاش ها به توسعه الگوریتم های نادرست و یا محدودکننده اختصاص داده شده است. بسیاری از مقالات بررسی, نوشته های این مسئله مانند [8]، [9] و [10] خلاصه نموده است. به حداقل رساندن هزینه دیرکرد منبع در چند مقاله مطالعه مورد قرار گرفته است. مرجع [1], RCPSP-TWRTPC را معرفی نمود و یک الگوریتم حد و انشعاب را برای این مسئله ارائه نموده است. البته این مسئله که آنها مطالعه نمودند, متفاوت از مسئله مورد مطالعه ما در اینجاست، زیرا در مسئله آنها, تنها منابع تجدید پذیر یگانی در نظر گرفته شده اند، به عنوان مثال، حداکثر در دسترس بودن منابع در هر دوره و همچنین نیاز به منابع حداکثر در هر یک از فعالیت ها, یک هستند. در [11], یک الگوریتم ترکیبی برای این مسئله ارائه شده است. در [12], یک فرم بسط یافته از RCPSP-TWRTPC معرفی شد و مورد مطالعه قرار گرفت. در این مسئله که RCPSP-TWRTPC (MRCPSP-TWRTPCP) چند حالته نامیده می شود، فعالیت های پروژه چند حالته هستند و علاوه بر منابع تجدید پذیر, آنها تحت منابع غیر قابل تجدید هستند. هدف از این مسئله, به حداقل رساندن هزینه کل منابع، از جمله هزینه وزنی دیرکرد منابع تجدید پذیر و هزینه استفاده از منابع غیر قابل تجدید به واسطه فعالیت های پروژه است. برای حل این مسئله، یک الگوریتم فراابتکاری بر اساس یک نسخه اصلاح شده از روش بهینه سازی ازدحام ذرات معرفی شد.
بقیه این مقاله به شرح زیر است. در بخش بعدی، مسئله RCPSP-TWRTPC و در بخش سوم، الگوریتم شاخه و کران برای حل این مسئله به طور مفصل شرح داده شده است. بخش چهارم به تجزیه و تحلیل تجربی اختصاص داده شده است و در نهایت بخش V شامل چند نکته پایانی می شود.

بخشی از مقاله انگلیسی:

In this paper, we study a project scheduling problem that is called resource constrained project scheduling problem under minimization of total weighted resource tardiness penalty cost (RCPSP-TWRTPC). In this problem, the project is subject to renewable resources, each renewable resource is available for limited time periods during the project life cycle, and keeping the resource for each extra period results in some tardiness penalty cost. We introduce a branch and bound algorithm to solve the problem exactly and use several bounding, fathoming, and dominance rules in our algorithm to shorten the enumeration process. We point out parameters affecting the RCPSP-TWRTPC degree of difficulty, generate extensive sets of sample instances for the problem, and perform comprehensive experimental analysis using the customized algorithm and also CPLEX solver. We analyze the algorithm behavior with respect to the changes in instances degree of difficulty and compare its performance for different cases with the CPLEX solver. The results reveal algorithm efficiency

1. Introduction

Resource constrained project scheduling problems are widely studied in the open literature. Various criteria are studied in these problems. Project makespan minimization is one of the most studied objectives which is aimed in the resource constrained project scheduling problem (RCPSP). Resource tardiness minimization is another objective that has been much less studied in the literature. This objective is studied in the current paper. It differs from makespan minimization, since it tries to schedule those activities earlier for which the due dates of the required resources are earlier, even though this may elongate the project makespan. The optimal schedule in this case can change by simply changing the due dates of the resources. But in makespan minimization, the due dates of the resources are not taken into account. Resource tardiness minimization is a pervasive objective in the practical cases of the project scheduling. In many projects, resources are available for limited periods of the project life cycle and keeping them available after the related periods is subject to some tardiness costs. Renewable resources that are rented from outside the project or the ones that are common between various projects are usually subject to this condition. For example, in construction projects, heavy machines such as tower cranes or bulldozers are usually subject to this condition.These resources may also have ready times; that is, they may not be ready at the beginning of the project. Resource tardiness cost minimization is a preferred objective in scheduling of these projects. In this paper we study an extension of the RCPSP problem that is called resource constrained project scheduling problem under minimization of total weighted resource tardiness penalty cost (RCPSP-TWRTPC) [1]. In this problem the project is subject to renewable resources. Each renewable resource is available for limited time periods during the project life cycle and keeping the resource for each extra period results in some tardiness penalty cost. The objective is to minimize the total resource tardiness penalty cost. We introduce a branch and bound algorithm to solve the problem exactly. The branching structure in this algorithm is similar to the precedence tree approach, which is a basic approach to solve the RCPSP problem [2]. We use several bounding, fathoming, and dominance rules in our algorithm to shorten the enumeration process. The algorithm performance is numerically analyzed. The results reveal algorithm efficiency. The rest of this paper is organized as follows. In the next section, the related literature is reviewed; in Section 3 the RCPSP-TWRTPC problem and in Section 4 the branch and bound algorithm to solve the problem are described in detail. Section 5 is dedicated to the experimental analysis and finally, Section 6 contains a few concluding remarks.