۶٫ کاهش در موجودی کالاهای تمام شده

۳۸

۳۹٫۳

۰٫۰

۱۰۰٫۰

۷٫ بهبود در کیفیت قطعه/ محصول

۳۹

۲۸٫۴

۰٫۰

۶۲٫۵

۸٫ کاهش در هزینه های هر واحد از کالا

۳۸

۱۶٫۰

۰٫۰

۶۰٫۰

ومرلوف و جانسون[۱۳] بررسی مشابهی را در آزمایشهای پیاده سازی و بهبودهای عملکرد تولید سلولی در ۴۶ کارخانه انجام دادند. در این بررسی، محصولات تولید شده در این ۴۶ کارخانه محصولات و اجزای الکتریکی و الکترونیکی، دستگاههای جابجایی سیالات و کنترل جریان، ماشین آلات و ماشین ابزارها، محصولات و اجزای گرمایشی و سرمایشی، ابزارها، موتورها و یاطاقانها میباشند. توجه کنید که شرکت های بررسی شده در این قسمت، شرکت های قبلی در بررسی توسط ومرلوف و هایر[۲۵] نیستند. جدول ۲-۳ بهبودهای عملکرد گزارش شده را نمایش میدهد.
تولید سلولی به عنوان یک شرط لازم برای تولید به موقع (JIT) در نظر گرفته میشود[۲۴]. JIT به سیستمهای تولیدی که زمان راه اندازی کوچک یا صفر، اندازههای انباشته کوچک (حجم محصول کم)، و موجودی کم داشته باشند، نیاز دارد. واضح است که تولید سلولی برای چنین شرایطی مناسب میباشد. بلاک[۴۰] [۹] همچنین تأکید کرده است که تشکیل سلولهای تولیدی اولین گام مهم برای رسیدن به تولید JIT است.

۲-۳-۱-۲- معایب تولید سلولی

هزینه‌های بالای انجام کار.
سازماندهی مجدد چیدمان موجود می‌تواند یک کار پرهزینه‌ای باشد، صرف نظر از کوشش‌هایی که برای فرآیند تعیین سلول‌های تولیدی و خانواده قطعات لازم است.
مشکلات مرتبط با خراب شدن، اضافه بار، بیکاری و ایجاد تعادل ماشین‌ها.
در یک سلول تولیدی خاص، هر ماشین برای صحیح کار کردن سلول مربوطه مهم و بحرانی است. خراب شدن یک ماشین خاص باعث می‌شود کل سلول فلج شود. در واقع در این نوع سیستم تولیدی انعطاف لازم جهت انتخاب کردن یک ماشین جایگزین، مانند تولید کارگاهی، وجود ندارد. علاوه بر این، مشکلات مربوط به استفاده بیش از حد برخی از ماشین‌های یک سلول و همچنین ایجاد تعادل در بار کاری یک سلول، از دیگر ضعف‌های موجود در یک سیستم تولید سلولی است.
نیاز به نیروی کار ماهر و آماده برای کارهای جدید.
نیروی کار در سیستم تکنولوژی گروهی باید آماده کار با شرایط جدید باشد یعنی باید قادر باشد که با انواع ماشین‌ها و ابزارهای داخل سلول کار کند، بر خلاف تولید کارگاهی که در آن لازم است تا نیروی کار تنها برای کار با یک نوع ماشین آموزش داده شود، بدین ترتیب هزینه آموزش نیروی کار ممکن است زیاد باشد.

4. مشکل هم زمان کردن قطعات مختلف برای مونتاژ شدن با هم در مراحل بعدی.

قطعات یا اجزا پیش مونتاژی که در سلول‌های مختلف ساخته می‌شوند ممکن است لازم باشد تا در مراحل بعدی با هم مونتاژ شوند بنابراین ممکن است هم زمان کردن تولید این نوع قطعات جهت مونتاژ با هم، کار مشکلی باشد.

• تعامل بین ” بهترین طرح تولیدی” و “طرح تولیدی مناسب”.

اغلب باید یک موازنه بین بهترین مسیر تولیدی ممکن و آن مسیری که نهایتاً برای یک قطعه انتخاب می‌شود تا آن قطعه را به یک سلول تولیدی خاص محدود کند، ایجاد شود.

6. مشکلات مربوط به عملیات‌های خارج از سلول.

در اکثر کاربردهای عملی معمولاً محدود ساختن تمامی عملیات مورد نیاز یک قطعه، درون سلول تولیدی مربوطه مقدور نیست، بدین ترتیب بعضی قطعات باید برای بعضی عملیات به سلول‌های دیگر برده شوند. این کار مشکلاتی را برای جابجا کردن قطعات بوجود می‌آورد.

7. تغییر در طیف تولید و ترکیب آن.

با تغییر دادن طیف‌های محصولات، امکان تغییر چیدمان سیستم تولیدی یا ترکیب سلول‌های تولیدی، بطور مداوم و متناسب با این تغییرات میسر نمی‌باشد، در نتیجه ممکن است این امکان وجود داشته باشد که بعضی مراکز کاری با بار کاری بیش از حد مواجه شوند در حالی که دیگر مراکز کمتر از توانشان کار می‌کنند.

۲-۴- زمانبندی

