-
دسته: رشته کامپیوتر, رشته مدیریتفرمت : word | حجم : 327kb | صفحات : 107قیمت: 11000 تومان1,866 بازدید
مقاله مدلسازی و حل مسئله زمانبندی جریان کارگاهی با زمانهای تنظیم وابسته به توالی مربوطه به صورت فایل ورد word و قابل ویرایش می باشد و دارای ۱۰۷ صفحه است . بلافاصله بعد از پرداخت و خرید لینک دانلود مقاله مدلسازی و حل مسئله زمانبندی جریان کارگاهی با زمانهای تنظیم وابسته به توالی نمایش داده می شود، علاوه بر آن لینک مقاله مربوطه به ایمیل شما نیز ارسال می گردد
فهرست
فصل ۱٫ ۱
کلیات.. ۱
۱-۱- مقدمه. ۱
۱-۲- محدوده تحقیق و اهداف آن.. ۹
۱-۳- مرور ادبیات.. ۱۳
فصل ۲٫ ۲۴
مدلسازی و حل جنبه ای جدید از مسئله زمانبندی جریان کارگاهی جایگشتی.. ۲۴
۲-۱- مقدمه. ۲۴
۲-۲- مدلسازی مسئله. ۲۴
۲-۳- الگوریتم ابتکاری جهت حل مسئله. ۲۸
۲-۴- نتایج محاسباتی.. ۳۴
۲-۴-۱- موارد تستی.. ۳۴
۲-۴-۲- کارآمدی روشهای ابتکاری.. ۳۶
۲-۵- نتیجه گیری.. ۴۰
فصل ۳٫٫ ۴۱
حل مسائل زمانبندی جریان کارگاهی جایگشتی با بکارگیری روشهای فراابتکاری ترکیبی.. ۴۱
۳-۱- مقدمه. ۴۱
۳-۲- الگوریتم ژنتیک… ۴۱
۳-۳- مدل ریاضی.. ۴۳
۳-۴- الگوریتم ژنتیک ترکیبی.. ۴۵
۳-۴-۱- جوابهای اولیه. ۴۶
۳-۴-۲- بهبود. ۴۶
۳-۴-۳- ارزیابی.. ۴۸
۳-۴-۴- انتخاب.. ۴۸
۳-۴-۵- عملگرهای ژنتیکی.. ۵۰
۳-۴-۵-۱- درجه عبور۵. ۵۰
۳-۴-۵-۲- جهش ابتکاری.. ۵۲
۳-۴-۵-۳- جهش وارونه. ۵۲
۳-۵- نتایج محاسباتی.. ۵۳
۳-۶- بهینه سازی جامعه مورچگان.. ۵۶
۳-۷- الگوریتم بهینه سازی جامعه مورچگان ترکیبی.. ۵۷
۳-۷-۱- تشخیص اولیه. ۵۷
۳-۷-۲- قانون انتقال۱ ۶۰
۳-۷-۳- جستجوی محلی.. ۶۰
۳-۷-۴- به روز رسانی فرومون ها ۶۰
۳-۷-۵- معیار توقف.. ۶۲
۳-۸- نتایج محاسباتی.. ۶۲
۳-۹- الگوریتم الکترومغناطیس… ۶۹
۳-۱۰- الگوریتم الکترومغناطیس ترکیبی.. ۷۲
۳-۱۱- نتایج محاسباتی.. ۷۵
۳-۱۲- نتیجه گیری.. ۸۰
فصل ۴٫٫ ۸۳
مسئله فروشنده دوره گرد. ۸۳
۴-۱- مقدمه. ۸۳
۴-۲- تعریف مسئله. ۸۵
۴-۳- کاربرد و ارتباط با مسائل زمانبندی.. ۸۵
۴-۴- مدل ریاضی.. ۸۶
۴-۵- روش حل.. ۸۸
۴-۶- نتایج محاسباتی.. ۸۸
۴-۷ نتیجه گیری.. ۹۰
فصل ۵٫ ۹۱
نتیجه گیری و پیشنهادات برای مطالعات و پژوهش های آتی.. ۹۱
۵-۱- نتیجه گیری.. ۹۱
۵-۲- پیشنهادها ۹۶
۶- منابع.. ۹۷
۶- منابع
Arnoldoو C. Hax, Dan Candea, 1984. Production and Inventory Management, 2th. New York.
Kenneth R. Baker, 1996. Elements of sequencing and scheduling, 3th. University of Toronto bookstores.
Deepu Philip, 2005. Scheduling Reentrant Flexible Job Shops With Sequence Dependent Setup Times, MS Thesis, MontanaStateUniversity.
Gupta D., Magnusson T., 2005. The capacitated lot-sizing and scheduling problem with sequence-dependent setup costs and setup times, Computers & Operations Research 32, 727-747.
Paulo M. França, Gupta J.N.D. Alexandre S., Mendes, Pablo Moscato, Klaas J. Veltink, 2005. Evolutionary algorithms for scheduling a flowshop manufacturing cell with sequence dependent family setups, Computers & Industrial Engineering 48(3), 491-506. Schaller E. Gupta J. N. D. Vakharia J., 2000. Scheduling a flowshop manufacturing cell with sequence dependent family setup times, European Journal of Operational Research 125(2), 324-339. Johnson S.M., 1954. Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly 1, 61–۶۸٫
Handbook of Industrial Engineering, 2th Edition., 1992. Salvendy G, editor.Ostwald P.F.
Allahverdi A. Gupta J.N.D. Aldowaisan T., 1999. A review of scheduling research involving setup considerations, OMEGA, International Journal of Management Science 27, 219–۲۳۹٫
Ruiz R. Maroto C., 2004. A comprehensive review and evaluation of permutation flowshop heuristics. European Journal of Operational Research [to appear].
Pinedo M., 1995. Scheduling: Theory, Algorithms, and Systems. 4th. Prentice Hall, NJ.
Eren T. Güner E., 2006. A bicriteria scheduling with sequence-dependent setup times, Applied Mathematics and Computation 179(1), 378-385. Cheng T.C.E. Gupta J.N.D. Wang G., 2000. A review of flowshop scheduling research with setup times. Production and Operations Management 9, 262–۲۸۲٫
Garey M.R. Johnson D.S. Sethi R., 1976. The complexity of flowshop and job-shop scheduling, Mathematics of Operations Research 1(2), 117–۱۲۹٫
Campbell H.G. Dudek R.A. Smith M.L., 1970. A heuristic algorithm for the n job, m machine sequencing problem. Management Science 16(10), B630–B637.
Nawaz M. Enscore Jr E.E. Ham I., 1983. A heuristic algorithm for the m-machine, n-job flowshop sequencing problem. OMEGA, The International Journal of Management Science 11(1), 91–۹۵٫
Osman I.H. Potts C.N., 1989. Simulated annealing for permutation flowshop scheduling. OMEGA, The International Journal of Management Science 17(6), 551–۵۵۷٫
Widmer M. Hertz A., 1989. A new heuristic method for the flowshop sequencing problem. European Journal of Operational Research 41, 186–۱۹۳٫
Reeves C.R., 1995. A genetic algorithm for flowshop sequencing. Computers & Operations Research 22(1), 5–۱۳٫
Stafford Jr E.E. Tseng F.T., 1990. On the Srikar–Ghosh MILP model for the N×M SDST flowshop problem. International Journal of Production Research 28(10), 1817–۱۸۳۰٫
Ríos-Mercado R.Z. Bard J.F., 1998. Computational experience with a branch-and-cut algorithm for flowshop scheduling with setups. Computers & Operations Research 25(5), 351–۳۶۶٫
Tseng F.T. Stafford Jr E.E., 2001. Two MILP models for the N×M SDST flowshop sequencing problem. International Journal of Production Research 39(8), 1777–۱۸۰۹٫
Ríos-Mercado R.Z. Bard J.F., 1999a. A branch-and-bound algorithm for permutation flowshops with sequence-dependent setup times. IIE Transactions 31, 721–۷۳۱٫
Ríos-Mercado R.Z. Bard J.F., 1999b. An enhanced TSP-based heuristic for makespan minimization in a flowshop with setup times. Journal of Heuristics 5, 53–۷۰٫
Bryan A., Norman, 1999. Scheduling flowshops with finite buffers and sequence-dependent setup times, Computers & Industrial Engineering 36(1), 163-177. Ruiz-Torres A.J. Centeno G., 2008. Minimizing the number of late jobs for the permutation flowshop problem with secondary resources. Computers & Operations Research 35, 1227-1249.
Wang X. Cheng T.C., 2007. An approximation scheme for two-machine flowshop scheduling with setup times and an availability constraint. Computers & Operations Research 34, 2894-2901.
Schaller J. Gupta J.N.D. Vakharia A.J., 2000. Scheduling a flowline manufacturing cell with sequence dependent family setup times. European Journal of Operational Research 125, 324–۳۳۹٫
Ruiz, R. Maroto C. Alcaraz J., 2005. Solving the flowshop scheduling problem with sequence dependent setup times using advanced metaheuristics, European Journal of Operational Research 165(1) 34-54. Ruiz R. Stutzle T., 2008. An iterated greedy heuristic for the sequence dependent setup times flowshop with makespan and weighted tardiness objectives. European Journal of Operational Research 187, 1143-1159.
Ekşioğlu B. Ekşioğlu S.D. Jain P., 2008. A tabu search algorithm for the flowshop scheduling problem with changing neighborhoods. Computers & Industrial Engineering 54, 1-11.
Allahverdi A. Ng C.T. Cheng T.C.E. Kovalyov M.Y., 2008. A survey of scheduling problems with setup times or costs, European Journal of Operational Research 187, 985-1032.
Logendran R. Salmasi N. Sriskandarajah C., 2006. Two-machine group scheduling problems in discrete parts manufacturing with sequence-dependent setups, Computers & Operations Research 33(1) 158-180. Stafford F. Tseng T., 2002. Two models for a family of flowshop sequencing problems, European Journal of Operational Research 142(2), 282-293. Tang L. Huang L., 2005. Optimal and near-optimal algorithms to rolling batch scheduling for seamless steel tube production, International Journal of Production Economics 105, 357–۳۷۱٫
Gupta S.R. Smith J.S., 2006. Algorithms for single machine total tardiness scheduling with sequence dependent setups. European Journal of Operational Research 175, 722-739.
Parthasarathy S. Rajendran C., 1997. An experimental evaluation of heuristics for scheduling in a real-life flowshop with sequence-dependent setup times of jobs, International Journal of Production Economics 49(3), 255-263.
GuptaN.D., 1975. A search algorithm for the generalized flowshop scheduling problem, Computer and Operation Research 2, 83-90.
Kenneth E. Mcgraw, Maged M. Dessouky, 2001. Sequence dependent batch chemical scheduling with earliness and tardiness penalties. International journal of production research 39(14), 3085-3107.
Merce C. and Fontan G., 2003. MIP-based heuristics for capaciated lotsizing problems, int. J. Production Economic 85, 97-111.
Osman I.H. Kelly J.P., 1996. Meta-heuristics: Theory and Applications. 3th. Kluwer Academic Publishers, Boston.
Das S.R. Canel C., 2005. An algorithm for scheduling batches of parts in a multi-cell flexible manufacturing system. International Journal of Production Economics ۹۷, ۲۴۷-۲۶۲٫
Ho W. Ji P., 2003. Component scheduling for chip shooter machines: a hybrid genetic algorithm approach, Computers and Operations Research 30, 2175–۲۱۸۹٫
Ho W. Ji P., 2004. A hybrid genetic algorithm for component sequencing and feeder arrangement. Journal of Intelligent Manufacturing 15, 307–۳۱۵٫
Goldberg D.E., 1989. Genetic Algorithms in Search, Optimization and Machine Learning. 2th. Addison-Wesley, New York.
Gen M. Cheng R., 1997. Genetic Algorithms and Engineering Design. 2th. Wiley, New York.
Laha D. Chakraborty U.K., 2007. An efficient stochastic hybrid heuristic for flowshop scheduling, Engineering Applications of Artificial Intelligence 20, 851–۸۵۶٫
Blum, C., 2005. Ant colony optimization: Introduction and recent trends. Physics of Life Reviews 2, 353–۳۷۳٫
Dorigo, M. Di Caro G. Gambardella L.M., 1999. Ant algorithms for discrete optimization. Artificial Life 5(2), 137–۷۲٫
Dorigo M. Stützle T., 2004. Ant Colony optimization. 2th. Cambridge, MA: MIT Press.
Liao C. Juan H., 2007. An ant colony optimization for single-machine tardiness scheduling with sequence-dependent setups. Computers & Operations Research 34, 1899–۱۹۰۹٫
Shyua S.J. Linb B.M.T. Yin P.Y., 2004. Application of ant colony optimization for no-wait flowshop scheduling problem to minimize the total completion time. Computers & Industrial Engineering 47, 181–۱۹۳٫
Rajendran C. Ziegler H., 2004. Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. European Journal of Operational Research 155, 426–۴۳۸٫
Birbil S.I. Fang S.C., 2003. An Electromagnetism-like Mechanism for Global Optimization. Journal of Global Optimization 25, 263–۲۸۲٫
Debels D. De Reyck B. Leus R. Vanhoucke M., 2006. A hybrid scatter search/electromagnetism meta-heuristic for project scheduling. European Journal of Operational Research 169, 638–۶۵۳٫
Chang PC, Chen SS, Fan CY, In press. A Hybrid Electromagnetism-Like Algorithm for Single Machine Scheduling Problem, Expert Systems with Applications, doi: 10.1016/j.eswa. 2007.11.050.
Birbil S.I. Feyzioglu O., 2003. A global optimization method for solving fuzzy relation equations. Lecture Notes in Artificial Intelligence 2715, 718-724.
Oda Y., 2002. An asymmetric analog of van der Veen conditions and the traveling salesman problem [II]. European Journal of Operational Research 138, 43-62.
Deıneko V.G. Hoffmann M. Okamoto Y. Woeginger J., 2006. The traveling salesman problem with few inner points. Operations Research Letters 34, 106-110.
Baki M.F., 2006. A new asymmetric pyramidally solvable class of the traveling salesman problem. Operations Research Letters 34, 613-620.
Lawler E. Lenstra J. Rinnooy Kan A. Shmoys D., 1985. The traveling salesman problem: a guided tour of combinatorial optimization. 3th. New York: Wiley.
Lin S. Kernighan B., 1973. An effective heuristic algorithm for the traveling salesman problem. Operations Research 21, 498–۵۱۶٫
Or I., 1976. Traveling salesman-type combinatorial problems and their relation to the logistics of regional bloodbanking. Ph.D. Thesis, Evanston, IL: North western University.
Tsubakitani S. Evans J., 1998. Optimizing tabu list size for the traveling salesman problem. Computers and Operations Research 25, 91–۹۷٫
Schmitt L. Amini M., 1998. Performance characteristics of alternative genetic algorithmic approaches to the traveling salesman problem using path representation: an empirical study. European Journal of Operational Research 108, 551–۵۷۰٫
Righini G. Trubian M., 2004. A note on the approximation of the asymmetric traveling salesman problem. European Journal of Operational Research 153, 255-265.
Mak V. Boland N., 2007. Polyhedral results and exact algorithms for the asymmetric traveling salesman problem with replenishment arcs. Discrete Applied Mathematics 155, 2093 – ۲۱۱۰٫
Choi C. Kim S. Kim H., 2003. A genetic algorithm with a mixedregion search for the asymmetric traveling salesman problem. Computers & Operations Research 30, 773–۷۸۶٫
فصل ۱
کلیات
۱-۱- مقدمه
برنامه ریزی۱ عبارتست از تصمیم گیری برای آینده و برنامه ریزی تولید به معنی تعیین استراتژی تولید به جهت نحوه تخصیص خطوط تولیدی برای پاسخگویی به سفارشات می باشد. از برجسته ترین موارد در تهیه برنامه زمانی تولید جهت خطوط تولیدی، تعیین اندازه انباشته و توالی سفارشات و نحوه تخصیص منابع در طول زمان است [۱].
ما همواره در مکالمات روزمره خود از اصطلاح زمانبندی۲ استفاده می کنیم، هر چند که ممکن است همیشه تعریف مناسبی از آن در ذهن نداشته باشیم. در حقیقت مفهوم آشنایی که ما عموما از آن استفاده می کنیم فهرستی از برنامه هاست و نه زمانبندی. مستندات و برنامه های ملموس همچون برنامه کلاسی، برنامه حرکت اتوبوس و غیره. یک برنامه معمولا به ما می گوید کی وقایع اتفاق می افتد. جواب به سئوالاتی که با کی شروع می شوند، معمولا اطلاعاتی در مورد زمان به ما می دهد. حرکت اتوبوس از ساعت ۶ شروع می شود و تا ساعت ۲۰ ادامه دارد. شام در ساعت ۲۱ سرو خواهد شد و مواردی از این دست. در برخی موارد نیز پاسخ ها به توالی وقایع اشاره می کند. اتوبوس پس از روشن شدن هوا حرکت می کند و شام پس از نظافت سالن سرو می شود. بنابراین سئوالاتی که با کی شروع می شوند، با اطلاعاتی در مورد زمان و یا توالی وقایع، که از برنامه بدست می آید پاسخ داده می شوند. فرآیند ایجاد برنامه، تحت عنوان زمانبندی شناخته می شود. هر چند که عموما برنامه ها ملموس و ساده به نظر می رسند، اما فرآیند ایجاد آنها بدون درک عمیقی از زمانبندی، پیچیده است. تهیه شام یک مسئله زمانبندی روزمره است که نیازمند انجام دادن کسری از فعالیتها است. مسائل زمانبندی در صنعت نیز ساختار مشابهی دارند. آنها شامل مجموعه ای از فعالیتها و مجموعه ای از منابع موجود جهت انجام آن فعالیتها است. همچنین در صنعت برخی از تصمیمات تحت عنوان تصمیمات برنامه ریزی شناخته می شوند. فرآیند برنامه ریزی، منابع لازم جهت تولید و مجموعه فعالیتهای مورد نیاز جهت زمانبندی را تعیین می کند. در فرآیند زمانبندی، ما نیازمند تعیین نوع و مقدار هر منبع هستیم و نتیجتا می توانیم زمان شدنی اتمام کارها را مشخص کنیم [۲]. زمانبندی، فرآیند تخصیص منابع محدود به فعالیت ها در طول زمان، جهت بهینه سازی یک و یا چند تابع هدف است. منابع شامل نیروی انسانی، ماشین آلات، مواد، تجهیزات کمکی و غیره می باشند.
عملیات های ماشین آلات، حرکتها، انتقالات و بارگیری ها و غیره نیز به عنوان مثالهایی از فعالیت مطرح می باشند. فعالیت ها می توانند دارای زودترین زمان شروع، دیرترین زمان خاتمه و زمان تحویل باشند. هدف از زمانبندی نیز مواردی چون حداقل زمان تکمیل جهت یک مجموعه از سفارشات، حداقل دیرکرد، حداکثر تعداد فعالیتها و یا سفارشات تکمیل شده در یک زمان مشخص، حداقل هزینه های راه اندازی، حداقل تعداد کارها یا سفارشات با تاخیر، حداکثر استفاده از منابع، حداقل موجودی میانی، تعادل در استفاده از منابع و غیره است. حال با توجه به اهداف مورد نظر و با عنایت به محدودیت های موجود، از قبیل ظرفیت تولید، ظرفیت منابع، میزان موجودی منابع، محدودیت بودجه و محدودیت زمان، مسئله زمانبندی و یا تخصیص منابع به فعالیتها در طول زمان انجام می گیرد [۳].
همانگونه که اشاره شد زمانبندی، تخصیص منابع در طول زمان برای اجرای مجموعه ای از وظایف است. این تعریف دو مفهوم مختلف را در بردارد. اولا زمانبندی نوعی تصمیم گیری است و فرایندی است که در جریان آن برنامه زمانی تعیین می شود. ثانیا زمانبندی مبحثی نظری است که مجموعه ای از اصول، مدلها، روشها و نتایج منطقی را در برمی گیرد، که برای ما بینشی عمیق در مورد عمل زمانبندی فراهم می آورد.
قدمهای دستیابی به تصمیمات زمانبندی را طبق رویکردی سیستمی می توان توصیف کرد. رویکرد سیستمی نشانگر ساختاری رسمی است که در عملکرد مدیریتی امروزی از حمایتی فزاینده برخوردار است. چهار مرحله اصولی رویکرد سیستمی، فرمولبندی، تحلیل، ایجاد و ارزیابی می باشد. در مرحله اول، اساسا مسئله را تعریف و ضابطه های حاکم بر تصمیم گیری را تعیین می کنند. این فعالیت، اغلب پیچیده و بغرنج است، ولی تصمیمات مناسب و خوب بدون تعریف روشن مسئله و مشخص کردن صریح اهداف به ندرت ممکن است اتخاذ شود. تحلیل، فرآیند مشروح بررسی عناصر مسئله و روابط متقابل آنها با یکدیگر است. هدف از این مرحله تعریف متغیرهای تصمیم گیری و نیز تشخیص روابط آنها با محدودیتهایی است که باید از آن پیروی کند. مرحله ایجاد، فرآیند ساختن گزینه های مختلف جواب مسئله و نقش آن، تعیین گزینه های ممکن است. بالاخره، ارزیابی مشتمل بر فرآیند مقایسه گزینه های امکانپذیر و انتخاب گزینه مطلوب جهت به کارگیری است. البته این انتخاب مبتنی بر ضابطه هایی است که در وهله نخست تعیین شده است.
بررسی مدلها و روشهای زمانبندی به توسعه مهارتها جهت صحت خروجی های مرتبط با مراحل چهارگانه کمک خواهد کرد. فرمولبندی ضابطه تصمیم گیری شاید مشکلترین فرم از این چهار مرحله باشد. آشنایی با مدلهای مناسب به انجام فرآیندهای تحلیل و ترکیب کمک می کند. مدلهایی که بررسی می شود عناصر و روابط متقابل مهمی دارد که بارها در مسائل زمانبندی مشاهده می شود. تئوری زمانبندی اصولا با مدلهای ریاضی سروکار دارد، یعنی بین کار زمانبندی و توسعه مدلهای زمانبندی رابطه برقرار می کند و بطور پیوسته آنها را با مسائل نظری و عملی محک می زند. دیدگاه نظری به طور غالب، دارای رویکری کمی است و سعی آن دست یافتن به ساختار مسئله در قالب شکل فشرده ریاضی است. به ویژه این رویکرد کمی، بابت تفسیر اهداف تصمیم گیری در قالب یک تابع هدف صریح و بیان موانع تصمیم گیری به صورت محدودیتهای صریح بکار گرفته می شود [۲]. تابع هدف آرمانی باید در برگیرنده تمام هزینه های سیستم برای اجرای تصمیمات مربوط به زمانبندی باشد. به هر حال، به هنگام اجرای آن در عمل، اندازه گیری یا حتی مشخص کردن کامل چنین هزینه هایی مشکل است. درحقیقت در فرآیند برنامه ریزی هزینه های عمده عملیاتی، تعیین می شوند، در حالی که تفکیک هزینه های کوتاه مدت دشوارتر است و آنها اغلب ثابت و به عنوان یک هزینه کلی به نظر می آیند. با وجود این، سه نوع اهداف تصمیم گیری در زمانبندی عمده تر به نظر می رسند: بهره برداری کارا از منابع، پاسخگویی سریع به تقاضا و انطباق دقیق موعدهای تحویل تعیین شده. غالبا می توان از یک ضابطه مهم هزینه ای مربوط به سنجش عملکرد سیستم (مانند زمان بیکاری ماشین، زمان انتظار برای انجام کار یا تاخیر کار) به عنوان جانشینی برای هزینه کل سیستم استفاده کرد. رویکردهای کمی مسائل مربوط به این معیارها در همه تحقیقات موجود در زمینه زمانبندی یافت می شود.
می توان مسائل زمانبندی بر اساس ترکیب منابع و طبیعت کار، تقسیم بندی کرد. مدل می تواند شامل یک و یا چند ماشین باشد. مجموعه کارها جهت فرآیند زمانبندی ممکن است ثابت باشد که در چنین شرایطی سیستم را ثابت می نامیم. همچنین ممکن است در طول فرآیند زمانبندی، کارهای جدید به سیستم اضافه شود که در این شرایط سیستم پویا نامیده می شود. معمولا دو نوع محدودیت در مسائل زمانبندی قابل بررسی است.
اولا، محدودیتهایی که مرتبط با دسترسی به منابع هستند.
ثانیا، محدودیتهای تکنولوژیکی که در ترتیب انجام کارها وجود دارد.
جواب مسئله زمانبندی، یافتن راه حلی امکانپذیر برای این دو نوع محدودیت است، به طوری که «حل» هر مسئله زمانبندی برابر با پاسخگویی به دو سوال زیر است:
کدام منبع برای انجام هر وظیفه تخصیص داده خواهد شد؟
هر وظیفه در چه وقت انجام خواهد شد؟
به عبارت دیگر، جوهره مسائل زمانبندی به تصمیم گیری در مورد تخصیص منابع و توالی عملیات منحصر می شود. نوشتارهای زمانبندی مملو از مدلهای ریاضی برای پاسخگویی به این دو سوال تصمیم گیری است. به طور سنتی، مسائل زمانبندی به صورت مسائل بهینه سازی دارای محدودیت به ویژه مسائل مربوط به تخصیص منابع و توالی عملیات مورد بررسی قرار گرفته است. در پاره ای از موارد مسئله
زمانبندی تنها مربوط به تخصیص منابع است و در این حالات مدلهای برنامه ریزی ریاضی معمولا می توانند برای تعیین تصمیمات در زمینه تخصیص منابع بهینه مورد استفاده قرار گیرند. عناصر مهم مدلهای زمانبندی، کارها و منابع اند. در تحقیقات مربوط به زمانبندی، منابع نوعا بر حسب قابلیتهای کمی و کیفی خود مشخص می شوند، به طوری که نوع و میزان هر منبع در مدل مشخص می شود. هر کار بر حسب اطلاعاتی از قبیل منبع مورد احتیاج، مدت انجام آن کار، زمانی که انجام آن را می توان شروع کرد و زمان تحویل آن توصیف می شود. به علاوه مجموعه ای از کارها بعضا می توانند بر حسب محدودیتهای تکنولوژیکی (روابط تقدمی) که در مورد عناصر متشکله آن صدق می کند بیان شوند.
تئوری زمانبندی همچنین شامل یکسری تکنیک های متعدد جهت حل مسائل زمانبندی است. در واقع، شاخه زمانبندی به یک کانون مرکزی برای توسعه، کاربرد و ارزیابی روشهای محاسباتی، تکنیک های شبیه سازی و رهیافت های حل ابتکاری۱ مبدل شده است. انتخاب رویکرد مناسب برای حل مسئله به طبیعت مدل و تابع هدف مسئله وابستگی زیادی دارد. در برخی موارد، استفاده از تکنیک جابجایی جهت حل توصیه می شود.
یک جنبه مفید جهت استنباط ارتباط مسائل زمانبندی و روشهای حل، شاخه جدید علوم کامپیوتر با نام تئوری پیچیدگی۲ است. عبارت پیچیدگی به میزان انرژی مورد نیاز جهت حل الگوریتم، اشاره دارد. به عنوان مثال در نظر بگیرید که می خواهیم یک الگوریتم را برای حل مسئله ای به اندازه n بکار گیریم (اندازه مسئله متناسب با مقدار اطلاعات مورد نیاز برای تشخیص مسئله است). تعداد محاسبات مورد نیاز جهت حل مسئله به وسیله یک الگوریتم خاص معمولا یک حد بالا بر اساس تابعی از n دارد. چنانچه درجه بزرگی این تابع با افزایش مقدار n بصورت یک چند جمله ای باشد، آنگاه ما می گوییم الگوریتم، چند جمله ای است. به عنوان مثال اگر درجه بزرگی تابع n2 باشد (بوسیله O(n)2 نمایش داده می شود)، الگوریتم چند جمله ای است و اگر تابع O(n)2 باشد تابع دیگر چند جمله ای نیست (در این حالت نمایی است).
گروهی از مسائل در دسته و یا کلاس مسائل ترکیبی دشوار۳ گروهبندی شده اند. در طول سالیان متمادی دانشمندان علوم ریاضی و کامپیوتر هیچ الگوریتم چند جمله ای را برای این دسته مسائل ارائه نکرده اند. مسائل بهینه سازی به دشواری این مسائل و یا حتی دشوارتر از آن، به عنوان مسائل کاملا سخت۴ شناخته می شوند. در این مسائل دستیابی به جواب بهینه بعضا دشوار و بسیار وقت گیر خواهد بود. بنابراین توسعه روشهای ابتکاری و دستیابی به جوابهای نسبتا خوب در این ارتباط با این مسائل می تواند کارایی بالایی داشته باشد. یک گروه آشنا از این دست مسائل، بحث زمانبندی و تصمیم گیری های مرتبط با آن می باشد.
در هر شرکت، یکی از مهمترین تصمیمات مدیران، انتخاب اندازه انباشته صحیح، انتخاب توالی تولید و همچنین زمانبندی است. به همین دلیل، این دسته مسائل در ادبیات پژوهش عملیاتی، توجه بسیاری از مقالات را به خود معطوف ساخته است. مسئله زمانبندی و اندازه انباشته به دو روش مختلف در ادبیات موضوع، مدل شده است. مسئله زمانبندی و اندازه انباشته گسسته که پنجره زمانی کوچک۱ هم خوانده می شود، افق برنامه ریزی را به پریودهای زمانی کوچک، تقسیم می کند به گونه ای که در هر پریود زمانی، حداکثر یک نوع محصول، قابل تولید است (شکل ۱-۱) [۴]. در این دسته از مسائل، اجرای تنظیم و تولید، تعداد صحیحی از پریودهای زمانی را شامل می شود. بنابراین این مسئله، برخی مواقع، مسئله سیکل تولید۲ نیز نامیده می شود [۴] و بصورت گسترده ای در ادبیات موضوع، مطالعه شده است. در مقابل، مسئله زمانبندی و اندازه انباشته با محدودیت ظرفیت۳ (CLSP) با نام پنجره زمانی بزرگ۴ معروف است. این مسئله، پریودهای زمانی بزرگتر که در هر پریود چندین محصول می تواند تولید شود را در نظر می گیرد. مدیر برنامه ریزی باید مقادیر تولید در هر پریود را به گونه ای که تمامی سفارشات در زمان مناسب پوشش داده شوند، برنامه ریزی کند.
دسته بندی کلی دیگر از تحقیقات انجام گرفته در زمینه مسائل زمانبندی بر اساس ماهیت و فضای محیط کاری و سیستم تولید است که بر اساس آن مسائل به چهار دسته تک ماشین، جریان کارگاهی، کار کارگاهی و تکنولوژی گروهی تقسیم بندی می شوند. حالت وجود یک ماشین جهت زمانبندی سفارشات کاملا مشخص است. در ادامه به شرح مختصری از بقیه فضاها پرداخته می شود.
جریان کارگاهی، استقرار تجهیزات تولید۵ بر اساس مراحل تولید هر محصول است و مواد در مسیر حرکت خود در هر مرحله تکمیل تر و نهایتا به محصول نهایی تبدیل می شود (شکل ۱-۲). در سیستم خط تولید، کارها۶ به اجزاء کوچکتری به نام عملیات۷ شکسته می شوند و هر عملیات بر روی یک ماشین
جداگانه انجام می شود. در حقیقت هر عملیات بعد از عملیات نخست، دقیقا یک پیش نیاز مستقیم و هر عملیات قبل از عملیات آخر، دقیقا یک پس نیاز مستقیم دارد [۲]. بنابراین هر کار شامل یک توالی مشخص از عملیاتها است که به منظور تکمیل کار باید انجام شود. این نوع ساختار تحت عنوان ساختار پیش نیازی خطی شناخته می شود. این سیستم تولیدی جهت تولید محصولات در حجم بالا و تنوع پایین مناسب است.
در جریان کارگاهی، m ماشین مختلف وجود دارد که در مدل جریان کارگاهی خالص۱، هر کار شامل m عملیات است که هر کدام باید روی یک ماشین خاص انجام شود. ماشین ها می توانند تحت عنوان ماشین های ۱، ۲، … و m شماره گذاری شوند و عملیاتهای کار j نیز می تواند بوسیله زوج های (j،۱)، (j،۲) … و (m,j)، نشان داده شود. بنابراین عملیاتها برابر با تعداد ماشین آلات است و هر کار باید روی تمامی ماشین آلات پردازش شوند (شکل ۱-۳). ولی در جریان کارگاهی عمومی۲، برخی کارها ممکن است تعداد عملیاتهای کمتری را نیاز داشته باشند (کمتر از تعداد ماشین آلات یا m) و نتیجتا آنها بر روی تمامی ماشین آلات پردازش نمی شوند. همچنین عملیاتها ابتدایی و انتهایی تمامی کارها ماشین های شماره ۱ و شماره m نخواهد بود (شکل ۱-۴).
مسائل کار کارگاهی از جریان کارگاهی متفاوت است. در این سیستم جریان کار هدایت شده نیست. اجزاء مسئله m ماشین و n کار است که باید زمانبندی شوند. هر کار همانند مدل خط تولید، شامل چند عملیات با ساختار پیش نیازی خطی است. در این سیستم استقرار تجهیزات تولید بر اساس نوع فرآیند است (شکل ۱-۵). هر چند یک کار می تواند هر تعداد عملیات داشته باشند، معمول ترین فرمولبندی کار گروهی، برای هر کار دقیقا m عملیات (یکی بر روی هر ماشین) مشخص می کند. یک مدل عمومی تر، پردازش یک کار بر روی یک ماشین، بیش از یک بار را مجاز می داند. هر ماشین می تواند به عنوان یک کارگاه جداگانه که ورودی و خروجی مخصوص به خود را دارد در نظر گرفته شود (شکل ۱-۶). مسلما این سیستم تولیدی قابلیت انطاف پذیری بالایی دارد و جهت تولید محصولات متنوع در مقادیر کم مناسب است [۲].
تکنولوژی گروهی نیز به عنوان یک فلسفه تولید از تشابه قطعات به لحاظ طرح و ساخت استفاده نموده و با استفاده از گروهبندی قطعه (یا ماشین) به دنبال افزایش بهره وری تولید است. در واقع این مورد یک حالت بینابین از دو محیط قبلی است. فضای کاری در این تحقیق بر اساس جریان کارگاهی در نظر گرفته شده است که در ادامه به شرح آن می پردازیم.
۱-۲- محدوده تحقیق و اهداف آن
سلولهای تولیدی۱ معمولا شامل یک گروه از ماشین آلات که به تولید محدوده مشخصی از خانواده ها۲ تخصیص داده شده اند می باشد. یک خانواده یک مجموعه اقلام۳ است که نیازمندی مشترکی به لحاظ ابزار و توالی های عملیاتی دارند. در این محیط، تولید سلولی نیازمند سه فعالیت برنامه ریزی، قبل از تولید واقعی است. نخست گروهبندی ماشین آلات در سلولهای تولیدی مختلف (فرم دهی سلولها۴). دوم، اقلام باید به ماشین آلات مشخص در سلولهای تولیدی، تخصیص داده شوند (بار دادن به ماشین آلات۵). سوم، اقلام باید در هر سلول تولیدی زمانبندی شوند [۵ و ۶]. اغلب چنین مسائل زمانبندی شامل سلولهای تولیدی چندتایی و احتمالا پیچیده است. بنابراین تلاشهایی در جهت توسعه مفهوم زمانبندی جهت یک سلول تولیدی در یک
زمان صورت گرفته است. این بخش از تحقیق به مسئله زمانبندی چند سفارش۱ دریافتی از چند مشتری در فضای جریان کارگاهی جایگشتی۲ با فرض آنکه فعالیتهای مرتبط با فرم دهی و بار دادن انجام گرفته، می پردازد. هر سفارش می تواند به عنوان یک خانواده و هر کار به عنوان یک قلم در نظر گرفته شود. البته یک تفاوت عمده وجود دارد و آن این است که همه سفارشات به ابزار و توالی های عملیاتی یکسانی نیاز دارند.
در فرم دهی و باردادن سلولهای تولیدی، اقلام خانواده بر اساس توالی های عملیاتی به سلولها تخصیص می یابد. بنابراین جریان مواد و زمانبندی، حتی چنانچه اقلام تولیدی نیازمند ابزار متفاوتی جهت تنظیمات باشند، ساده می شود. در این فرآیند ممکن است هر خانواده نیازمند ماشین آلات مشابهی باشد و مسلما اقلام با ترتیب مشخصی بر روی ماشین آلات پردازش می شوند. این سلولهای تولیدی سلول تولیدی جریان کارگاهی خالص نام دارند و مشخص کننده جریان کارگاهی معمول می باشند. این شرایط در زمان وجود چندین خانواده با نیازمندی های متفاوت صادق نخواهد بود [۵]. معمولا یک هزینه تنظیم عمده جهت تغییر پردازش از کارها در یک سفارش به سفارش دیگر نیاز است.
یکی از شناخته شده ترین مسائل زمانبندی مسئله زمانبندی جریان کارگاهی است. این مسئله برای بیش از پنجاه سال در میان محققین جایگاه ویژه ای را برای خود باز کرده است. در این مسئله m مرحله بصورت سری وجود دارد که در هر مرحله یک ماشین یا بیشتر وجود دارد. n کار باید بر روی m ماشین پردازش شوند. هر کار بر روی هر ماشین، یک زمان پردازش مثبت دارد. در جریان کارگاهی، همه کارها با یک ترتیب بر روی ماشین آلات پردازش می شوند. زمان پردازش هر کار در هر مرحله می تواند متفاوت باشد. در این شرایط برای هرماشین n! توالی از کارها وجود خواهد داشت و در کل برای مسئله (n!)m توالی ممکن خواهیم داشت. یک ساده سازی در این ارتباط، حفظ ترتیب پردازش کارها از ماشین ۱ تا ماشین m است. این بدان معنی است که کارها با یک ترتیب بر روی همه ماشین آلات پردازش شوند. چنین مسئله ای تحت عنوان مسئله جریان کارگاهی جایگشتی شناخته می شود. در این حالت به اندازه n! توالی برای کارها وجود خواهد داشت که با این شرایط مسئله تحت عنوان مسئله کاملا سخت شناخته می شود [۵].
از جمله صنایعی که مسائل زمانبندی جریان کارگاهی جایگشتی بصورت کاملا برجسته و حیاتی مطرح می باشد، صنعت نساجی، کابل و رنگ است. در این تحقیق سعی بر آن بوده است تا با ایده گرفتن از چنین صنایعی در دنیای واقعی، تعریف متفاوتی از مسئله زمانبندی بر اساس ماهیت این صنایع در شرایط واقعی ارائه گردد. در حقیقت در این تحقیق ما یک سلول تولیدی تکی که شامل تعدادی ماشین آلات (مراحل) و تعدادی سفارش که باید بر روی ماشین آلات پردازش شوند را در نظر می گیریم. هر سفارش یک مشتری مشخص دارد و شامل تعداد مشخصی از کارهای مشابه است. کارهای هر سفارش باید از طریق سلولهای
تولید، مرحله به مرحله پردازش شوند و زمانی که اولین کار یک سفارش شروع به پردازش شد، کارهای متعلق به سفارشات دیگر تا زمان پردازش آخرین کار سفارش مربوطه نمی توانند پردازش شوند. در حقیقت انقطاع سفارش در هنگام پردازش مجاز نبوده ولی چنین کاری در هنگام ارسال سفارش امکان پذیر است. بدیهی است عدم امکان انقطاع سفارش در هنگام پردازش به دلیل هزینه های تنظیم بالا، در این گروه از صنایع و به خصوص در صنعت نساجی می باشد. کارهای متعلق به یک سفارش دقیقا شبیه به یکدیگر هستند و بنابراین زمان یا هزینه تنظیمی میان دو کار از یک سفارش وجود ندارد. هر سفارش با توجه به مشتری مربوطه، زمان تحویل و هزینه تاخیر مشخص دارد و هزینه های تاخیر به ازای هر واحد از سفارش که با تاخیر ارسال می گردد و هر واحد زمانی تاخیر محاسبه می شود. به همین منظور و به جهت کاهش هزینه های تاخیر، انقطاع سفارش در هنگام ارسال برای مشتری امکان پذیر خواهد بود چراکه هر واحد از یک سفارش با تاخیر که زودتر به دست مشتری برسد هزینه تاخیر کمتری خواهد داشت. هزینه و زمان تنظیم اولین کار از هر سفارش به زمانبندی قبلی بستگی دارد. این شرایط منطبق با بسیاری از مسائل دنیای واقعی است. برای مثال در صنعت نساجی و به خصوص در فرآیند رنگرزی و ریسندگی (همه انواع الیاف مانند اکریلیک، پلی استر و A-10) تعدادی سفارش وجود دارد که تفاوت میان آنها رنگ آنهاست. هر سفارش اندازه مشخصی دارد و زمان و هزینه تنظیم کاملا وابسته به توالی است (فرآیند تمیزکاری و انجام برخی تنظیمات برای رنگ جدید بسته به رنگ قبلی است).
از سوی دیگر برخی توالی ها در تولید هزینه زیادی را تحمیل می کنند و ممکن است غیر منطقی باشند. به عنوان مثال در صنعت ریسندگی، تولید الیاف با رنگ کاملا روشن (سفید، کرم روشن) بعد از الیاف با رنگ کاملا تیره (سیاه، سورمه ای و زرشکی) هزینه تنظیم بسیار بالایی دارد (بیش از دو روز فرآیند تمیز کاری و حداقل به ازای هر ماشین یک و یا دو سبد ضایعات). عدم امکان پذیری این توالی ها بسته به حد بالای هزینه تولید است. مسلما با توجه به قیمت فروش، هر سفارش یک حد بالا جهت هزینه های تولید دارد که تولید با بیشتر از آن هزینه، غیر منطقی است. شرایط مشابهی نیز در صنعت کابل در شرایطی که رشته سیم های رنگی تولید می شوند وجود دارد. می توان مثالهای متعددی به خصوص در صنایع شیمیایی و صنایع نساجی پیدا نمود که این شرایط صادق باشد. جدای از وابستگی میان توالی ها، این عدم امکان پذیری برخی از توالی ها (بر اساس حد بالای هزینه تولید) در ادبیات موضوع کاملا نادیده گرفته شده است.
همچنین ما به دنبال یک تابع هدف واقعی برای مسئله هستیم. با یک مرور سریع در ارتباط با ادبیات موضوع ما با بسیاری از معیارها در ارتباط با تابع هدف مواجه می شویم. ولی در فرآیند زمانبندی، تابع هدف باید شامل بر همه هزینه های سیستم که وابسته به تصمیمات زمانبندی هستند باشد [۲]. در مسائل زمانبندی
دنیای واقعی، در نظرگیری اجزاء هزینه و معیارهای گوناگون تصمیم اهمیت زیادی دارد و صرفا لحاظ نمودن یک معیار عمده (همانند زمان ختم کل که در بسیاری از تحقیقات پیشین به چشم می خورد) سئوال برانگیز است.
در این تحقیق فرض بر وجود استراتژی تولید جهت سفارش۱ است. در این استراتژی، تولید بر اساس سفارشات رسیده انجام می شود و برخلاف استراتژی تولید جهت انبار۲ که ابتدا تولید انجام شده و سپس کالا در انبار به منظور یافتن مشتری مناسب نگهداری می شود، کالایی بدون وجود سفارش از طرف مشتری تولید نخواهد شد. انبوهی از سفارشات در پریود نخست دریافت می شوند که تعدادی از آنها بر اساس توان تولید قبول و بقیه رد می شوند. این فرضیات نیز بر اساس شرایط دنیای واقعی جهت صنایع ذکر شده در نظر گرفته شده اند. منابع تولید باید به گونه ای زمانبندی شوند تا تمامی هزینه های ملموس چون هزینه دیرکرد، هزینه تنظیم و هزینه نگهداری که از جمله حیاتی ترین معیارها در مباحث زمانبندی و برنامه ریزی تولید در بسیاری از صنایع است، حداقل شود. در چنین شرایطی قائدتا یک مدل زمانبندی چند معیاره نیاز است.
همانگونه که از توضیحات بر می آید در تحقیق حاضر، کارها در مسائل جریان کارگاهی معمول با سفارشات جایگزین شده اند. زمانبندی تعدادی از سفارشات که هر سفارش حاوی تعداد مشخصی از کارهای مشابه و یک مشتری مشخص با زمان تحویل قطعی و همچنین هزینه تاخیر مشخص است، محور اصلی تحقیق است. در مسئله مورد بررسی هزینه های نگهداری و تاخیر اهمیت فراوان دارد. در این گونه مسائل، تصمیمات زمانبندی دو سطح دارد. در سطح بالاتر زمانبندی سفارشات قرار دارد به نحوی که کدام سفارش و به چه نحوی و با چه ترتیبی باید پردازش شود. سطح بعدی زمانبندی کارهای داخل هر سفارش است به این ترتیب که کارها با چه ترتیبی و به چه شکلی باید پردازش شوند. در اینجا صرفا سطح نخست بررسی می شود و ترتیب پردازش کارهای داخل هر سفارش، موضوع این تحقیق نیست. در مسئله مورد بررسی، زمان و هزینه های تنظیم مهم و وابسته به توالی می باشند. کارهای داخل هر سفارش کاملا مشابه فرض می شوند و زمان و هزینه تنظیم میان دو کار از یک سفارش نادیده گرفته می شود. همچنین فرض می شود برخی از توالی ها میان سفارشات ناممکن باشد. همانگونه که در ادامه تحقیق تحلیل خواهد شد اضافه نمودن چنین فرضی، یافتن یک جواب اولیه برای مسئله مورد بررسی بر اساس روشهای ابتکاری موجود را بسیار دشوار می سازد. یک زمان تحویل مشخص و هزینه تاخیر معین برای هر سفارش (بر اساس نظر مشتری آن) فرض می شود. هدف حداقل نمودن هزینه های تنظیم، تاخیر و نگهداری می باشد.
همانگونه که در ادامه بررسی خواهد شد با توجه به خصوصیات مسئله مورد بررسی روشهای ابتکاری موجود در حل مسئله چندان کارا نمی باشند بنابراین در این تحقیق یک روش ابتکاری جهت یافتن جواب
اولیه و همچنین یک روش ابتکاری جهت بهبود جواب اولیه بر اساس روش شبیه سازی تبریدی۱ به منظور حل مسئله زمانبندی ارائه خواهد شد.
در مجموع، عدم توجه به گروه عظیمی از مسائل زمانبندی در دنیای واقعی در ادبیات موضوع، انگیزه اصلی طرح مسئله حاضر می باشد که با توجه به کاربردی بودن آن می تواند به عنوان یک ضرورت در تحقیق مطرح باشد. مسلما چنین توجهی به مسائل زمانبندی در صنایع با توجه به فرضیات واقعی آن می تواند فاصله عمیقی که بعضا میان مسائل دنیای واقعی و مباحث علمی وجود دارد را کاهش داده و سرفصل جدیدی را جهت این دسته از مسائل بگشاید. همانگونه که در ادامه بصورت برجسته تر مطرح می گردد، عمده تولیدات علمی در زمینه مسائل زمانبندی در سابقه موضوع بر اساس شرایط بسیار محدود از دنیای واقعی بوده و انگیزه اصلی در پرداختن به آنها عمدتا شکست روشهای ابتکاری با توسعه بیشتر آنها می باشد. مسلما درنظرگیری شرایط دنیای واقعی موجب پیچیده تر شدن مسئله خواهد شد که در این حیطه استفاده از روشهای فراابتکاری موثر راهگشا خواهد بود. متدولوژی کلی تحقیق منطبق بر گام های ذیل می باشد:
۱) تشریح شرایط زمانبندی در صنایعی چون نساجی، کابل و رنگ
۲) مدلسازی مسئله با توجه به فرضیات واقعی
۳) حل مسئله با بکارگیری یک روش ابتکاری شامل بر:
۳-۱) ساخت جواب اولیه با کمک گرفتن از دانش تئوری گراف
۳-۲) بهبود جواب اولیه با استفاده از روش ترکیبی شبیه سازی تبریدی
۴) مقایسه روش ارائه شده با یک روش مناسب در ادبیات موضوع
۵) حذف برخی فرضیات مسئله جهت نزدیک شدن به مسائل معروف زمانبندی که در مرور ادبیات بصورت گسترده به آن پرداخته شده است.
۶) توسعه روشهای ترکیبی مختلف بر اساس الگوریتم ژنتیک، بهینه سازی جامعه مورچگان و الکترومغناطیس به منظور شکست بهترین روشهای فراابتکاری موجود در ادبیات موضوع
۱-۳- مرور ادبیات
تمام مقالات و پایان نامه و پروژه ها به صورت فایل دنلودی می باشند و شما به محض پرداخت آنلاین مبلغ همان لحظه قادر به دریافت فایل خواهید بود. این عملیات کاملاً خودکار بوده و توسط سیستم انجام می پذیرد.
جهت پرداخت مبلغ شما به درگاه پرداخت یکی از بانک ها منتقل خواهید شد، برای پرداخت آنلاین از درگاه بانک این بانک ها، حتماً نیاز نیست که شما شماره کارت همان بانک را داشته باشید و بلکه شما میتوانید از طریق همه کارت های عضو شبکه بانکی، مبلغ را پرداخت نمایید.
ارسال نظر