مدل‌سازی و حل یک مسأله زمان بندی دو معیاره در یک سیستم تولید سلولی با در نظر گرفتن زمان‌های آماده‌سازی وابسته به توالی سلول‌ها

نوع مقاله : مقاله پژوهشی

نویسندگان

1 نویسنده مسئول و استاد گروه مهندسی صنایع، پردیس دانشکدههای فنی، دانشگاه تهران:

2 دانش آموخته کارشناسی ارشد گروه مهندسی صنایع، پردیس دانشکدههای فنی، دانشگاه تهران

چکیده

در این مقاله، یک مدل برنامه‌ریزی ریاضی عدد صحیح مختلط دو معیاره برای زمان بندی سلول‌ها و قطعات در هر سلول به­طور همزمان در یک سیستم تولید سلولی[i](CMS) ارائه می‌شود. هدف این مدل، کمینه کردن زمان کل تکمیل ساخت قطعات و حرکت بین سلولی قطعات با در نظر گرفتن زمان‌های راه‌اندازی وابسته به توالی خانواده قطعهاختصاص یافته به سلول‌ها می‌باشد. در طراحی و برنامه‌ریزی سیستم تولید سلولی، سه مرحله اصلی می‌بایست مد نظر قرار گیرد که شامل تشکیل سلول، استقرار سلول‌ها و ماشین‌ها، و زمان بندی آنها است. از آنجا که این مدل پیشنهادی و مسأله زمانبندی CMS جزء مسایل چندجمله­ای نامعین سخت[ii] است، از الگوریتم ژنتیک[iii](GA)  به‌عنوان یکی از روش‌های فراابتکاری کارامد برای حل مدل استفاده می‌شود. در پایان برای نشان دادن کارایی این الگوریتم پیشنهادی، چند مسأله نمونه حل شده، نتایج محاسباتی مربوطه با نتایج به­دست آمده به کمک یک ابزار بهینه‌ساز مورد مقایسه قرار می‌گیرد.


[i] Cellular Manufacturing Systems