زمانبندی تخصیص منابع در طول زمان برای اجرای مجموعهای از وظایف است[۳۲]. این تعریف نسبتاً کلی واژه دو مفهوم مختلف را دربردارد: اولاً، زمانبندی نوعی تصمیمگیری است و فرآیندی است که در جریان آن برنامه زمانی را تعیین میکند. از این لحاظ بیشتر آموختههای ما در مورد زمانبندی را میتوان در مورد تصمیمگیریهای دیگر نیز به کار بست و لذا این مبحث ارزش عملی عام دارد. ثانیاً زمانبندی مبحثی نظری است که مجموعهای از اصول، مدلها، روشها و نتایج منطقی را در برمیگیرد، که برای ما بینشی عمیق در مورد عمل زمانبندی فراهم میآورد. از این لحاظ نیز بیشتر آموخته های ما در مورد زمانبندی را میتوان در مورد سایر نظریه ها بکار برد و بنابراین ارزش مفهومی عام دارد.
مسأله عملی تخصیص منابع در طول زمان برای اجرای مجموعهای از کارها، در وضعیتهای مختلف مطرح میشود. اما در بیشتر موارد عمل زمانبندی کارها پس از حل برخی مسائل مربوط به برنامه‌ریزی اصولی مورد توجه قرار می‌گیرد، و باید همواره این نکته را مد نظر داشت که تصمیمات مربوط به زمانبندی اهمیت کمتری نسبت به مجموعه وسیع‌‌تری از تصمیمات مدیریتی دارد. به عنوان مثال در حل مسائل مربوط به ساخت، مسائل اساسی مدیریتی مربوط به انتخاب محصولی که باید ساخته شود و تعیین میزان تولید هر محصول اولویت دارد. بعد از به کارگیری بررسی بازار و تحلیل‌های اقتصادی برای حل این گونه مسائل، برنامه‌ریزی تکنولوژیکی را بر این مسئله که محصول چگونه باید ساخته شود متمرکز می‌کنند و تنها بعد از اینکه جواب این سوالات مربوط به برنامه‌ریزی داده شد و در دسترس بودن منابع دانسته شد، زمان برای توجه به مسائل زمانبندی مناسب است. حال برای روشن‌تر شدن موضوع مثال دیگری می‌آوریم: مسائل اساسی مدیریتی در ارائه خدمات درمانی مستلزم طراحی و تعیین تعداد خدمات و میزان کارایی و خدمتدهی در هر مورد است. برنامه‌ریزی تکنولوژیکی پس از آن به مسائلی همچون طراحی کارخانه، میزان بهره‌برداری از تجهیزات و گسترش نیروی انسانی در مراحل بعدی مربوط می‌شود. وقتی که با اتخاذ این تصمیمات نموداری از منابع دسترسپذیر فراهم شد می‌توان به مسائل زمانبندی پرداخت.
این مثالها نشان می‌دهد که چطور تصمیمات اصولی مدیریت به مسائل سه گانه زیر مرتبط می‌شوند.

1. چه محصول یا خدمتی قرار است عرضه شود؟

1. در چه مقیاسی قرار است عرضه شود؟

1. چه منابعی قرار است تأمین شود؟

پاسخ دادن به این پرسش‌ها، کار برنامه‌ریزی است. در مقابل در کار زمانبندی فرض بر این است که جواب این پرسش‌ها از پیش فراهم شده است. بنابراین، کار زمانبندی صرفاً به وضعیتی مربوط می‌شود که در آن طبیعت کارهایی که باید زمانبندی شود توصیف شده و ترکیب منابع موجود تعیین شده باشد. در واقع زمانبندی ابزاری است که استفاده از منابع در دسترس را بهینه می‌کند. منابع و کارها در زمانبندی ممکن است انواع گوناگونی داشته باشد. منابع ممکن است ماشین‌ها در کارگاه‌ها، مسیرها در فرودگاه، کارگران یک کارگاه ساختمانی، واحدهای پردازش کننده در یک محیط محاسباتی و غیره باشد[۳۲].
در عمل کارهای برنامه‌ریزی و زمانبندی کاملاً مستقل از هم نیست. برای روشن‌تر شدن این امر سناریوی نمونه زیر را در نظر بگیرید: برنامه‌ریز ابتدا وظایفی را که باید انجام شود مشخص و حدودی برای میزان منابع دسترس‌پذیر تعیین می‌کند. سپس زمانبند این اطلاعات را می‌گیرد و مشخص می‌کند که منابع موجود چگونه به انجام کارهای تعیین شده تخصیص یابند.
نظریه زمانبندی اصولاً با مدل‌های ریاضی سروکار دارد و بین کار زمانبندی و توسعه مدل‌های زمانبندی رابطه برقرار می‌کند و به طور پیوسته آن‌ها را با مسائل نظری و عملی زمانبندی محک می‌زند. دیدگاه نظری به طور غالب رویکردی کمی ‌است و سعی آن دست یافتن به ساختار مساله در قالب شکل فشرده ریاضی است. به ویژه، این رویکرد کمی با تفسیر اهداف تصمیم‌گیری در قالب یک تابع هدف صریح و بیان موانع تصمیم‌گیری به صورت محدودیت‌های صریح شروع می‌شود[۳۳].
تابع هدف آرمانی باید دربرگیرنده تمام هزینه های سیستم برای اجرای تصمیمات مربوط به زمانبندی باشد. به هر حال، به هنگام اجرای آن در عمل، اندازه گیری یا حتی مشخص کردن کامل چنین هزینه هایی مشکل است. در حقیقت، هزینه های عمده عملیاتی (و به آسانی قابل تشخیص ترین آنها) را کار برنامه ریزی، تعیین میکند، در حالی که تفکیک هزینه های کوتاه مدت دشوار است و آنها اغلب ثابت به نظر میآیند.
با وجود این، سه نوع از اهداف تصمیم‌گیری در زمانبندی عمده‌تر به نظر می‌رسند: بهره‌برداری کارا از منابع، پاسخگویی سریع به تقاضا و انطباق دقیق زمان‌های تحویل، موعدهای تحویل تعیین شده. غالباً می‌توان از یک ضابطه مهم هزینه‌ای مربوط به سنجش عملکرد سیستم مانند زمان بیکاری ماشین، زمان انتظار برای انجام کار یا تأخیر کار به عنوان جانشینی برای هزینه کل سیستم استفاده کرد.
دو نوع از محدودیت‌های مربوط به امکان‌پذیری معمولاً در مسائل زمانبندی ظاهر می‌شود: اولاً محدودیت‌هایی در دسترس‌پذیری منابع وجود دارد، ثانیاً محدودیت‌های تکنولوژیکی در ترتیب انجام کارها وجود دارد. جواب هر مسأله زمانبندی یافتن راه حلی امکان‌پذیر برای این نوع محدویت است. به گونه ای که حل هر مسأله زمانبندی برابر با پاسخگویی به این دو سوال است:

