International Journal of Industrial Engineering & Production Management (2013)

-144144-24523

February 2013, Volume 23, Number 4
pp. 471-484

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

Due Date Assignment for Delivery Time in Multi-Server
Dynamic PERT Networks

S. Noori& S. Yaghoubi

Siamak Noori, Associate professor, Department of Industrial Engineering , Iran University of Science & Technology,
Saeed Yaghoubi, Assistant Professor, Department of Industrial Engineering, Iran University of Science & Technology, yaghoubi@iust.ac.ir

Keywords 1ABSTRACT

Project management, In this paper, multi-class dynamic PERT network is considered as a Queueing network, queueing network, where the projects are similar and new projects
Markov process are generated according to a Poisson process. Each activity is performed independently in its corresponding service station with exponential distribution by one server from several servers settled in the service station based on FCFS (Fist Come, First Served) discipline. Also, each project’s end result has a penalty cost that is some linear function of its due-date and its actual completion time. In this investigation, for computing the due date for multi-class dynamic PERT network, we first convert the queueing network into a
stochastic network. Then, by constructing an appropriate finite-state continuous-time Markov model, a system of differential equations is created to solve and find the project completion time distribution for any particular project, analytically. Finally, the optimal due date for delivery time is obtained by using a linear function of its due-date and minimizing the expected aggregate cost per project.
© 2013 IUST Publication, IJIEPM. Vol. 23, No. 4, All Rights Reserved

-116839-1435396

تعيين موعد مقرر تحويل پروژه در شبکه هاي پرت پويا با چندين
خدمت دهنده

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

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

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

