International Journal of Industrial Engineering & Production Management (2013)

-144144-24523

November 2013, Volume 24, Number 3
pp. 349-360

http://IJIEPM.iust.ac.ir/

Calculating the Mean Project Completion Time in Dynamic
PERT Networks (Multi-Project System) with Finite Capacity

S. Noori& S. Yaghoubi

Siamak Noori, Associate professor, Department of Industrial Engineering , Iran University of Science & Technology, [email protected] Saeed Yaghoubi, PhD, Department of Industrial Engineering, Iran University of Science & Technology, [email protected]
Keywords 1ABSTRACT

Project management, In this paper, dynamic PERT networks with finite capacity of Network of queue, concurrent projects are expressed in the framework of networks of
Markov Processes queues. In this investigation, it is assumed that the system capacity is

1268732040127

Downloaded from ijiepm.iust.ac.ir at 14:42 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 14:42 IRST on Saturday November 4th 2017

finite and new projects are generated according to a Poisson process. There is only one server in every service station and the discipline of queue is FCFS (Fist Come, First Served). Each activity is performed independently in its corresponding service station with exponential distribution. For calculating the mean project completion time in dynamic PERT network with finite capacity, we first convert the network of queues into a stochastic network. Then, by constructing a proper finite-state continuous-time Markov model, a system of differential equations is created to solve and find the manufacturing lead time distribution for any particular work, analytically. Finally, by using Little’s Theorem the mean project completion time is obtained.

© 2013 IUST Publication, IJIEPM. Vol. 24, No. 3, All Rights Reserved