1. کدام منبع برای انجام هر وظیفه تخصیص داده خواهد شد؟

1. هر وظیفه در چه وقت انجام خواهد شد؟

به عبارت دیگر، وظیفه اصلی مسائل زمانبندی به تصمیم‌گیری در مورد تخصیص منابع و توالی عملیات منحصر می‌شود. نوشتارهای زمانبندی مملو از مدل‌های ریاضی برای پاسخگویی به این دو سوال تصمیم‌گیری است[۳۳].
به طور سنتی مسائل زمانبندی به صورت مسائل بهینه‌سازی محدودیت‌دار به ویژه مسائل مربوط به تخصیص منابع است و در این حالت عملیات مورد بررسی قرار گرفته است. در برخی موارد مسأله زمانبندی تنها مربوط به تخصیص منابع است و در این حالات مدل‌های برنامه‌ریزی ریاضی معمولاً می‌تواند برای تعیین تصمیمات در زمینه تخصیص منابع بهینه مورد استفاده قرار گیرد. از طرف دیگر مسائلی که صرفاً مقوله توالی عملیات را در نظر دارد نیز به حوزه زمانبندی مربوط می شود.
عناصر مهم مدلهای زمانبندی کارها و منابعاند. در نوشتارهای مربوط به زمانبندی، منابع نوعاً بر حسب قابلیتهای کمی وکیفی خود مشخص میشوند، به طوری که هر مدل نشان دهنده نوع و میزان هر منبع است. هر کار مشخص بر حسب اطلاعاتی از قبیل منبع مورد احتیاج، مدت انجام آن کار، زمانی که انجام آن را می توان شروع کرد وزمان تحویل آن توصیف می شود. به علاوه مجموعه ای از کارها را بعضاً می توان برحسب محدودیتهای تکنولوژیکی (روابط تقدمی) که در مورد عناصر متشکله آن صدق میکند بیان کرد.
نظریه زمانبندی همچنین شامل شیوه‌های متنوع و مختلفی است که در حل مسائل زمانبندی مفید واقع می‌شود. در واقع حوزه زمانبندی به صورت نقطه کانونی ایجاد، به کارگیری و ارزیابی روش‌های ترکیبی، شیوه‌های شبیه‌سازی، روش‌های شبکه‌ای و رویکردهای ابتکاری حل مسائل در آمده است. انتخاب شیوه مناسب به پیچیدگی مسأله طبیعت مدل و انتخاب معیار کارایی و عوامل دیگر بستگی دارد. در خیلی از حالات بهتر است چند شیوه به عنوان گزینه‌های مختلف برخورد به مسأله در نظر گرفته شود[۳۳].
در عمل، زمانبندی‌ها با استفاده از الگوریتم زمانبندی با قوانین بر پایه دانش ایجاد می‌شوند. الگوریتم‌های زمانبندی، زمانبندی‌هایی را توسعه می‌دهد که یک معیار اندازه‌گیری مانند حداقل کردن انحراف از موعد تحویل، حداقل جریمه دیرکرد یا حداقل حداکثر دیرکرد و همچنین کل مدت زمان ساخت[۴۱] را بهینه می‌کند. امروزه به کارگیری الگوریتم‌های ابتکاری و فراابتکاری برای حل مسائل توالی و زمانبندی و به دست آوردن حل‌های بهینه و یا نزدیک به بهینه بسیار متداول شده است[۳۳].

۲-۴-۱- مدل‌های زمانبندی [۶۴]

در اصطلاح برنامه‌ریزی تولید، مدل‌های زمانبندی می‌تواند به دسته‌های زیر تقسیم بندی شود:

یری می‌شود و مشکل عدم وجود فضای کافی حل می‌شود.
روش‌های زمانبندی ابزاری هستند که اجازه می‌دهند تولید به طور مؤثر انجام شود.کارایی زمانبندی می‌تواند به وسیله شاخص‌های مختلفی ارزیابی شود. دو مورد از متداولترین این شاخص‌ها حداقل کردن زمان مورد نیاز برای تکمیل کارها و حداقل کردن جریمه برای کارهایی که زودتر و یا دیرتر از موعد تحویل تکمیل می‌شوند، است.
در اصطلاح شناسی زمانبندی، توالی، زمانبندی و سیاست زمانبندی به صورت مجزا تعریف می‌شود. توالی معمولا در ارتباط با تغییر کامل مجموعه کارها یا ترتیبی که کارها باید روی یک ماشین معین پردازش شوند، می‌باشد. زمانبندی همانگونه که قبلا اشاره شد، معمولا به تخصیص کارها در بین یک مجموعه پیچیده از ماشین‌ها بر می‌گردد که می‌تواند اجازه بریدگی کارها توسط کارهای دیگر که در زمان دیرتر برسند، بدهد. مفهوم سیاست زمانبندی برای هر حالتی که سیستم می‌تواند داشته باشد برنامه زمانبندی مقرر می‌کند. در مدل‌های قطعی، معمولا تنها توالی‌ها و زمانبندی‌ها دارای اهمیت می‌باشد.

۲-۵- مروری بر مسائل تولید سلولی با رویکردهای تشکیل سلول، چیدمان سلول و زمانبندی گروهی