9. مقدمه9
در سال هاي اخير، رويکرد پروژه محوري به عنوان يک ديدگاه اصلي، در بسياري از سازمان ها اتخاذ شده است به طوري که فعاليت ها و اقدامات سازمان ها براساس پروژه هاي شان انجام مي شوند. در چنين شرايطي، سازمان ها اغلب با يک سيستم چندپروژه اي2 روبرو هستند که براي بهره برداري هر چه بهتر از امکانات و منابع، آنها را در بين تمامي پروژه هاي سازمان به اشتراک مي گذارند. در اين گونه سازمان ها، به سبب اجراي هم زمان چندين پروژه، مسئله برنامه ريزي چندپروژه اي مطرح شده که
تاريخ وصول: 39/6/19 تاريخ تصويب: 62/1/19
*نويسنده مسئول مقاله: دکتر سيامک نوري، دانشييار دانشيکده مهندسيي صنايع، دانشگاه علم و صنعت ايران ،snoori@iust.ac.ir
سعيد يعقوبي، استاديار دانشکده مهندسي صنايع، دانشگاه علم و صنعت ايران،
2 Multi-project system yaghoubi@iust.ac.ir
عموماً به وسيله اضافه نمودن فعاليت هاي مجازي ابتدايي و انتهايي، و در نظرگرفتن هر پروژه به عنوان يک زيرپروژه و ايجاد يک پروژه بزرگ، و يا با در نظرگرفتن پروژه ها به عنوان اجزاء مستقل و به کار بردن يک يا چندين تابع هدف که شامل همه آنها باشد، مورد مطالعه قرار مي گيرد. از اولين مطالعات انجام شده در زمينه مسئله برنامه ريزي چندپروژه اي مي توان به] 4-1[ اشاره کرد. لازم به ذکر است که مدل هاي چندهدفه] 5[، چندمعياره] 6[ و همچنين روش هاي فراابتکاري و ابتکاري] 13-7[، توسط محققان در تحليل مسئله مذکور مورد استفاده واقع شده است.
فعاليت هاي پروژه در حين اجراء، اغلب در معرض عدم قطعيت قرار دارند که ممکن است منجر به اختلالات فراوان در برنامه ريزي شود]14[. از سوي ديگر در برخي از سازمان هاي چندپروژه اي ،علاوه بر عدم قطعيت در زمان انجام فعاليت ها، ممکن است پروژه ها به صورت پويا و احتمالي، درگذر زمان وارد سازمان شوند، که اين موضوع برنامه ريزي پروژه را پيچيده تر و دشوارتر از پيش مي نمايد .اين نوع از مسائل که علاوه بر احتمالي بودن فعاليت ها، ورود پروژه ها نيز در يک محيط پويا و به صورت احتمالي صورت پذيرد ،شبکه هاي پرتپويا1 نامگذاري شدهاست .
مسئله مذکور با استفاده از ديدگاه فرآيندي در] 15[ مورد مطالعه قرارگرفت، به طوري که سازمان بهصورت يک شبکه پردازشي احتمالي درنظرگرفته شد که داراي چندين ايستگاهکاري ميباشد. پروژه ها به صورت احتمالي و در گذر زمان وارد سازمان شده و هر ايستگاه کاري که چندين خدمت دهنده را در خود جاي داده است، در حال خدمت دادن به فعاليتهاي مرتبط بهخود ميباشد که درچنين شرايطي سازمان با يک شبکه صف روبرو ميشود. مولفان زمان تکميل پروژه را با بهره گيري از شبيه سازي مورد مطالعه قرار دادند. لازم به ذکر است که در اين ديدگاه فرآيندي سازمان به صورت يک سيستم واحد تلقي شده که پروژهها جهت دريافت خدمت، به طور مستمر وارد سازمان شده و منابع مشترکاً در اختيار تمامي پروژه ها قرار مي گيرد. در چنين سيستمهايي، پروژهها پس از طي ايستگاه هاي کاري براساس شبکه پيش نيازي خود، پايان پذيرفته و آماده تحويل به کارفرماي خود ميباشند که با توجه به ماهيت شبکههاي پروژه، زمان تکميل پروژه معادل طولاني ترين مسير شبکه صف خواهد بود .همچنين شبکه هاي پرت پويا با در نظرگرفتن چندين خدمتدهنده در هر ايستگاه کاري و ظرفيت محدود در پذيرش پروژه ها با استفاده از شبيه سازي در] 16[ مورد مطالعه قرارگرفت .
همچنين مسئله تخصيص منابع در شبکه هاي پرت پويا با ظرفيت محدود با استفاده از شبيهسازي در] 17[ و] 11[ مورد پژوهش قرارگرفت .
از طرف ديگر، آذرون و مدرس] 11[ شبکه هاي پرت پويا را با استفاده از يک روش تحليلي بهمنظور بهدست آوردن تابع توزيع زمان تکميل پروژه مورد مطالعه قرارداده و سپس آذرون و توکلي مقدم] 22[ مسئله تخصيص منابع )موازنه زمان-هزينه( را با ارائه يک مدل برنامهريزي چندهدفه احتمالي در شبکه هاي پرت پويا مطرح نمودند. مولفان فرضکردند که پروژه ها با توزيع پواسون وارد يک سيستم چندپروژه اي با ظرفيت نامحدود شده و توزيع زمان انجام فعاليتها نمايي مي باشد، درحالي که در هر ايستگاه کاري يک و يا بي نهايت خدمتدهنده مستقر ميباشد .همچنين، يعقوبي و همکاران] 21[ مسئله تخصيص منابع در شبکههاي پرتپويا را با فرض محدودبودن ظرفيت سيستم در پذيرش پروژه هاي ورودي مورد پژوهش قراردادند. علاوه براين ،يعقوبي و همکاران] 22[ با مطرحنمودن دو ديدگاه منابع به عنوان Dynamic PERT networks 1
473
خدمت دهنده ها3 و منابع موثر برخدمت دهنده ها درتخصيص منابع، شبکه هاي پرت پويا با چندين خدمت دهنده در هر ايستگاه کاري را با ارائه مدل هاي برنامه ريزي احتمالي چندهدفه ،مدل نمودند .
اخيراً هم مسئله تخصيص موعدمقرر براي تحويل پروژه در شبکههاي پرت پويا با فرض مستقربودن يک و يا بي نهايت خدمت دهنده در هر ايستگاه کاري و نامحدودبودن ظرفيت سيستم، توسط آذرون و همکاران] 23[ مطرح شده و يک الگوريتم براي محاسبه موعدمقرر ارائهشده است. لازم به ذکر است که در اين مقاله با تعميم مطالعه آذرون و همکاران] 23[، مسئله تخصيص موعدمقرر براي تحويل پروژه در شبکه هاي پرت پويا با چندين خدمت دهنده و ظرفيت نامحدود، توسط يک زنجيره مارکوفي با تعداد حالات محدود و زمان پيوسته مورد مطالعه قرارخواهدگرفت و اين درحالي است که مسئله تخصيص منابع که مسئله اي متفاوت با مسئله تخصيص موعدمقرر براي تحويل پروژه در شبکه هاي پرت پويا ميباشد، در تحقيقات] 23-22[ توسط برنامه ريزي چندهدفه احتمالي مدل شده است .
تحقيقات متعددي درخصوص طولاني ترين مسير يا زمان تکميل پروژه در شبکههاي احتمالي )شبکه هاي پرت کلاسيک( انجام پذيرفته است، به طوري که برخي از اين مطالعات، اين مقوله را به صورت تحليلي مورد پژوهش قرار داده اند و اين در حالي است که تحقيقات اندکي در حوزه طولاني ترين مسير در شبکههاي صف و يا زمان تکميل پروژه در شبکه هاي پرت پويا صورت پذيرفته است. يک برنامه ريزي تصادفي براي شبکه هاي احتمالي با فرض نمايي بودن فعاليت ها در] 24[ و نيز يک روش سيستماتيک کاهشدادن شبکه به فعاليت هاي سري-موازي در] 25[، جهت محاسبه طولاني ترين مسير در شبکه هاي احتمالي ارائه شده است .
همچنين، برنامهريزي پويا هم براي مدل نمودن مسئله مذکور در ]26[ مطرح شده است. کالکارني و آدلاخا] 27[ با فرض نمايي بودن فعاليتها، شبکه پرت را به يک زنجيره مارکوفي با تعداد حالات محدود و زمان پيوسته که داراي حالت جذب کنندهاي مي باشد، تبديل نمودند و به کمک آن تابع توزيع تکميل پروژه را محاسبه نمودند. گفتني است که يک دسته بندي خوبي بر روي شبکه هاي احتمالي در] 21[ صورت پذيرفته است. همچنين ،برخي از مطالعات مانند] 32-21[، به علت سختي و پيچيدگي در محاسبه توزيع زمان تکميل پروژه، تکنيک هاي تقريبي و يا حد پايين براي زمان تکميل پروژه ارائه نموده اند .
با توجه به مطالب ذکر شده ميتوان چنين نتيجه گرفت که هيچ روش تحليلي براي بدست آوردن موعدمقرر تحويل پروژه در
3 Resources as servers
474
شبکه هاي پرت پويا با چندين خدمت دهنده انجام نشده است .
درنتيجه، نوآوري اين پژوهش ارائه يک روش تحليلي به کمک زنجيره مارکوفي با تعداد حالات محدود و زمان پيوسته جهت تعيين تابع توزيع زمان تکميل پروژه در شبکه هاي پرت پويا با چندين خدمت دهنده و نيز ارائه يک الگوريتم جهت تعيين موعدمقرر تحويل پروژه مي باشد. لازم به يادآوري است که در مطالعه] 23[، فرض بر اين است که در هر ايستگاه کاري يک و يا بي نهايت خدمت دهنده مستقر شده است، در حالي که در اين مقاله اين فرض به صورت کلّّي درنظرگرفته شده است.
در اين پژوهش، فرض شده است که پروژه هاي ورودي کاملاً مشابه بوده و طبق فرآيند پوآسون وارد سازمان مي شوند. فعاليت ها به طور مستقل از هم و با توزيع نمايي در ايستگاه کاري متناظر خود و فقط توسط يک خدمت دهنده از ميان چندين خدمتدهنده موجود با نظم اولين ورودي، اولين سرويس (FCFS) 1، انجام مي شوند .
همچنين، هر پروژه يک هزينه جريمه اي برحسب زمان تکميل واقعي پروژه و زمان انجام متعهد شده توسط مجري پروژه، به خود اختصاص مي دهد. در اين مقاله، براي بدستآوردن زمان ثابت موعدمقرر تحويل پروژه در شبکه هاي پرت پويا با چندين خدمتدهنده، ابتدا شبکه صف را به يک شبکه احتمالي تبديل نموده و با ايجاد يک مدل مارکوفي مناسب که داراي حالات محدود و زمان پيوسته مي باشد، معادله ديفرانسيلي سيستم تشکيل مي گردد که درنتيجه مي توان تابع توزيع زمان تکميل هر پروژه را بدست آورد. سپس با بهره گيري از يک تابع جريمه خطي و حداقل کردن ميانگين مجموع هزينه هاي هر پروژه، موعدمقرر براي تحويل هر پروژه بدست ميآيد.
در ادامه مقاله، در بخش 2 يک مدل مارکوفي با حالات محدود و زمان پيوسته براي شبکههاي پرت پويا با چندين خدمت دهنده جهت بدستآوردن تابع توزيع زمان تکميل پروژه ارائه خواهد شد و نيز الگوريتم تعيين موعدمقرر تحويل پروژه در شبکه هاي پرت پويا با چندين خدمت دهنده، در بخش 3 ارائه خواهد شد. در بخش 4 يک مثال عددي بيان شده و در انتها، نتيجهگيري و پيشنهادات براي مطالعات آتي در بخش 5 ذکر خواهد شد.

6. شبکه هاي پرت پويا با چندين خدمت دهنده
در اين قسمت، هدف مدل نمودن شبکه پرت پويا با چندين خدمتدهنده بهکمک يک زنجيره مارکوفي با تعداد حالات محدود و زمان پيوسته و سپس تعيين تابع توزيع زمان تکميل هر پروژه مي باشد، به طوري که پروژه هاي ورودي داراي ساختار )پيشنيازي و توزيع فعاليت ها( کاملاً مشابه بوده و طبق فرآيند پوآسون با نرخ وارد سازمان مي شوند. همچنين فرض بر اين است که تعدادma خدمت دهنده در ايستگاه کاري a اُُم مستقر شده و فعاليت ها به طور مستقل از هم، با توزيع نمايي و فقط توسط يکي از خدمت دهنده هاي هر ايستگاه با نظم FCFS انجام مي شوند .زمان انجام فعاليت a اُُم در ايستگاه کاري a، داراي توزيع نمايي با پارامتر a بوده و نيز ظرفيت سيستم و ظرفيت ايستگاه هاي کاري نامتناهي درنظرگرفته شده است.

6-9. فرآيند مارکوفي با زمان پيوسته در اين قسمت هدف ارائه يک زنجيره مارکوفي با حالات محدود و زمان پيوسته با توجه به فرضيات بيان شده براي شبکه هاي پرت پويا با چندين خدمت دهنده مي باشد که بدين منظور مراحل ذيل ارائه مي گردد:

قدم 9. تابع چگالي زمان صرف شده در هر ايستگاه کاري محاسبه شود.
قدم 9. 9. اگر يک خدمت دهنده در ايستگاه کاريa اُُم ساکن شده باشد، در اين صورت سيستم /M / M بوده و تابع توزيع زمان صرفشده در سيستم )زمان انتظار در صف و زمان دريافت خدمت( بهصورت زير خواهد بود:

wa (t)  (a ).e(a )tt  0, if ma  1 )1(

که در آن  نرخ ورود پروژه هاست که با فرآيند پواسون ايجاد مي شوند و نيزa نرخ ارائه خدمت در ايستگاه کاري a اُُم با تابع توزيع نمايي مي باشد. يعني زمان صرف شده در ايستگاه کاري a اُُم با يک خدمت دهنده، داراي توزيع نمايي با پارامتر (a ) خواهد بود.
قدم 9. 6. اگر بي نهايت خدمت دهنده در ايستگاهکاريa اُمُ وجود داشته باشد، در اين صورت سيستم M / M /  بوده و تابع توزيع زمان صرف شده در سيستم، توزيع نمايي با پارامتر a خواهد بود.

wa (t)  a .eatt  0, if ma   )2(

قدم 9. 3. اگر  ma  1 خدمت دهنده در ايستگاه کاريa اُُم استقرار يافته باشد، در اين صورت سيستم M /M /ma
1542526487855

بوده و تابع توزيع زمان صرف شده در سيستم، به طور تقريبي برابراست با دو توزيع نمايي سري با پارامترهاي (maaa) و (1mmaaa)، در حاليکه a 

maa. درنتيجه تابع توزيع زمان صرف شده در ايستگاه کاري a اُُم به طور تقريبي برابر خواهد بود با: )براي جزئيات بيشتر پيوست را مطالعه نماييد(.

0
)
1
)(
)
(
)
1
(
)
(
(
).
)(
)
(
)
1
(
)
1
(
(
)
(
)
1
(
)
(

t
e
m
m
m
m
m
m
e
m
m
m
m
m
m
t
w
t
m
m
a
a
a
a
a
a
a
a
a
a
a
a
t
m
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a



































(
3
)

0

)

1

)(

)

(

)



قیمت: تومان


پاسخ دهید