[ii] Non–Deterministic Polynomial Hard )NP-Hard(


[iii] Genetic Algorithm

کلیدواژه‌ها

عنوان مقاله [English]

Modeling and Solving of a Bi-Criteria Scheduling Problem for a Cellular Manufacturing System with Sequence-Dependent Cell Setup Times

نویسندگان [English]

  • Reza Tavakkoli-Moghaddam 1
  • Azadeh Nasri 2
چکیده [English]

This paper presents a new, bi-criteria mixed-integer programming model for scheduling cells (part families) and parts within each cell in a manufacturing cellular system. The objective of this model is to minimize the makespan and inter-cell movements simultaneously, while considering sequence-dependent cell setup times. In the CMS design and planning, three main steps must be considered, namely cell formation (i.e., part families and machine grouping), inter and intra-cell layouts, and scheduling issue. Due to the NP-hardness of the proposed model and the scheduling problem in the CMS, a genetic algorithm (GA) as an efficient meta-heuristic method is proposed to solve such a hard problem. Finally, a number of test problems are solved to show the efficiency of the proposed GA and the related computational results are compared with the results obtained by the use of an optimization tool.

کلیدواژه‌ها [English]

  • Scheduling
  • Cellular Manufacturing System
  • Sequence-Dependent Setup Times
  • genetic algorithm

مراجع

[1] Soleymanpour, M., Vrat, P., Shankar, R., "A transiently chaotic neural network approach to the design of cellular manufacturing", International Journal of Production Research, Vol. 40 (10), p.p. 2225–2244, 2002.
[2] Yoshida, T., Hitomi, K., "Optimal two-stage production scheduling with setup times separated", AIIE Transactions, Vol. 11, p.p. 261–263, 1979.
[3] Sekiguchi, Y., "Optimal schedule in a GT-type flow-shop under series-parallel precedence constraints", Journal of the Operations Research Society of Japan, Vol. 26, p.p. 226–251, 1983.
[4] Baker, K.R., "Scheduling groups of jobs in the two machine flow shop", Mathematical and Computer Modeling, Vol. 13, p.p. 29-36, 1990.
[5] Yang, D.L., Chern, M..S., "Two-machine flow shop group scheduling problem", Computers & Operations Research, Vol. 27, p.p. 975–985, 2000.
[6] Hitomi, K., Ham, I., "Operations scheduling for group technology applications", Annals of the CIRP, Vol. 25 (1), p.p. 419–422, 1976.
[7] Logendran, R., Sriskandarajah, C., "Two-machine group scheduling problem with blocking and anticipatory setups", European Journal of Operational Research, Vol. 69 (3), p.p., 467–481., 1993.
[8] Logendran, R., Nudtasomboon, N., "Minimizing the makespan of a group scheduling problem: A new heuristic", International Journal of Production Economics, Vol. 22, p.p. 217–230, 1991.
[9] Nawaz, M., Enscore, J.E.E., Ham, I., "A heuristic algorithm for the m-machine, n-job flow shop sequencing problem", OMEGA: International Journal of Management Science, Vol. 11 (1), p.p. 91–95., 1983.
[10] Wemmerl. ov, U., Vakharia, A.J., "Job and family scheduling of a flow-line manufacturing cell: A simulation study", IIE Transactions, Vol. 23 (4), p.p. 383–393, 1991.
[11] Mahmoodi, F., Dooley, K.J., "Group scheduling and order releasing: Review and foundations for research", Production Planning & Control, Vol. 3 (1), p.p. 70–80, 1992.
[12] Eom, D.H., Shin, H.J., Kwun, I.H., Shim, J.K., Kim, S.S., "Scheduling jobs on parallel machines with sequence-dependent family setup times". Advanced Manufacturing Technology, Vol. 19, p.p. 926–932, 2002.
[13] Logendran, R., Mai, L., Talkington, D., "Combined heuristics for bi-level group scheduling problems", International Journal of Production Economics, Vol. 38, p.p. 133–145, 1995.
[14] Campbell, H.G., Dudek, R.A., Smith, M.L., "A heuristic algorithm for the n job, m machine sequencing problem", Management Science, Vol. 16, p.p. 630-637. 1970.
[15] Yang, W. H., Liao, C. J., "Group scheduling on two cells with inter-cell movement", Computers & Operations Research, Vol. 23 (10), p.p. 997–1006, 1996.
[16] Schaller, J., "A new lower bound for the flow shop group scheduling problem", Computers & Industrial Engineering, Vol. 41, p.p. 151–161, 2001.
[17] Schaller, J.E., Gupta, J.N.D., Vakharia, A.J., "Scheduling a flowline manufacturing cell with sequence dependent family setup times". European Journal of Operational Research, Vol. 125, p.p. 324–339, 2000.
[18] Franca, P.M., Gupta, J.N.D., Mendes, A.S., Moscato, P., Veltink, K.J., "Evolutionary algorithms for scheduling a flowshop manufacturing cell with sequence dependent family setups". Computers & Industrial Engineering, Vol. 48 (3), p.p. 491–506, 2005.
[19] Hendizadeh, S.H., Faramarzi, H., Mansouri, S.A., "Meta-heuristics for scheduling a flowline manufacturing cell with sequence dependent family setup times". International Journal of Production Economics, Vol. 111 (2), p.p. 593-605, 2008.
[20] Tavakkoli-Moghaddam, R., Gholipour-Kanani, Y., Cheraghalizadeh, R., "A genetic algorithm and memetic algorithm to sequencing and scheduling of cellular manufacturing systems", International Journal of Management Science and Engineering Management, Vol. 3 (2), pp. 119-130, 2008.
[21] Holland, J.; Adaptation natural and artificial systems, University of Michigan press, An Arbor, MI, MIT Press, Cambridge, Ma, 1975.
[22] Gen, M., Cheng, R.; Genetic algorithms & engineering design, New York, A Wiley Interscience Publication, 1997.

فایل ها

هم رسانی

ارجاع به این مقاله

آمار