برای طراحی موفق یک سیستم تولید سلولی باید سه فاکتور اساسی تشکیل سلول، چیدمان سلول و مدیریت (زمانبندی) سلول در نظر گرفته شوند[۱]. اکثر مطالعات صورت گرفته در زمینه طراحی سیستمهای تولید سلولی مربوط به موضوع تشکیل سلول میباشد چرا که مهمترین مساله هنگام طراحی این سیستم است. این تحقیقات را میتوان براساس دو گروه اصلی از دادههای تولیدی مورد استفاده به دو دسته تقسیمبندی نمود [۳۴]: گروه اول روشهایی هستند که از ماتریس قطعه-ماشین به عنوان تنها داده ورودی استفاده میکنند و گروه دوم روشهایی هستند که از دیگر اطلاعات ساخت همچون حجم تولید، زمان راهاندازی و پردازش، توالی عملیات، قابلیتهای ماشین، مسیرهای فرآیندی جایگزین، قابلیت اطمینان ماشین و غیره بهره میگیرند. بسیاری از رویکردهای حل ابتکاری و دقیق که برای حل مسائل تشکیل سلول توسعه یافتهاند شامل مواردی چون رویکرد تحلیل دستهای[۴۳]، رویکرد تقسیمبندی گراف[۴۴]، الگوریتمهای انشعاب و تحدید[۴۵] و الگوریتمهای فراابتکاری [۴۶] میباشند. مرور دقیق رویکردهای حل مساله تشکیل سلول در مقالات [۳۵-۳۸] در دسترس هستند.
طراحی چیدمان سلولی هدف برخی از مطالعات طراحی سیستمهای تولید سلولی است. اکثر تحقیقات فرض کردهاند که سلول تشکیل شده است و سپس به حل مساله چیدمان درون سلولی[۴۷] و بین سلولی[۴۸] پرداختهاند. کاندراسخاران و راجاگوپالان[۴۹] [۳۹] یک الگوریتم سنجش و مقیاسگذاری چند بعدی برای طراحی چیدمان بین سلولی با در نظر گرفتن سلول از پیش تشکیل شده، پیشنهاد کرده است. روش CLASS [۵۰]، یک روش مبتنی بر شبیهسازی تبرید است که توسط جاجودیا[۵۱] [۴۰] ارائه گردید بطوریکه چیدمان بین سلولی و درون سلولی را به طور همزمان مشخص مینماید. سالوم[۵۲] [۴۱] یک رویکرد دو مرحلهای را با استفاده از شبیهسازی برای حل مساله چیدمان سیستم تولید سلولی ارائه نمود. اوربان[۵۳] [۴۲] یک مدل یکپارچه برای فرمولبندی مساله چیدمان ماشینها و همچنین مساله تخصیص محصولات پیشنهاد کرده است بطوریکه در آن پیکربندی سیستم تولیدی توسط الزامات ساخت دیکته میشوند.
برخی محققان دو موضوع تشکیل سلول و چیدمان سلول را تواما مورد مطالعه قرار دادهاند. آروینده و ایرانی[۵۴] [۴۳] اثرات چهار مساله (تشکیل سلول، تکثیر ماشین[۵۵]، چیدمان درون سلولی و بین سلولی) را در طراحی سیستم تولید سلولی و هچنین اثرشان بر یکدیگر را مورد تحقیق و بررسی قرار دادهاند و برای حل این زیرمسالهها به طور همزمان یک رویکرد حل تکرار شونده پیشنهاد دادهاند. آکتورک[۵۶] [۴۴] یک مدل ریاضی برای تعیین چیدمان درون سلولی و تشکیل سلول با هدف حداقل کردن هزینه جابجایی مواد را ارائه کرده است. او همچنین مقادیری به عنوان مقادیر عدم تشابه بین قطعهها بر اساس توالی عملیاتها پیشنهاد کرده است. چیانگ و لی[۵۷] [۴۵] دو مساله تشکیل سلول و چیدمان بین سلولی را با لحاظ چیدمان خطی برای سلولهای ماشینی با هدف حداقل کردن هزینه جریان بین سلولی مورد تحقیق و بررسی قرار دادهاند. آنها برای حل این مساله از رویکرد ترکیبی شبیهساری تبرید با الگوریتم برنامهریزی پویا بهره گرفتهاند. مهدوی و همکارانش[۵۸] [۴۶] یک الگوریتم ابتکاری مبتنی بر ماتریس جریان برای تشکیل سلولها و چیدمان ماشینهای داخل هر یک از سلولها به طور همزمان پیشنهاد دادهاند. آهی و همکارانش[۵۹] [۴۷] یک رویکرد حل دو مرحلهای را برای حل همزمان مسائل تشکیل سلول و چیدمان سلول توسعه دادند که در مرحله نخست، یک حل اولیه با استفاده از تکنیکی برای معیار رتبهبندی توسط حل ایدهآل بدست میآید و سپس در مرحله دوم، این حل بهبود مییابد. وو و همکارانش[۶۰] [۴۸] و [۱] یک مدل ریاضی را پیشنهاد داده و یک الگوریتم ژنتیک برای حل مساله تشکیل سلول و چیدمان سلول به طور همزمان توسعه دادهاند.
از طرف دیگر، تصمیمگیری در مورد زمانبندی سلولی در سیستمهای تولید سلولی توسط برخی دیگر از محققان مورد مطالعه قرار گرفته است. سریدهار و راجندران [۶۱] [۴۹] یک الگوریتم ترکیبی شبیهسازی تبرید به منظور حل مساله زمانبندی در سیستمهای تولید سلولی ارائه کرده است. در این تحقیق فرض بر آن است که سلولها از قبل تشکیل شدهاند و الگوریتم پیشنهادی سعی بر آن دارد که یک توالی از عملیاتها را با هدف حداقل کردن مجموع زمانهای تکمیل همه کارها در یک سلول، بدست آورد. اتمانی و همکاران[۶۲] [۵۰] یک مدل برنامهریزی ریاضی معرفی نمودهاند که دو مساله تشکیل سلول و تخصیص عملیاتها را همزمان حل میکند. هدف مدل آنها حداقل کردن مجموع هزینههای حمل و نقل، فیکسچرها و عملیاتها میباشد. آنها همچنین چندین برنامه فرآیند برای هر قطعه در نظر گرفتهاند بطوریکه هر عملیات از یک نوع قطعه میتواند بر روی بیش از یک ماشین پردازش شود. الگوریتم SVS یک الگوریتم ابتکاری دو مرحلهای است که توسط سلیمانپور و همکارانش[۵۱] برای حداقل کردن زمان تکمیل آخرین کار در سیستم تولید سلولی پیشنهاد شده است. مراحل اول و دوم (با نامهای زمانبندی درون سلولی و زمانبندی بین سلول) به ترتیب توالی عملیاتها و توالی سلولها را تعیین مینمایند. فرانکا و همکاران[۶۳] [۵۲] از الگوریتمهای ابتکاری برای حل مساله زمانبندی خانوادههای قطعات و کارهای درون هر یک از خانواده قطعهها در یک سلول تولیدی خط جریان با در نظر گرفتن زمانهای راهاندازی وابسته به توالی خانواده ا
ستفاده کرده است. ردی و نارندران[۶۴] [۵۳] یک سری روشهای ابتکاری برای زمانبندی کارها در یک خانواده قطعه از طریق شناسایی زیرخانوادهها پیشنهاد داده است. در این تحقیق هدف بهبود بهرهبرداری از ماشینها در یک سلول، کاهش میزان تاخیر و تعداد کارهایی که با تاخیر صورت میگیرند، است.
واضح است که اکثر مطالعاتی که در زمینه سیستمهای تولید سلولی صورت گرفتهاند به حل یکی از سه فاکتور تصمیمگیری (CF,CL و CS) پرداختهاند و برخی از آنها این دو یا سه موضوع را به طور متوالی و پی در پی[۶۵] در نظر گرفتهاند. این رویکردها راه حلهایی را ارائه میدهند که ممکن است تنها برای یکی از این سه مساله کارآمد باشند، اما راه حلهای رضایتبخشی برای کل مجموعه سیستم به دنبال نداشته باشند. این رخداد به دلیل تاثیر این سه زیر مساله بر روی یکدیگر در هنگام طراحی سیستم تولید سلولی میباشد. حل یکی از این زیر مسالهها بدون در نظر گرفتن ارتباط بین آنها تضمین نمیکند که راه حل ارائه شده، بقیه زیر مسالهها را نیز ارضاء نماید. اهمیت یکپارچگی تشکیل سلول و چیدمان سلولی توسط لوجندران [۶۶] [۵۴] و آورینده و ایرانی مورد تاکید قرار گرفته است. وو و همکارانش [۱] نشان دادهاند که تشکیل سلول و زمانبندی سلول با هم در ارتباط هستند و راه حلی که برای مساله زمانبندی بدست آوردند به طور مستقیم تحت تاثیر مساله تشکیل سلول است. تنها مدل ریاضی که تشکیل سلول را با چیدمان بین سلولی و درون سلولی ادغام نموده است توسط وو و همکارانش [۴۸] و [۵۵] ارائه شده است اما در مدل و راه حل آنها چیدمان سلولی به روش درستی انجام نشده و سلولها ممکن است با یکدیگر همپوشانی داشته باشند. اگر سلولها با یکدیگر همپوشانی داشته باشند همانند حالتی که در طراحی سلولهای مجازی رخ میدهد، در اینصورت دیگر چیدمان بین سلولی معنایی نخواهد داشت. این مشکل همپوشانی سلولها توسط آرکات و همکارانش [۲] با تعیین محل دقیق ماشینها در درون سلولهای مجزا از هم و تحت چیدمان مستطیلی رفع شده است. آنها مدل یکپارچه خود را با استفاده از الگوریتم ژنتیک حل کردهاند. آرکات و همکارانش [۵۶] با حفظ شرایط تحقیق پیشین خود در این زمینه با افزودن یک هدف دیگر به مدل، یک مدل چند هدفه را معرفی نمودند که به طور همزمان به تشکیل سلول، چیدمان سلول و زمانبندی عملیاتها با هدف حداقل کردن هزینه کل جابجایی قطعهها و زمان تکمیل آخرین کار میپردازد. برای حل این مساله یک الگوریتم ژنتیک چند هدفه[۶۷] توسعه دادهاند. در جدول ۲-۴ خلاصهای از تحقیقات اخیری که حداقل دو زیر مساله از سه زیر مساله تصمیمگیری CF, CL و CS را در سیستمهای تولید سلولی مورد مطالعه قرار دادهاند ارائه شده است.
اگرچه آرکات [۲] در مدل خود به تعیین محل دقیق ماشینها و عدم هم پوشانی سلولها پرداخته است اما سلولها از چیدمان مناسبی برخوردار نسیتند و به چیدمان مناسب سلولها به طور مجزا و مستقل در کنار یکدیگر توجه نشده است. ما در مطالعه پیش رو علاوه بر حفظ مزایای مدلهای ارائه شده قبلی در این زمینه به چیدمان مناسب سلولها به طور مستقل پرداخته و نحوه قرار گیری بهینه سلولها در کنار یکدیگر را تعیین میکنیم. در مطالعات گذشته در بخش چیدمان سلولی به سلولها به عنوان یک واحد مجزا و مسقل توجه نشده و فاصله بین سلولها در محاسبات و فرضیات تنها با یک تغییر مقیاس به طور کلی در نظر گرفته شده است. در حالیکه در این تحقیق در چیدمان بین سلولی
جدول ۲‑۴٫ خلاصهای از مرور ادبیات
فاصله سلولها به طور جداگانه بیان شده و در تعیین چیدمان بهینه سلولها در کنار هم مورد استفاده قرار گرفته است.
هراگو و کوسیاک[۶۸] [۵۷] نشان دادهاند که چیدمان ماشینها و سلولها[۶۹] با توجه به نوع تجهیزات جابجایی موادی که مورد استفاده قرار میگیرد، تعیین میگردند. از میان انواع مختلف این چیدمانها، چیدمانهای خطی تک ردیفی و دو ردیفی[۷۰] بسیار محبوب هستند (شکل ۲-۴). استفاده مکرر از این چیدمانها به دلیل انعطافپذیری آنها در هنگام کار با تجهیزات مختلف جابجایی مواد میباشد.
شکل ۲‑۴٫ چیدمان سلولی پایه الف) چیدمان خطی تک ردیفی ب) چیدمان خطی دو ردیفی
از آنجاییکه چانگ[۷۱] و همکارانش [۴] نشان دادند که عملکرد چیدمان خطی دو ردیفی بهتر از چیدمان خطی تک ردیفی به جهت کاهش مجموع فاصله جابجایی بین سلولی[۷۲] است ما در تعیین چیدمان بهینه سلولها از این نوع بهره گرفتهایم. از طرف دیگر، در این مطالعه در بخش تشکیل سلول به تخصیص قطعه به سلول توجه ویژهای شده است. در سه مقاله اخیر [۱]، [۲] و [۵۶] تنها مقاله [۱] به تشکیل خانواده قطعهها پرداخته است و در این فرآیند به شرط انجام حداقل یک عملیات از مجموعه عملیاتهای یک قطعه توسط یکی از ماشینهای موجود در هر سلول برای اختصاص آن قطعه به سلول کفایت کرده است که این فاکتور باعث ایجاد جابجاییهایی در مساله خواهد که در مدل در نظر گرفته نشده است و مدل را با مشکل مواجه میسازد. در مدل ارائه شده در این تحقیق برای رفع این مشکل نیز راه حلهایی پیشنهاد و در مدل مورد استفاده قرار گرفته است. ما در مطالعه پیش رو به چیدمان بهینه سلولها در کنار یکدیگر و تشکیل خانواده قطعهها به طور مناسب میپردازیم.