به دست آوردن ميانگين زمان تکميل پروژه در شبکه هاي پرت پویا
)سيستم چندپروژه اي( با ظرفيت محدود

سيامک نوري* و سعيد یعقوبي

کلمات کليدي چکيده:
-137153127

مديريت پروژه، شبکه صف ، در اين نوشتار، شبکههاي پرتپويا با ظرفيت محدود در اجراي همزمان پروژهها در چارچوب شبکه صف فرآيندهاي مارکوفي بيان شدهاست. در اين پژوهش، فرض شدهاست که ظرفيت سيستم براي اجراي هم زمان پروژهها محدود مي باشد و نيز پروژه هاي ورودي کاملاکاملاً مشابه بوده و طبق فرآيند پوآسون وارد سازمان مي شوند. در هر ايستگاه کاري فقط يک خدمت دهنده مستقر بوده و نيز نظم حاکم بر صف ها، اولين ورودي، اولين سرويس (FCFS) مي باشد .هر فعاليت به طور مستقل و با توزيع نمايي در ايستگاه کاري متناظر خود اجراء مي شود. براي به دست آوردن ميانگين زمان تکميل پروژه در شبکه هاي پرت پويا با ظرفيت محدود ،ابتدا شبکه صف را به شبکه احتمالي تبديل نموده و سپس با ايجاد يک مدل مارکوفي مناسب که داراي حالات محدود و زمان پيوسته مي باشد، معادله ديفرانسيلي سيستم تشکيل مي گردد. در نهايت با بهره گيري از قانون ليتل، ميانگين زمان تکميل پروژه به دست مي آيد.
-1371559918

1. مقدمه1
عموماعموماً مديريت پروژه سنتي بر روي مسائل برنامه ريزي تک پروژه اي متمرکز مي شود، در حالي که 09% سازمان ها، چندين پروژه را به طور هم زمان مديريت مي نمايند] 1[. در چنين شرايطي، سازمان ها براي بهره برداري هر چه بيشتر از منابع، آنها را در بين پروژه ها به اشتراک گذاشته که اين امر، برنامه ريزي پروژه ها را پيچيده و دشوار مي سازد. در نتيجه امروزه مديريت چندپروژه اي2 يک ديدگاه ضروري و حياتي در اکثر سازمان ها ،بالاخص سازمان هاي پروژه محور مي باشد.
به طور کلي مسئله برنامه ريزي چندپروژه اي با در نظر گرفتن پروژه ها بهعنوان اجزاء مستقل و به کاربردن يک يا چندين تابع هدف که شامل همه آنها باشد و يا بهوسيله اضافه نمودن فعاليت هاي مجازي ابتدايي و انتهايي، و در نظر گرفتن هر پروژه
تاریخ وصول: 3/6/39 تاریخ تصویب: 15/1/31
*نویسنده مسئول مقاله: دکتر سيامک نوري، دانشييار دانشيکده مهندسييصنايع، دانشگاه علم و صنعت ايران ،[email protected]
دکتر سعيد یعقوبي، استاديار دانشکده مهندسي صنايع، دانشگاه علم و صنعت ايران، Multi-project management [email protected] 2
به عنوان يک زيرپروژه و ايجاد يک پروژه بزرگ، مورد مطالعه قرار مي گيرد] .2[، ]3[، ]4[ و] 5[ جزو اولين مطالعاتي بودند که مسئله برنامه ريزي چندپروژه اي را مورد بررسي قرار دادند. مسئله برنامه ريزي چندپروژه اي با استفاده از برنامه ريزي صفر و يک] 6[، و نيز روش هاي چندمعياره] 7[ مورد مطالعه قرار گرفته است .
همچنين روش هاي فرآابتکاري و ابتکاري کاربرد زيادي در حل مسائل برنامه ريزي چندپروژه اي دارند که در اين زمينه مي توان به مطالعات] 8[، ]0[، ]19[، ]11[، ]12[ و] 13[ اشاره کرد .
1268732040127Downloaded from ijiepm.iust.ac.ir at 14:42 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 14:42 IRST on Saturday November 4th 2017

در حين اجراي پروژه، فعاليت هاي پروژه در معرض عدم قطعيت4 و بي ثباتي قابل توجهي قرار دارند که ممکن است منجر به اختلالات فراوان در برنامه ريزي شود. اين عدم قطعيت ممکن است از برخي منابع احتمالي نشأت بگيرد که عبارتند از: تغيير محسوس زمان فعاليتها نسبت به برآورد انجام شده، در دسترس نبودن منابع به مقدار لازم، عدم پيش بيني دقيق درخصوص فعاليت ها و منابع ،تغييرنمودن موعد تحويل پروژه، اعمال تغييرات در شبکه پروژه )شامل: اضافه نمودن فعاليت جديد، حذفکردن يک يا چندين فعاليت و اعمال تغييرات در پيش نيازيها(، وقوع وقايع غير مترقبه و غيره]14[.
4 Uncertainty

1268732040127Downloaded from ijiepm.iust.ac.ir at 14:42 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 14:42 IRST on Saturday November 4th 2017

971
در بسياري از سازمان ها، علاوه بر مواجهه با عدم قطعيت در انجامفعاليت ها ممکن است که پروژه ها در زمانهاي مشخص و از پيشتعيين شده، وارد سازمان نشده و به صورت پويا و احتمالي، درگذر زمان وارد سازمان شوند، که اين امر، برنامه ريزي پروژه را پيچيده تر و دشوارتر از پيش مي نمايد. اين نوع مسائل که علاوه بر احتمالي بودن فعاليت ها، ورود پروژه ها نير احتمالي بوده و پروژه ها در يک محيط پويا وارد سازمان مي شوند، شبکه هاي پرت پويا1 نام گذاري شده اند .
آدلر و همکاران] 15[ براي فائق آمدن به مسائل شبکه هاي پرت پويا ، ديدگاه فرآيندي را ارائه نموده و با استفاده از شبيه سازي زمان تکميل پروژه را مورد مطالعه قراردادند. در اين ديدگاه سازمان به صورت يک شبکه پردازشي احتمالي درنظر گرفته مي شود که داراي ايستگاه هاي کاري مي باشد. پروژه ها به طور مستمر وارد سازمان شده و ايستگاه هاي کاري نيز در حال خدمت دادن به پروژه ها با يک نظم از پيش تعيين شده مي باشند. در نتيجه سازمان با يک شبکه صف روبرو مي باشد که پروژه ها براي دريافت خدمت به ايستگاه هاي کاري مراجعه مي کنند .
در اين ديدگاه فرآيندي، پروژه ها به صورت انفرادي با ملزومات و منابع مختص به خود، درنظر گرفته نشده، بلکه به صورت يک سيستم يکپارچه اي که پروژه ها جهت دريافت خدمت، به طور مستمر وارد سازمان شده و منابع مشترکامشترکاً در اختيار تمامي پروژه ها قرار مي گيرد، تلقي مي شوند. در اين نوع سيستم، پروژه ها پس از طي ايستگاه هاي کاري براساس شبکه پيش نيازي خود، تکميل شده و آماده تحويل به کارفرماي خود مي باشند، به طوري که زمان تکميل پروژه معادل طولاني ترين مسير شبکه صف خواهد بود .
در دنياي واقعي به دليل وجود محدوديتهايي در سيستم، معمولاًمعمولا امکان اجراي هم زمان پروژه ها از يک تعداد مشخصي بيشتر وجود ندارد. با توجه به وجود اين نوع محدوديت در سازمان ها ،اناوي ايساکو و گلاني ]16[ شبکه هاي پرت پويا را با در نظر گرفتن محدوديت ظرفيت در پذيرش پروژه ها مورد مطالعه قرار دادند. آنها محدوديت سيستم را در تعداد ثابت پروژه هاي در حال پردازش )CONPIP(3 و يا در زمان ثابت در حال پردازش) CONTIP(4 در نظر گرفته و با استفاده از شبيه سازي براي نظم هاي مختلف ،زمان تکميل پروژه را به دست آوردند. مسئله تخصيص منابع در شبکه هاي پرت پويا با ظرفيت محدود نيز با استفاده از روش کراس آنتروپي که يک روش مبتني بر شبيه سازي مي باشد مورد مطالعه قرار گرفته است] 17[ و] 18[. همچنين فاطمي قمي و اشجري 1 Dynamic PERT networks
]10[ مساله تخصيص منابع چندين پروژه اي را به عنوان يک سيستم صف چندکاناله در نظر گرفته و از شبيه سازي براي به دست آوردن متغيرهايي همچون سطح منبع، ميانگين استفاده از منبع و ميانگين زمان انجام پروژه ها، استفاده نمودند. ولي آنها محيط پويايي که منجر به ايجاد پروژه هاي جديد در گذر زمان شود، مدنظر قرار ندادند.
از طرف ديگر، آذرون و مدرس] 29[ با استفاده از يک روش تحليلي، تابع توزيع زمان تکميل پروژه در شبکه هاي پرت پويا را مورد مطالعه قرار دادند. آنها فرض کردند که پروژه ها با توزيع پواسون وارد سيستم شده و توزيع زمان انجام فعاليت ها نمايي مي باشد. همچنين مولفان فرض کردند که در هر ايستگاه کاري يک و يا بي نهايت خدمت دهنده مستقر بوده و نيز ظرفيت سيستم نامحدود است .
همچنين، آذرون و همکاران] 21[ تابع توزيع طولاني ترين مسير در شبکه هاي صف را که قابل استفاده در شبکه هاي پرت پويا مي باشد، مورد مطالعه قرار داند و نيز آذرون و فاطمي قمي] 22[ يک حد پايين براي ميانگين زمان تکميل پروژه در شبکه هاي پرت پويا ارائه نمودند. همچنين، آذرون و توکلي مقدم] 23[ و يعقوبي و همکاران] 24[، يک مدل برنامه ريزي احتمالي به کمک فرآيند مارکوفي براي مسئله تخصيص منابع در شبکه هاي پرت پويا ارائه نمودند. اخيرااخيراً هم آذرون و همکاران] 25[ بر روي تخصيص موعد مقرر تحويل پروژه ها در شبکه هاي پرت پويا متمرکز شده و يک الگوريتم براي محاسبه آن ارائه کرده اند. لازم به ذکر است که در مقالات ذکر شده که همگي از يک روش تحليلي براي مدل نمودن شبکه هاي پرت پويا استفاده مي نمايند، فرض بر اين است که محدوديتي در انجام هم زمان پروژه ها نبوده و ظرفيت سيستم نامحدود است.
عليرغم اينکه مطالعات کمي درخصوص زمان تکميل پروژه در شبکه هاي پرت پويا و نيز طولاني ترين مسير در شبکه هاي صف انجام شده، ولي تحقيقات متعددي درخصوص طولاني ترين مسير يا زمان تکميل پروژه در شبکه هاي احتمالي صورت پذيرفته است ،به طوري که برخي از اين مطالعات، اين مقوله را به صورت تحليلي مورد بررسي قرار داده اند. آدلاخا و کالکارني] 26[ يک دسته بندي خوبي بر روي شبکه هاي احتمالي انجام دادند .
چارنس و همکاران] 27[ با فرض نمايي بودن فعاليت ها يک برنامه ريزي تصادفي براي شبکه هاي احتمالي ارائه نمودند .
همچنين، يک روش سيستماتيک براي محاسبه طولاني ترين مسير در شبکه هاي احتمالي با استفاده از کاهش دادن شبکه به فعاليت هاي سري-موازي در ]28[ و نيز يک برنامه ريزي پويا براي مسئله مذکور در] 20[ ارائه شده است. کالکارني و آدلاخا] 39[ با فرض نمايي بودن فعاليت ها شبکه پرت را به يک زنجيره مارکوفي
با تعداد حالات محدود و زمان پيوسته که داراي حالتجذب کننده اي مي باشد، تبديل نمود و به کمک آن تابع توزيعتکميل پروژه را محاسبه نمود. لازم به ذکر است که در اين مقاله ،ما نيز براي مدل نمودن شبکه هاي پرت پويا با ظرفيت محدود، يک زنجيره مارکوفي با تعداد حالات محدود و زمان پيوسته ارائه خواهيم نمود. به علت سختي و پيچيدگي در محاسبه توزيع زمان تکميل پروژه، برخي از مطالعات مانند] 31[، ]32[، ]33[ و] 34[، تکنيک هاي تقريبي و يا حدحدّپايينّپايين براي زمان تکميل پروژه ارائه کرده و نيز بعضي از تحقيقات مانند] 35[، ]36[ و] 37[، بر روي ميانگين زمان تکميل پروژه متمرکز شده اند.
لازم به ذکر است که به سبب وجود محدوديت ظرفيت در بسياري از سيستم هاي واقعي، شبکه صف ظرفيت محدود (FCQN) مورد توجه بسياري از محققان قرار گرفته است، که در اين ميان مي توان به پرپِرُسُس] 38[ به عنوان يکي از محققان پيشرو اشاره کرد .
شبکه صف ظرفيت محدود در زمينه هاي مختلفي از قبيل:
سيستم هاي توليدي]30[، ]49[، معماري نرم افزار] 41[، فعاليت هاي بهداشتي] 42[، سيستم هاي ارتباط از راه دور] 43[، مرکز تلفن] 44[ و غيره، کاربرد وسيعي دارد .
با توجه به مطالب ذکر شده مي توان نتيجه گرفت که هيچ روش تحليلي براي به دست آوردن ميانگين زمان تکميل پروژه در شبکه هاي پرت پويا با ظرفيت محدود انجام نشده و مطالعات در اين زمينه محدود به انجام شبيه سازي مي باشد. در نتيجه، نوآوري اين پژوهش ارائه يک روش تحليلي به کمک زنجيره مارکوفي با تعداد حالات محدود و زمان پيوسته جهت محاسبه ميانگين زمان تکميل پروژه مي باشد. لازم به يادآوري است که در] 29[ زمان تکميل پروژه در شبکه هاي پرت پويا و در] 21[ طولاني ترين مسير در شبکه هاي صف، بدون در نظر گرفتن محدوديت در ظرفيت
سيستم ها مورد مطالعه قرار گرفته است، که با توجه به محدود بودن بيشتر سيستم ها و عدم امکان اجراي هم زمان پروژه ها از يک تعداد
مشخصي بيشتر، نامحدود فرض کردن ظرفيت سيستم چندان واقعي به نظر نمي رسد .
در اين مقاله فرض شده است که ظرفيت سيستم براي اجراي هم زمان پروژه ها محدود مي باشد و نيز پروژه هاي ورودي کاملاً مشابه بوده و طبق فرآيند پوآسون وارد سازمان مي شوند. همچنين فرض بر اين است که در هر ايستگاه کاري فقط يک خدمت دهنده مستقر بوده و نيز نظم حاکم بر صف ها، اولين ورودي، اولين سرويس (FCFS) مي باشد. فعاليت ها به طور مستقل از هم و با توزيع نمايي در ايستگاه کاري متناظر خود انجام مي شوند. در اين مقاله، براي به دست آوردن ميانگين زمان تکميل پروژه در

971
شبکه هاي پرت پويا با ظرفيت محدود، ابتدا شبکه صف را به شبکه احتمالي تبديل نموده و با ايجاد يک مدل مارکوفي مناسب که داراي حالات محدود و زمان پيوسته مي باشد، معادله ديفرانسيلي سيستم تشکيل مي گردد. سپس با بهره گيري از قانون ليتل ،ميانگين زمان تکميل پروژه به دست مي آيد. موضوع مورد بحث در اين مقاله براي سازمان هاي چندپروژه اي که داراي محدوديت در اجراي هم زمان پروژه ها مي باشند، بسيار مناسب است؛ به طوري که پروژه ها علاوه بر مواجهه با عدم قطعيت در انجام فعاليت ها، به طور پويا و احتمالي، درگذر زمان وارد سازمان مي شوند. از نمونه هاي بارز اين گونه پروژه ها مي توان به پروژه هاي تعميرات نگهداري هواپيما، قطار، مترو و غيره اشاره کرد.
در ادامه مقاله، در بخش 2 يک مدل مارکوفي با حالات محدود و زمان پيوسته براي شبکه هاي پرت پويا با ظرفيت محدود ارائه خواهد شد و سپس ميانگين زمان تکميل پروژه در بخش 3 به دست خواهد آمد. در بخش 4 هم يک مثال عددي بيان شده و در انتها، نتيجه گيري و پيشنهادات براي مطالعات آتي در بخش 5
ذکر خواهد شد .

1. شبکه هاي پرت پویا با ظرفيت محدود
در اين قسمت يک زنجيره مارکوفي با تعداد حالات محدود و زمان پيوسته براي شبکه پرت پويا با ظرفيت محدود که به عنوان يک شبکه صف در نظر گرفته شده، ارائه مي شود. در اين مقاله فرض شده است که ظرفيت سيستم براي اجراي هم زمان پروژه ها محدود مي باشد و نيز پروژه هاي ورودي کاملاکاملاً مشابه بوده و طبق فرآيند پوآسون با نرخ  وارد سازمان مي شوند. همچنين فرض بر اين است که در هر ايستگاه کاري فقط يک خدمت دهنده مستقر بوده و نيز نظم حاکم بر صف ها FCFS مي باشد .
فعاليت ها به طور مستقل از هم و با توزيع نمايي انجام مي شوند ،به طوري که زمان انجام فعاليت a اُُم در ايستگاه کاري a، داراي توزيع نمايي با پارامتر a مي باشد .
براي مدل نمودن مسئله مذکور، ابتدا شبکه پرت پويا ، که به صورت شبکه فعاليت در گره) AoN( نشان داده مي شود، به يک شبکه پرت کلاسيک) AoA( تبديل مي شود. اگر فرض کنيم گرهk در شبکه پرت پويا ، داراي کمانهاي ورودي b1,b2,…, bn و کمان هاي خروجي d1,d2,…, dm باشد، در اين صورت در شبکه پرت کلاسيک، با کمان (k,k) تعويض خواهد شد که n کمان به گره k وارد شده وm کمان از گره k خارج مي شود.
1268732040127Downloaded from ijiepm.iust.ac.ir at 14:42 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 14:42 IRST on Saturday November 4th 2017

شبکه پرت کلاسيک) AoA(، را به صورت (G  (V, A در نظر مي گيريم که در آن مجموعه V بيانگر مجموعه گره ها و مجموعه A بيانگر مجموعه فعاليت ها خواهد بود. لازم به ذکر است که در طول اين مقاله واژه هاي فعاليت و کمان معادل بوده و ممکن است
979
به جاي يکديگر استفاده شوند. همچنين گرهs ، نشاندهنده گرهابتدايي و گره y ، نمايانگر گره انتهايي در شبکه پرت کلاسيکمي باشد، در حالي که طول کمان a  A، يک متغير تصادفي با توزيع نمايي و پارامتر a مي باشد. براي هر (a) ، a  A را گره شروع فعاليت a و (a) را گره پاياني فعاليت a تعريف مي نمائيم. همچنين تعاريف زير را براي مسئله مورد بحث در نظر مي گيريم:
تعریف 1. I(v) را به عنوان مجموعه فعاليت هايي )کمان هايي( که به گره v در شبکه هاي پرت کلاسيک خاتمه مي يابند و O(v) را مجموعه فعاليت هايي )کمان هايي( که از گره v در شبکه پرت کلاسيک شروع مي شوند، تعريف مي کنيم، يعني داريم:

I(v) a A:(a) v (vV), )1(
O(v) a A:(a) v (vV). )2(

30131111556

1831345221741

تعریف 1. اگر X  V چنانچه s  X و y  X  V  X باشد، دراينصورت ((X,X، مجموعه فعاليت هايي که شروع در X و پايان در X باشد را نمايش خواهد داد. يعني براي برش
:داريم (s,y)

3117812805

18188012805

(X,X)  a  A :(a) X,(a) X. )3(

حال اگر X,X) ) باشد، به آن برش، برش جهتدار يکنواخت Uniformly Directed Cut (UDC) گفته مي شود يعني اينکه در برش انجام شده، دو فعاليت در يک مسير وجود نداشته باشد.
مثال 1. شبکه پرت پويا ي نشان داده شده در شکل 1-الف را درنظر بگيريد. برشهاي جهتدار يکنواخت اين مثال عبارتند از: 3(,2,1)، 4(,3,1)، 5,2,1)، 5,4,1)، 6,1) و (7)، که از شبکه پرت کلاسيک )شکل 1-ب( بهدست مي آيد.

)
(
الف
AoN

)
ب
(
AoA

شکل

1
شبکه
.

مثال

هاي
1

2

4

6

7

1

پايان

λ

3

5

شروع

1
3

t

4

2

s

1

4

3

2

6

7

5



قیمت: تومان


دیدگاهتان را بنویسید