توضیحات
ABSTRACT
In this paper, we present an extension of the classical Resource Constrained Project Scheduling Problem (RCPSP). We present a new type of resource constraints in which staff members are involved. We present a new model where staff members can have several skills with different proficiency, i.e., a staff member is able to perform more than one kind of activity as well as the time need is complete the task assign depends on the staff individual skill. We call this model the Weighted-Multi-Skill Project Scheduling Problem (WMSPSP). In our model, an activity has specific skill requirements that must be satisfied. To solve this problem, we propose a lower bound that uses a linear programming scheme for the RCPSP .
INTRODUCTION
The Resource Constrained Project Scheduling Problem (RCPSP) is a general scheduling problem . It consists of a set of activities and a set of renewable resources. Each resource is available in a given constant amount. Each activity has duration and requires a constant amount of resource to be processed. Preemption is not allowed. Activities are related by two sets of constraints: temporal constraints modeled through precedence constraints and resource constraints that state that for each time period and for each resource, the total demand cannot exceed the resource capacity. The objective considered here is the minimization of the makespan (total duration) of the project. This problem is NP-hard. Most work about RCPSP considers static problems in which activities are known in advance and constraints are fixed. However, every schedule is subject to unexpected events (consider for example a new activity to schedule, or a resource failure—e.g. machine breakdown).When such a situation arises, a new solution, taking these events into account, is needed in a preferably short time. Two classical methods used to solve such problems are: re-computing a new schedule from scratch each time an event occurs (a quite time consuming technique) and constructing a partial schedule and completing it progressively as time goes by (like in on-line sche duling problems—this is not compatible with planning purposes).Constraint Satisfaction Problems (CSP) are also increasingly used for solving scheduling problems.
چکیده
در این مقاله، گسترش یک برنامه زمانبندی پروژه محصور شده با منابع کلاسیک (RCPSP) را ارائه می کنیم. ما نوع جدیدی از محدودیت های منابع را در اختیار کارکنان قرار می دهیم. ما مدل جدیدی را ارائه می دهیم که اعضای هیات می توانند مهارت های مختلفی با مهارت های مختلف داشته باشند، به عنوان مثال، یک کارمند قادر به انجام بیش از یک نوع فعالیت و همچنین زمان نیاز به تکمیل است وظیفه بستگی به مهارت فردی فرد دارد. ما با استفاده از این مدل، برنامه ریزی زمان بندی پروژه وزن (Multi-Skill Project Planning) (WMSPSP). در مدل ما یک فعالیت دارای نیازهای خاصی است که باید رضایت بخش باشد. برای حل این مشکل، ما یک محدودیت پایین را پیشنهاد می کنیم که از یک برنامه برنامه ریزی خطی برای RCPSP استفاده می کند.
مقدمه
مشکل زمانبندی پروژه محدود شده منابع (RCPSP) یک مشکل زمانبندی عمومی است. این مجموعه شامل مجموعه ای از فعالیت ها و مجموعه ای از منابع تجدید پذیر است. هر منبع در یک مقدار ثابت در دسترس است. هر فعالیت طول می کشد و نیاز به یک مقدار ثابت از منابع را پردازش می کند. اخطار مجاز نیست فعالیت ها بوسیله دو مجموعه محدودیت ها مرتبط می شوند: محدودیت های زمانی به وسیله محدودیت های قضیه و محدودیت های منابع که براساس هر دوره زمانی و برای هر منبع تعیین می شود، تقاضای کل از ظرفیت منابع تجاوز نمی کند. هدف در اینجا این است که به حداقل رساندن زمان (طول کل) پروژه است. این مشکل NP سخت است. اکثر کارهایی که در مورد RCPSP انجام می شود، مشکالت استاتیک است که در آن فعالیت ها از قبل شناخته شده است و محدودیت ها ثابت می شوند. با این حال، هر برنامه در معرض وقایع غیر منتظره است (به عنوان مثال یک فعالیت جدید برای برنامه ریزی، یا یک خرابی منابع – به عنوان مثال تجزیه ماشین – در نظر بگیرید). هنگامی که چنین وضعیتی رخ می دهد، یک راه حل جدید، زمان کوتاه. دو روش کلاسیک برای حل این مشکلات عبارتند از: مجددا محاسبه یک برنامه جدید از ابتدا هر زمانی که اتفاق می افتد (یک تکنیک کاملا وقت گیر) و ساختن یک برنامه جزئی و تکمیل آن به طور مداوم به عنوان زمان انجام می شود (مانند در طرح آنلاین مشکلات دالین- این با اهداف برنامه ریزی سازگار نیست.) مسائل رفع محدودیت (CSP) نیز به طور فزاینده ای برای حل مسائل برنامه ریزی استفاده می شود.
Year: 2011
Publisher : SCIRES
By : Fawaz S. Al-Anzi, Khaled Al-Zamel, Ali Allahverdi
File Information: English Language/ 6 Page / size: 71.97 KB
Only site members can download free of charge after registering and adding to the cart
سال : 1390
ناشر : SCIRES
کاری از : فوزوس الآنزی، خالد الزمال، علی اله وردی
اطلاعات فایل : زبان انگلیسی / 6 صفحه / حجم : KB 71.97
نقد و بررسیها
هنوز بررسیای ثبت نشده است.