۳-۳-۳- پارامترهای خروجی

Tjoo′ : زمان جابجایی قطعه j ام بین دو عملیات متوالی o و o′ از مسیر پردازش آن قطعه (o′=o+1)
gjo : زمان تکمیل عملیات o قطعه j ام.
g(j) : زمان تمکیل آخرین عملیات قطعه j ام (زمان تکمیل کار قطعه j ام)

۳-۳-۴- متغیرهای تصمیمگیری

Yjk : ۱ ، اگر قطعه j به سلول k اختصاص یابد. ۰ ، در غیر اینصورت.
Wik : ۱ ، اگر ماشین i به سلول k اختصاص یابد. ۰ ، در غیر اینصورت.
Xikp : ۱ ، اگر ماشین i در سلول k در موقعیت p ام قرار بگیرد. ۰ ، در غیر اینصورت.
Zjoj′o′ : ۱ ، اگر عملیات o قطعه j ام مقدم بر عملیات o′ قطعه j′ ام باشد. ۰ ، در غیر اینصورت.
{ ∀(o,o′) ϵ Ni , ∀i , j≠j′ }

۳-۴- مدل ریاضی

S.T

۴-۴- تشریح مدل

در (۱) تابع هدف مدل ارائه شده است که در آن ما به دنبال حداقل کردن زمان تکمیل همه کارها هستیم.
محدودیتهای شماره (۲) و (۳) به ترتیب تضمین میکنند که هر قطعه تنها به یک سلول میتواند اختصاص یابد و اینکه به هر سلول میبایست حداقل یک قطعه تخصیص پیدا کند.
محدویت شماره (۴) باعث میشود قطعه به سلولی اختصاص یابد که اولین عملیات آن توسط یکی از ماشینهای اختصاص یافته با آن سلول پردازش شود.
محدودیت شماره (۵) بیان میکند که هر ماشین میبایست فقط به یک سلول نسبت داده شود.
محدودیتهای شماره (۶) و (۷) مانع از این میشود که تعداد ماشینهای موجود در هر سلول از محدوده حداقل و حداکثر تعداد ماشین مجاز در هر سلول خارج شود.
محدودیت شماره (۸) هر ماشین را در یکی از موقعیتهای ممکن در سلول اختصاص یافته به آن ماشین قرار میدهد. به عبارت دیگر استقرار هر ماشین تنها در موقعیتهایی مجاز است که مربوطه به سلول انتخابی برای حضور آن ماشین هستند و نه سلولهای دیگر.
محدودیت شماره (۹) از اختصاص بیش از یک ماشین به هر موقعیت از هر سلول ممانعت مینماید.
محدودیت (۱۰) اشاره دارد که هر ماشین باید تنها در یکی از موقعیتهای یک سلول قرار گیرد.
محدودیت شماره (۱۱) زمان جابجایی بین سلولی و درون سلولی را محاسبه میکند.
محدودیت شماره (۱۲) تاکید میکند که عملیاتهای هر قطعه مطابق توالی عملیاتهای مورد نیاز انجام میگیرند.
محدودیتهای (۱۳) و (۱۴) تضمین میکند که هر ماشین در یک لحظه نمیتواند بیش از یک قطعه را پردازش کند.
محدودیت (۱۵) تضمین میکند که زمان تکمیل عملیات o قطعه j بزرگتر مساوی زمان پردازش این عملیات است.
محدودیت (۱۶) زمان تکمیل کار قطعه j را محاسبه میکندو در نهایت محدودیت (۱۷) مشخص میکند که متغیرهای تصمیم ما باینری هستند.

