پایان نامه کارشناسی ارشد رشته مهندسی صنایع- سیستم های اقتصادی اجتماعی
مرداد 1391
چکیده
مسئله زمانبندی پروژه با محدودیت منابع، از معروفترین مسائل مطرح در مباحث تحقیق در عملیات و بهینه سازی می باشد. در این مسئله هر پروژه از تعداد ی فعالیت تشکیل شده است به علاوه تعداد منبع با ظرفیتهای محدود وجود دارد. فعالیتها علاوه بر اینکه نسبت به یکدیگر جهت اجرا دارای اولویت هستند، در استفاده از منابع نیز محدودیت دارند. هدف کمینه کردن زمان اتمام پروژه می باشد به نحوی که محدودیت ها تقدمی و منبعی ارضا شدند. برای حل مسئله یک الگوریتم جدید بهینه سازی جامعه نامنظم (ASO) طراحی شده است. پس از انتخاب یک جمعیت اولیه به شکل تصادفی، با انتخاب سیاست حرکتی مبتنی بر مکان فعلی هر عضو یا سیاست حرکتی مبتنی بر مکانهای گذشته شخصی هر عضو یا سیاست حرکتی مبتنی بر مکان سایر اعضای جامعه انسانی یا سیاست حرکتی مبتنی بر قانون ترکیبی به جوابهای جدید می رسیم. برای تنظیم پارامترهای الگوریتم از روش تاگوچی استفاده میکنیم. در ادامه الگوریتم مذکور، پیاده سازی شده و در مورد نمونه های مختلف مسئله،تست و تنظیم گردیده است. پیاده سازی این الگوریتم روی مسایل پایه، کارایی آن را در مقایسه با سایر الگوریتم های موجود نشان می دهد.
واژگان کلیدی: زمانبندی پروژه، الگوریتم بهینه سازی جامعه نامنظم، مسئله زمانبندی پروژه با محدودیت منابع.
فصل اول
مفاهیم وکلیات زمانبندی پروژه
مقدمه
قدمت مدیریت پروژه بدون توجه به دانش مدیریت پروژه[1]، حداقل به 4500 سال پیش برمیگردد، سازندگان اهرام مصر و معابد مایا در آمریکای مرکزی اغلب به عنوان اولین مدیران پروژه دنیا محسوب می شوند]1[. پیدایش مدیریت پروژه به عنوان یک علم از جنگ جهانی اول آغاز شد به طوریکه در سال 1917، هنری ال .گانت[2] نمودار معروف گانت چارت[3] را ابداع کرد. بعد از سال 1950 سایر تکنیک های معروف مدیریت پروزه مانند روش مسیر بحرانی[4] و ... توسعه یافت. علم مدیریت پروژه به طور ویژه در دهه های گذشته از مهمترین و کاربردیترین موضوعات مورد توجه بوده است. با پیشرفت علوم و پیجیده تر شدن ساختارهای پروژه های تعریف شده در بخش های مختلف علمی وتجربی، مدیریت پروژه دائما به عنوان یک جزء لاینفک در کلیت پروژه خودنمایی میکند. در دنیای امروز با افزایش فضای رقابتی، تحویل به موقع کالا یا خدمات با کیفیت مورد نظر با رعایت محدودیتهای مختلف مانند نیروی کار، سرمایه و ...، بسیار با اهمیت جلوه میکند. با توجه به صرفه جویی حاصل از مدیریت پروژه در زمان و منابع و هزینه، علاقه مندان به این رشته در سراسر جهان به طور تصاعدی در حال افزایش است. در میان اجزای مختلف مدیریت پروژه، زمان بندی پروژه[5] به جهت اهمیت و نقش به سزای آن در سطح مدیریت کلان برنامه ریزی پروژه های مختلف جایگاه ویژه ای را به خوداختصاص داده است. از بعد عملی با بهبود زمان بندی پروژه که جزئی از مدیریت پروژه است، سود شرکت ها به خصوص شرکت هایی که کار تولید و فروش را به طور همزمان انجام میدهند(تولید به مصرف) به میزان چشمگیری افزایش می یابد. از کاربردهای عملی زمان بندی پروژه می توان در زمینه های توسعه نرم افزار، برنامه ریزی در سازمان های حمل و نقل و کارهای عمرانی و بسیاری زمینه های دیگر اشاره کرد. زمان بندی پروژه علاوه بر بعد عملی، از بعد نظری و تحقیقاتی نیز بسیار حائز اهمیت است و در سال های اخیر، تحقیقات بسیاری در این زمینه صورت گرفته است. از آنجاییکه بسیاری از مسائل بهینه سازی معروف حالت خاصی از مسائل مطرح در زمانبندی پروژه هستند، این مقوله یک زمینه تحقیقاتی جذاب برای علاقه مندان علم تحقیق در عملیات است، به عنوان مثال مسئله زمانبندی کارکارگاهی[6] (jssp) که یکی از معروف ترین مسایل بهینه سازی ترکیبی است که حالت خاصی از مسئله زمانبندی با محدودیت منابع است که در آن منابع مسئله فقط ماشین ها هستند.
طبق استاندارد PMBOK 2008 [7]مدیریت پروزه شامل 42 فرایند است که زمان بندی پروژه تنها یکی از این فرایندها محسوب می شود. در یک تقسیم بندی کلی تر بر طبق استاندارد PMBOK 2008 مدیریت پروژه شامل 5 مجموع فرایند اصلی به شرح ذیل است:
فرایندهای آغازین
فرایندهای برنامه ریزی
فرایندهای اجرا
فرایندهای کنترلی
فرایندهای اختتامی
زمان بندی پروژه که موضوع اصلی در این پایان نامه است، طبق این تقسیم بندی در گروه فرایندهای برنامه ریزی قرار میگیرید. زمان بندی پروژه به صورت تعیین توالی زمانی، جهت انجام یک سری فعالیت های وابسته به هم که تشکیل دهنده پروژه هستند تعریف می شود. منظور از وابستگی فعالیتها ، وجود روابط تقدمی در انجام آنهاست، بدین معنا که ممکن است انجام یک فعالیت وابسته به انجام یک یا چند فعالیت دیگر باشد، که در این حالت گفته می شود که پروژه دارای محدودیتهای تقدمی است. تعیین این برنامه زمانبندی میتواند تحت یک هدف و یا چند هدف خاص صورت گیرد. علاوه بر محدودیت های تقدمی که در تمام پروژه ها بین فعالیت ها موجود هستند، نوع دیگری از محدودیتها تحت عنوان محدودیت منابع نیز ممکن است در پروژه وجود داشته باشد. مسائل زمانبندی پروژه که فقط محدودیت تقدمی در آن وجود داشته باشد، به مسائل زمانبندی پروژه بدون محدودیت منابع معروف هستند. در مسائل زمانبندی پروژه اگر علاوه بر محدودیت تقدمی، محدودیت منابع نیز وجود داشته باشد، به مسئله زمانبندی پروژه با محدودیت منابع[8] (RCPSP) معروفند. اولین مدل ها و روش های زمانبندی پروژه که برای مقیاس بزرگ (بیش از صد فعالیت) طراحی شده اند به اواخر دهه 1950 برمیگردد. از معروفترین این روشها میتوان به روش مسیر بحرانی اشاره کرد که درسال 1961 توسط کلی[9] برای پروژه هایی که دارای فعالیت هایی با زمانهای قطعی و مشخص هستند طراحی شد.از روش های معروف دیگر در زمانبندی پروژه میتوان به روش تکنیک ارزیابی و بازنگری پروژه[10] (PERT) اشاره کرد که در سال 1956 توسط مالکولم[11] ابداع شد و برای پروژه هایی که دارای فعالیتهایی با زمان غیر قطعی و احتمالی هستند به وجود آمد. روش تکنیک ارزیابی و بازنگری گرافیکی[12] در سال 1967 توسط پریتسکر[13] و هاپ[14] ابداع شد که در آن فعالیت های پروژه به صورت احتمالی هستند. روش ها و مدل های اولیه زمانبندی پروژه که به سه روش مهم آن اشاره شد، برای پروژه هایی طراحی شده بودند که فقط دارای محدودیت تقدمی بین فعالیتها هستند در حالیکه در دنیای واقعی یکی از مهمترین مشکلات زمانبندی پروژه با محدودیت منابع است. از اواخر 1960، مدلهای زمانبندی پروژه که در آن هم محدودیت تقدمی و هم محدودیت منابع به طور همزمان مد نظر گرفته می شد گسترش یافتند. حل این نوع مسائل نسبت به مدل های قبلی بسیار سخت بود به طوریکه روش های یادشده برای حل این نوع مسائل کارایی نداشت، در این نوع مسائل جدید زمان حل مسئله با افزایش فعالیتها به صورت نمایی افزایش می یافت و در نتیجه در مسائل بزرگ(بیش از صد فعالیت) به خاطر بزرگ شدن فضای جستجو استفاده از روش های دقیق نیز از لحاظ زمانی مرقون به صرفه نبود چراکه این نوع مسائل به خصوص در ابعاد بزرگ جزء مسائل بهینه سازی NP-hard [15] محسوب می شدند. مسئله زمانبندی پروژه با محدودیت منابع در حالت کلاسیک (RCPSP) ساده ترین نوع مسائل زمانبندی پروژه با محدودیت منابع است که در ابعاد بزرگ (بیش از صد فعالیت) هیچ روش دقیقی برای حل آن وجو ندارد. بلازویچ[16] ثابت کرد که مسئله PCPSP به عنوان تعمیمی از مسئله JSSP یک مسئله NP-hard است به طوریکه زمان لازم برای یافتن جواب بهینه توسط بهترین روشهای دقیق برای شبکه های مشتمل بر بیش از سی فعالیت بسیار زیاد است]2[. در نتیجه محققان برای حل مسئله RCPSP در ابعاد بزرگ به روشهای ابتکاری[17] و فراابتکاری[18] روی آوردند، چرا که این روشها نیاز به پیمودن کل فضای جستجو ندارند و میتوان با آنها در زمان معقول به جواب نزدیک به بهینه رسید. به همین خاطر ما در این پایان نامه سعی داریم تا از الگوریتم جدید فراابتکاری بهینه سازی جامعه نامنظم (ASO) [19] که در سال 2011 توسط احمدی جاوید[20] به وجود آمده]3[، برای اولین بار برای حل مسئله زمانبندی پروژه با محدودیت منابع در حالت کلاسیک به کار بگیریم و نتایج آن را با بهترین الگوریتم های معروف، که قبلا بکار گرفته شده مقایسه کنیم.
1-1)اجزای زمانبندی پروژه
اجزای یک مسئله زمانبندی پروژه در سه جزء خلاصه می شود که عبارتند از : فعالبت ها، منابع و روابط تقدمی. در ادامه به طور اجمالی به بررسی هر یک از این اجزا میپردازیم. قبل از ادامه بحث در این قسمت، جدول 1 -1 را به عنوان جدول استادارد علائم مورد استفاده در این پایان نامه معرفی میکنیم.
Abstract
The resource - constrained project scheduling problem is the most famous problem in operation research and optimization.
The RCPSP involves a single project comprising of a set of non-dummy activities. A non-preemptive duration exists for each activity. Moreover, some renewable resources exist and each resource has a constant capacity. The objective of RCPSP is to minimize the project make span.
this study presents a new algorithm in order to solve the problem of anarchic society optimization (ASO). After choosing the initial population by random methods, we can gain new answers by movement policy based on the current position or past position of each member, movement policy based on other member positions or movement policy based on combination rules. The method of Taguchi is used in order to regulate of algorithm parameters. Then, algorithm is operated, and is regulated and tested for the problem of different samples. By operating of this algorithm in basic problems, we can show the efficiency of it rather than other algorithms.
Keywords: project scheduling, anarchic society optimization algorithm, resource-constrained project scheduling problem.
منابع و مآخذ
منابع انگلیسی:
Demeulmeester, E. K. & Horroelen, W. S. (2002). Project Scheduling: A research Handbook, Springer.
Blazewicz, J., Lenstra, J.K., and A.H.G. Rinnooy Kan, “Scheduling Subject to Resource Constraints: Classification and Complexity”, Discrete Applied Mthematics, 5(1983), PP. 11-24. Evalutionary Computation (CEC), June 5-8, New Orlens, LA, pp. 2586-2592, 2011.
Ahmadi-Javid, A., Anarchic society optimization: A Human-inspired method, Proceeding of IEEE Congress on
Bottcher, J., Drexl, A., Kolisch, R., Salewski, F. (1996). “Project Scheduling Under Partially Renewable Resource Constraints”. Technicl report 398 Manuscipte aus den Instituten fur Betriebswritschaftslehre der Universitat Kiel.
Talbot, F.B (1982). “Resource-Constrined Project Scheduling with Time-Resource Tradeoffs: The Nonpreemptive Case”. Management Science, 38: pp. 1498-1509.
Pritsker, A. B., Watters, L. J. and Wolfe, P. M., Multiproject scheduling with limited resources: A zero-one programming approach. Management Science, 1969, 16, 93-108.
Patterson, J. H. and Roth, G., Scheduling a project under multiple resource constraints: A zero-oneprogramming approach. AIIE Transactions, 1976, 8, 449-456.
Carruthers, J. A. and Battersby, A., Advances in critical path methods. Opertional Research Quarterly, 1966, 17, 359-380.
Petrovic, R., Optimisation of resource allocation in project planning. Operations Research, 1986, 16, 559-586.
Demeulemeester, E. and Herroelen, W., New benchmark results for the resource-constrained project scheduling problem. Management Science, 1997, 43, 1485-1492.
Brucker, P., Schoo, A. nd Thiele, O., A branch-and-bound algorithm for the resource-constrained project scheduling problem. European Journal of Operational Research, 1998, to appear.
Dorndorf, U., Pesch, E., Phan-Huy, T. A branch-and-bound algorithm for the resource-constrained project scheduling problem, Mathematical Methods of Operations Research 52(2000) 413-439.
Sprecher, A. , Drexl, A. (1995). Semi-Active, Active and non-delay Schedules for the Resource Constrained Project Scheduling Poblem, European Journal of Operational Research 80, 94-102.
Kolisch, R. (1996). Series and Parallel Resource Constrained Project Scheduling Method Revisited: Theory and Computation, European Jounal Of Operational Research 90,320-333.
Lee, J.K. and Y.D. Kim (1996), Search Heuristics for Resource Constrained Project Scheduling, Jounal of the Operational Research Society, 47, 678-689.
Kohlmorgen, U., H. Schmeck and K. Haase (1999), Experiences with Fine-Gained Parallel Genetic Algorithms, Annals of Opertions Reseach, 90, 203-219.
S. Hartmann, A competitive genetic algorithm for resource-constrained poject scheduling, Naval Research Logistics 49 (2002) 433-448.
J. Alcaraz, C. Maroto, A robust genetic algorithm for resource allocation in poject scheduling, Annals of Operations Research 102 (2001) 83-109.
S. Hartmann, A self-adapting genetic algorithm for project scheduling under resource constraints, Naval Research Logistics 49 (2002) 433-448.
Y.C. Toklu, Appliction of genetic algorithm to construction scheduling with o without resouce constraints, Candian Journal of Civil Engineeing 29 (2002) 421-429.
K.S. Hindi, H. Yang, K. Fleszar, An evolutionary algorithm for resource-constrained project scheduling, IEEE Transaction on Evolutionary Computation 6 (2002) 512-518.
J. Coelho, L. Tavares, Comparative analysis of metaheuicstics for the resource constrained project scheduling problem, Technical, report, Depertmant of Civil Engineering, Instituto Superior Tecnico, Portugal.
J. Gonclves, J. Mendes, A random key based genetic algorithm for the resource-constained poject scheduling problem. Technical report, Depatamento de Engenharia Universidade do Porto, 2003.
Goncalves JF, Beirao NC. Um algoritmo genetic baseado em chaves aleatorias para sequenciamento de operacoes. Revista Associacao Portuguesa Investigacao Opeacional 1999;19:123-37 (in Portuguese).
Mendes. J.J.M, Goncalves. J.F, Resende. M.G.C. A random key based genetic algorithm for the resource constrained project scheduling problem. Computers and Operations Research 36 (2009) 92-109.
P.R. Thomas, S. Salhi, A tabu search approach for the resource constrained project scheduling problem, Journal of Heuristics 4 (1998) 123-139.
T. Baar, P. Brucker, S. Knust, Tabu-search algorithm and lower bounds for the resource-constrained project scheduling problem, in: S. Voss, S. Martello, I. Osman, C. Roucairolb (Eds), Meta-heuristics: Advances and Trends in Local Search Paradigms for optimization, Kluwer Academic Publishers, Dordrecht, 1998, pp. 1-8.
R. Klein, Project scheduling with time-varying resource-constraints, International Journal of Production Research 38(16) (2000) 3937-3952.
K. Nonobe, T. Ibaraki, Formulation and tabu search algorithm for the resource constrained project scheduling problem, in: C.C. Ribeiro, P. Hansen (Eds.), Essays and Surveys in Metaheuristics, Kluwer Academic Publishers, 2002, pp. 557-588.
N. Pan, P. Wen Hsaio, K. Chen, A study of project scheduling optimization using Tabu Search algorithm, Engineering Applications of Artificial Intelligence 21 (2008) 1101-1112.
P. Tormos, A. Lova, A competitive heuristics solution technique for resource-constrained project scheduling, Annals of Operations Research 102 (2001) 65-81.
V. Valls, M.S. Quintailla, F. Ballestin, Resource-constrained project scheduling: A critical reordering heuristic, European Journal of Operational Research 149 (2003) 282-301.
V. Valls, F. Ballestin, M.S. Quintanilla, Justification and RCPSP: A technique that pays, European Journal of Operational Research 165 (2005) 375-386.
H. Zhang, X. Li, H. Li, F. Huang,”Particle swarm optimization-based schemes for resource-constrained project scheduling “, Automation in construction 14 (2005) 393-404.
R.M. Chen, C,L, Wu, C.M. Wang, Sh.T. Lo, “Using novel particle swarn optimization scheme to solve resource-constrained scheduling problem in PSPLIB “, Expert Systems with Applications, Volume 37. Issue 3, 15 March, 2010, pp. 1899-1910.
A. Ahmadi-Javid, P. Hooshangi-Tabrizi, An Anarchic Society Optimization Algorithm for a Flow-Shop Scheduling Problem with Multiple Transporters between Successive Machines, Proceedings of the 2012 International Conference Industrial Engineering and Operations Management Istanbul, Turkey, July 3-6, 2012.
Pritsker A. A.B., Watters, L. J., Wolfe, P. M., (1969). Multi project Scheduling with Limited Resources: A Zero-one Programming Approach, Management Science, 16, 93-108
Alvarez-Valdez, R. , Tamarit, J. M. , (1993). The Project Scheduling Polyhedron: Dimensions, Facts and Lifting Theorems European Jornal of Operational Research 67, 204-220
Mingozzi A. , Maniezzo, V. , Ricciardelli, S., and Bianco, L. (1998), An Exact Algorithm for Resource Constrained Project Scheduling Problem based on a new mathematical Formulation, Management Science, 44, 715-729.
J.Kennedy and R. Eberhart, “Particle swarn optimization”, Proceedings of the IEEE International Conference on Neural Networks (Perth, Australia) 1942-1948, 1995.
Kolisch, R. and A. Sprecher (1996), PSPLIB - A project scheduling library, European Journal of Operational Research,Vol. 96, pp. 205--216.
kolisch,R.,Sprecher,A.,Drexl,A,Charactrization and generation of a general class of resource-constrained project scheduling problems.Management science 41,pp.1693-1703.1995
[43] Taguchi, G., 1986. Introduction to quality engineering. White Plains: Asian Productivity Organization/UNIPUB.
[44] R. Kolisch und S. Hartmann (2006): Experimental Investigation of Heuristics for
Resource-Constrained Project Scheduling: An Update, European Journal of
Operational Research 174, 23-37, 2006.