۳-۲- روش حل با استفاده از الگوریتم ژنتیک

۳-۲-۱- آشنایی با الگوریتم ژنتیک

۳-۲-۱-۱- مقدمه

الگوریتم ژنتیک یک روش آماری برای بهینه سازی و جستجو است. الگوریتم ژنتیک جزئی از محاسبات تکاملی است که خود جزئی از هوش مصنوعی میباشد. ویژگیهای خاص این الگوریتم باعث میشود که نتوانیم آن را یک جستجوگر تصادفی ساده قلمداد کنیم. در واقع ایده اولیه این روش از نظریه تکاملی داروین (۱۸۵۹) الهام گرفته شده است و کارکرد آن بر اساس ژنتیک طبیعی استوار میباشد. نظریه تکاملی داروین بدین صورت است که آن دسته از صفات طبیعی که با قوانین طبیعی سازگاری بیشتری دارند، شانس بقاء بیشتری دارند.
ایده محاسبات تکاملی اولین بار در سال ١٩۶٠ توسط رچنبرگ[۷۴] که در زمینه استراتژیهای تکاملی تحقیق میکرد بوجود آمد که نظریه او بعدها توسط دیگر محققان توسعه داده شد. اصول اولیه الگوریتم ژنتیک توسط هلند[۷۵] و همکارانش در دانشگاه میشیگان در سال ١٩۶٢ ارائه شد. آنان در تحقیقات خود به فرایند سازگاری در سیستم های طبیعی توجه نمودند و برای مدل سازی آن در سیستم های مصنوعی که باید دارای توانایی های اصلی سیستم های طبیعی باشند، تلاش نمودند. نتیجه این تلاشها، پیدایش الگوریتم ژنتیک بود. سپس در سال ١٩٧۵، مبانی ریاضی آن در کتابی توسط هلند با نام «تطابق در سیستمهای طبیعی و مصنوعی»[۷۶] منتشر شد. ودر سال ۱۹۸۹ کاربرد آن با انتشار کتابی توسط گلدبرگ[۷۷] تسریع یافت. در سال ١٩٩٢، جان کوزا[۷۸] الگوریتم ژنتیک را به منظور انجام وظایف خاصی در برنامههایش بکار برد. او این روش را برنامه ریزی تکاملی[۷۹] نامید. در برنامه ریزی تکاملی، هدف پیدا کردن الگوریتمی است که بتواند جواب هر صورت مسالهای را پیدا کند. در این روش باید برای الگوریتمها مطلوبیت تعریف کرد تا فهمیده شود که کدام الگوریتم بهتر است.
خاصیت مهم الگوریتم ژنتیک، مقاوم بودن آن است، بطوریکه در آن یک تعادل انعطافپذیر بین کارایی و خصوصیات لازم برای بقا در محیطها و شرایط گوناگون وجود دارد. بطور کلی هر چه سیستم مصنوعی از نظر مقاومت در درجه بالاتری باشد، هزینه طراحی مجدد آن کاهش یافته و حتی حذف میگردد. در واقع چنانچه میزان سازگاری سیستمی افزایش یابد، آن سیستم قادر خواهد بود که به مدت طولانیتر و به نحو مطلوبتری به کار بپردازد. در سیستمهای بیولوژیک میزان انعطاف پذیری، مقاومت و کارایی به شکل شگفتانگیزی زیاد است. سازگاری، بقا، خودترمیمی، هدایت و تولید مثل از دیگر ویژگیهای خاص سیستمهای طبیعی و بیولوژیک می باشد که مهندسان در صددند تا در سیستمهای مصنوعی از آنها تقلید کنند. اما بطور کلی جایی که کارکرد مقاوم مورد نیاز باشد، طبیعت بهتر عمل خواهد کرد.
از الگوریتم ژنتیک در کاربردهای مختلفی مثل بهینهسازی توابع، شناسایی سیستمها و پردازش تصویر استفاده شده است. در زیر برخی از موارد استفاده از الگوریتم ژنتیک در علوم مختلف نشان داده شده است.
بیولوژی: شبیه سازی تکامل یک جمعیت از ارگانیسم های تک سلولی
علوم کامپیوتر: جستجو برای تکامل تابع ارزشیابی
مهندسی: شناسایی سیستمهای دینامیکی

• کدینگ باینری

این نوع کدینگ، متداولترین نوع کدینگ می باشد. در این روش کدگذاری، هر کروموزوم یک رشته از بیتهای شامل ٠ و ١ می باشد. کدینگ باینری می تواند حالت های زیادی را پوشش دهد، حتی در مواردی که تعداد آلل ها کم باشد.
 
شکل ۳‑۲٫ کدینگ باینری
از طرف دیگر این نوع کدینگ برای خیلی از مسائل حالت طبیعی ندارد و اغلب اوقات لازم است که بعد از تقاطع و جهش اصلاحاتی صورت بگیرد.

2. کدینگ جهشی

این نوع کدینگ میتواند در مسائل ترتیبی نظیر مساله فروشنده دوره گرد یا مساله ترتیب کارها بکار رود. در کدینگ جهشی، هر کروموزوم یک رشته از اعداد میباشد. شکل زیر نمونه ای از این نوع کدینگ را نشان میدهد.
شکل ۳‑۳٫ کدینگ جهشی
کدینگ جهشی تنها برای مسائل ترتیبی مفید است. حتی برای همین مسائل نیز گاهی اوقات باید تقاطعها و جهشهای اصلاحی به منظور ایجاد کروموزومهای سازگار و مناسب انجام شود.

3. کدینگ ارزشی

این نوع کدینگ درمسائلی که در آنها مقادیر پیچیده نظیر اعداد حقیقی بکار میروند استفاده میشود. استفاده از کدینگ باینری برای چنین مسائلی بسیار سخت میباشد. در کدینگ ارزشی هر ژن یک کروموزوم ارزش خاصی دارد. این پارامتر با ارزش میتواند عدد، حرف یا کلمه باشد. دراین نوع کدینگ نیاز به توسعه عملگرهای جابجایی و جهش جدیدی برای مسائل خاص میباشد.
شکل ۳‑۴٫ کدینگ ارزشی

4. کدینگ درختی

کدینگ درختی در برنامه های تکاملی به منظور برنامه ریزی تکاملی بکار میرود. در کدینگ درختی هرکروموزوم یک درخت از اشیائی نظیر توابع یا دستورها در زبان برنامه نویسی میباشد. شکل زیر دو نمونه از این کروموزومها را نشان میدهد. این نوع کدینگ برای برنامههای تکاملی بسیار عالی است.
شکل ۳‑۶٫ کدینگ درختی
نکته ای که در انتهای این قسمت باید به آن توجه کرد این است که در الگوریتم های ژنتیکی کدینگ یک رابطه بین فضای کدینگ و فضای جوابها می باشد بطوریکه الگوریتم ژنتیک عملیات تکاملی را بطور متناوب در این دو فضا انجام می دهد (شکل ۳-۷). انتخاب طبیعی نیز به عنوان یک رابطه بین کروموزومها و عملکرد جوابهای کدشده آنها می باشد.
شکل ۳‑۷٫ فضای کدینگ وفضای جواب

۳-۲-۱-۵-۵- کروموزوم

رشته یا دنبالهای از بیتها که به عنوان شکل کد شده یک جواب ممکن (مناسب یا نامناسب) از مساله مورد نظر میباشد را کروموزوم میگویند. در حقیقت بیتهای یک کروموزوم، نقش ژنها را در طبیعت بازی میکنند.

۳-۲-۱-۵-۶- جمعیت[۹۰]

مجموعهای از کروموزومها را جمعیت گویند. یکی از ویژگیهای ژنتیک این است که به جای تمرکز بر روی یک نقطه از فضای جستجو یا یک کروموزوم، بر روی جمعیتی از کروموزومها کار میکند. بدین ترتیب در هر مرحله، الگوریتم دارای جمعیتی از کروموزومها بوده که خواص مورد نظر را بیشتر از جمعیت مرحله قبل دارا میباشد. هر جمعیت یا یک نسل از کروموزومها، دارای یک اندازه میباشد که به اندازه جمعیت[۹۱] معروف است. اندازه جمعیت معرف تعداد کروموزومهای موجود در جمعیت یا یک نسل است.

۳-۲-۱-۵-۷- مقدار برازندگی[۹۲]

مناسب بودن یا نبودن جواب، با معیاری که از تابع هدف بدست میآید، سنجیده میشود. هر چه که یک جواب مناسبتر باشد، مقدار برازندگی بزرگتری دارد. برای آنکه شانس بقای چنین جوابی بیشتر شود، احتمال بقای آن، متناسب با مقدار برازندگی آن در نظر گرفته میشود. بنابراین کروموزمی که برازنده ترین است با احتمال بیشتری در تولید فرزندان شرکت میکند و دنبالههای بیشتری از آن به وجود میآید. به عنوان مثال چنانچه هدف بیشینه کردن یک تابع باشد، مقدار برازندگی، یک تابع صعودی از تابع هدف در نظر گرفته میشود و اگر هدف یافتن مقدار کمینه یک تابع باشد، عدد برازندگی، یک تابع نزولی از آن قرار داده میشود. معمولاً در مواردی که امکان دارد، تابع برازندگی را در فاصله [۱و۰] نرمالیزه میکنند.

۳-۲-۱-۵-۸- عملگر تقاطع

این عملگر بر روی یک جفت از کروموزوم ها عمل می کند و میتواند به صورت تک نقطهای، چند نقطهای و یکنواخت باشد. عملگر تقاطعی تک نقطهای، دو کروموزوم را به طور تصادفی از یک نقطه شکسته و بخش های شکسته دو کروموزوم را جابجا می کند. بدین ترتیب دو کروموزوم جدید بدست می آید. به کروموزومهای اولیه، کروموزومهای”والد“و به کروموزوم های حاصل شده از عمل جابجایی و عمل جهش، کروموزوم”فرزند“میگویند.
 
شکل ۳‑۸٫ مثالی از عمل جابجایی تک نقطه ای
عملگر تقاطع با احتمال Pc بر روی کروموزوم های والد عمل میکند. بدین معنی که با احتمال Pcعمل تقاطع انجام میگیرد. اگر هیچ تقاطعی صورت نگیرد، فرزندان دقیقًا مشابه والدین خواهند بود (البته این مطلب بدین معنی نیست که نسل جدید همان نسل قبلی است). در صورتی که عمل تقاطع صورت بگیرد، فرزندان از قسمتهای مختلف کروموزومهای والد ساخته میشوند. اگر احتمال تقاطع ١ باشد، تمامی فرزندان از طریق عمل تقاطعی ایجاد میشوند. عملیات تقاطع با این هدف انجام میشود که کروموزومهای جدید در بردارنده قسمتهای مناسب و خوب کروموزومهای قبلی خواهند بود و شاید این کروموزومهای جدید عملکرد بهتری داشته باشند. اما بهتر است همیشه بهترین کروموزومهای نسل قبلی بدون هیچ تغییری به نسل جدید منتقل شوند.
تفاوت عملگر چند نقطهای در مقایسه با عملگر تقاطع تک نقطه ای دراین است که نقطه شکست دو کروموزوم، بیش از یکی است و تقاطع در بخشهای شکسته شده دو کروموزوم به صورت یک در میان انجام میگیرد. شکل ۳-۹ مثالی از عمل تقاطع دو نقطه ای را نشان میدهند.
شکل ۳‑۹٫ تقاطعی دو نقطه ای