1-6- تعریف مسأله زمانبندی مربوط به تحقیق…………………………………………………….3

1-7- مفروضات مسئله……………………………………………………………………………………….5

1-8- ضرورت انجام تحقیق………………………………………………………………………………..6

1-9- جمع بندی……………………………………………………………………………………………….7

فصل 2- مروری بر ادبیات موضوع…………………………………………………………………45-8

2-1- مقدمه……………………………………………………………………………………………..24

2-2- مروری بر رویکرد و اصول سیستم تولیدی JIT…………………………………………..

2-3- توالی ماشین های موازی با معیار دیر کرد…………………………………………………28

2-3-1- حداقل کل دیر کرد…………………………………………………………………………28

2-3-2- حداقل کل دیر کرد وزنی…………………………………………………………………..32

2-4- توالی ماشین های موازی با معیارهای زود کرد و دیر کرد…………………………34

2-4-1- مسائل با تمرکز بر زمان آماده سازی بین کارها……………………………………35

2-4-2- مسائل با تمرکز بر موعد تحویل یکسان برای کارها……………………………….39

2-4-2-1- موعد تحویل معلوم……………………………………………………………..39

2-4-2-2- موعد تحویل نامعلوم……………………………………………………………….44

2-5 دسترسی محدود به ماشینها ……………………………………………………………45

2-6 جمع بندی ………………………………………………………………………………….45

فصل 3- ارائه مدل ریاضی………………………………………………………………58-46

3-1- مقدمه……………………………………………………………………………………..47

3-2-تعریف مسئله…………………………………………………………………………….47

3-3- فرضیات مسئله………………………………………………………………………..48

3-4- مدل ریاضی پیشنهادی……………………………………………………………..49

3-4-1- پارامترهای ورودی…………………………………………………………………49

3-4-2- نمادها، تعاریف، پارامترها و متغیر های تصمیم…………………………..50

3-4-3- مدل ریاضی……………………………………………………………………51

3-5 –اعتبار سنجی مدل………………………………………………………………53

3-6 –تئوری پیچیدگی و پیچیدگی مساله مورد نظر………………………….56

3-6- جمعﺑندی…………………………………………………………………………58

فصل 4- الگوریتم پیشنهادی نتایج محاسباتی………………………………110-59

4-1 مقدمه……………………………………………………………………………….60

4-2 الگوریتم ژنتیک …………………………………………………………………….62

4-2-1 شمای کلی الگوریتم ژنتیک…………………………………………………64

4-3) اجزای الگوریتم ژنتیک………………………………………………………66

4-3-1) کروموزوم……………………………………………………………………66

4-3-2) جمعیت……………………………………………………………………..66

4-3-3) مقدار برازندگی…………………………………………………………..67

6-3-4) کدگذاری…………………………………………………………………..67

4-3-5) انتخاب…………………………………………………………………….68

4-3-6) عملگر تقاطعی………………………………………………………………76

4-3-7) جهش………………………………………………………………………….82

4-3-8) جابه‌جایی…………………………………………………………………….83

4-3-8) قاعده توقف……………………………………………………………….83

4-3 الگوریتم حرکت جمعی پرندگان ………………………………………..84

4-4 حرکت دسته جمعی ذرات ……………………………………………….86

4-5 مفاهیم پایه الگوریتم……………………………………………………..88

4-6 رابطه بروز رسانی سرعت………………………………………………..88

4-7 رابطه بروز رسانی موقعیت…………………………………………………92

4-8 گامهای الگوریتم……………………………………………………………93

4-9 شبه کد الگوریتم……………………………………………………………..93

4-10)طراحی الگوریتم پیشنهادی…………………………………………..94

4-10) تنطیمات پارامترها و شرایط اجرای الگوریتم ها……………….99

4‐11) ساختار مسائل…………………………………………………………..99

4‐12)مسائل با ابعاد کوچک و متوسط…………………………………..100

4-13) نتایج آزمایشات……………………………………………………..100

4-14 مسائل با ابعاد بزرگ…………………………………………………….107

4-15 جمع بندی………………………………………………………………109

فصل5- نتیجه گیری و پیشنهادات آتی…………………………….113-110

5-1) نتیجه گیری……………………………………………………………….111

5-2) پیشنهادات آتی ………………………………………………………..113

منابع……………………………………………………………………………115

چکیده:

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

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

فصل اول: کلیات و بیان مسأله

1-1- مقدمه

در جهان رقابتی حاضر، توالی و زمانبندی موثر ضرورتی برای بقا در فضای بازار است. زمانبندی ابزاری است که استفاده از منابع در دسترس را بهینه می کند.زمان همواره یک محدودیت اساسی بوده، بنابراین زمانبندی فعالیتها به منظور حداقل کردن این منبع محدود یک الزام است. زمانبندی و توالی عملیات یکی از مهم ترین مسائل برنامه ریزی تولید بوده و کاربردهای زیادی در واحدهای تولیدی و غیرتولیدی دارد.

عمل زمانبندی در یک سازمان از مدل ها و روش های ریاضی و یا روش های ابتکاری برای تخصیص منابع محدود به کارهای در حال جریان استفاده می کند. اهمیت توالی ماشین های موازی، با هدف متمرکز بر دیرکرد از آن جهت مورد توجه است که در محیط کسب و کار حاضر، رقابت شرکت های تولیدی از طریق قابلیت آنها برای پاسخگویی سریع به تغییرات سریع در زمینه تجارتی و تولید محصولات با کیفیت بالاتر و هزینه های کمتر تعیین می شود. شرکت های تولیدی در تلاش هستند تا این قابلیت ها را از طریق اتوماسیون و مفاهیم خلاق مانند تولید به موقع[1](JIT)، پاسخگوی سریع[2](QR)، تکنولوژی گروهی[3](GT)و مدیریت کیفیت جامع[4](TQM)بدست آورند[3].

این مفاهیم ( برای مثال JIT و GT ) به بسیاری از شرکت ها در بدست آوردن سود اقتصادی کمک کرده است. در سیسستم های JIT کار نباید نه زودتر و نه دیرتر تکمیل شود، که به مسائل زمانبندی با هزینه های زودکرد و دیرکرد و تخصیص موعدهای تحویل منجر می شود. در یک بازار رقابتی دیرکرد کارها با توجه به موعد تحویل آنها یک مقیاس عملکرد بسیار مهم برای محیط های تولید متنوع است.

مسائل با تعیین موعد تحویل در 25 سال گذشته بعلت روشهای جدید مدیریت مانند مفاهیمJITمورد توجه بسیار قرار گرفته است.چنگ که کمک زیادی به مسائل زمانبندی و تخصیص موعد تحویل کرد بیان می کند که تکمیل یک کار زودتر از موعد تحویل به معنی تحمیل هزینه های نگهداری موجودی غیر ضروری است ، در حالیکه تکمیل یک کار دیرتر از موعد تحویل منجر به جریمه های قراردادی و از دست دادن اعتبار مشتری می شود[4].

بطور جالب توجه هدف مسئله حداقل دیرکرد و زودکرد[5](ET) کاملا با سیاست کنترل تولید JITمطابقت دارد.مسئله ماشین های موازی از دو دیدگاه تئوری و عملی دارای اهمیت می باشند. از دیدگاه تئوری به اینخاطر که تعمیمی از حالت تک ماشینه می باشد و از دیدگاه عملی به این جهت که در دنیای واقعی بسیارمعمول است مورد توجه قرار گرفته شده است.

مسئله به کارگیری ماشین های موازی[6] از آنجا مورد توجه است که اگر زمانبندی روی یک ماشین منجر به هزینه زیادی شود ممکن است در نظر گرفتن ماشینهای بیشتر سبب کاهش هزینه شود. ضمن این که مقدار دیرکرد یا زودکرد نیز می تواند با افزایش تعداد ماشین ها کاهش یابد. در این شرایط هزینه به کارگیری ماشین یا نگهداری ماشین اضافه می شود که با حل مسئله بهینه سازی می توان تعیین کرد چه ماشین هایی

به کار گرفته شوند و کدام کارها با چه توالی روی این ماشین ها انجام شود.

در عمل، زمانبندی ها با استفاده از الگوریتم های زمانبندی یا قوانین بر پایه دانش ایجاد می شوند. الگوریتم های زمانبندی ، زمانبندی را توسعه می دهد که یک معیار اندازه گیری مانند حداقل کردن انحراف موعد تحویل، حداقل جریمه دیرکرد یا حداقل حداکثر دیرکرد را بهینه می کند.

در این فصل، ابتدا مروری بر انواع مسائل زمانبندی و تعریف بعضی مفاهیم اولیه زمانبندی پرداخته می شود، در ادامه به خصوصیات و مشخصات مسأله مورد بحث این تحقیق، پرداخته می شود. در پایان اهداف، ضرورت و متدولوژی تحقیق بیان شده است.

1-6- تعریف مسأله زمانبندی مربوط به تحقیق :

بیان مسأله:

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

در این تحقیق مسئله زمانبندی ماشینهای موازی نامرتبط با در نظر گرفتن محدودیت های زمان نصب وابسته به توالی پردازش کاره و زمان دسترسی کارها با هدف کمینه سازی زمانهای زودکرد و دیرکرد وزنی کل بررسی می شود.یک مدل برنامه ریزی عدد صحیح برای مسئله پیشنهاد می شود.همچنین یک روش فراابتکاری برای حل آن ارائه می گردد.

نظام تولید بهنگام[7] تفکر و نگرشی نوین در اداره سازمانهای صنعتی است که با اصل تکنیکها و روشهای برخاسته از آن، حذف کامل و جامع اتلاف و افزایش بهره وری در تمامی فعالیتها اعم از داخل و خارج سازمان تعقیب می گردد.

تعاریف بسیاری توسط کارشناسان برای تولید بهنگام ارائه شده است، در زیر به تعدادی از این تعاریف اشاره شده است.

JIT یعنی :

پافشاری بر کیفیت برتر انجام امور خرید و تولید و … دقیقا در زمان مقرر
بهنگام بودن نظام، مستلزم بهنگام بودن همه اجزای آن است
در کل JIT یعنی فقط به هنگام ” نه دیرتر نه زودتر”
در JIT هدف تولید بهنگام است، یعنی اگر مشتری و تولید کننده زمان تحویل کالا را در یک زمان معین توافق کنند، تولید کننده باید تولیدات خود را طوری برنامه ریزی کند که کالا را در حد امکان در زمان مناسب تولید و در زمان مقرر تعیین شده به دست مشتری برساند. اگر این دیرتر از زمان تحویل آماده شود، تولید کننده متحمل جریمه ای به عنوان تأخیر تولید خواهد شد که این جریمه امکان دارد به صورتهای مختلف نمود پیدا کند. همچنین اگر تولید کننده، کالا را زودتر از زمان تحویل، تولید کند، این کالا را باید تا زمان تحویل در انبار نگهداری کند لذا در این صورت نیز متحمل هزینه خواهد شد.

1-7- مفروضات مسئله :

1-زمان نصب وابسته به توالی هنگام تعویض کارها بر روی ماشینها وجود دارد

2-هر کدام از کارها تنها بر روی زیر مجموعه ای از مجموعه ماشینها می تواند پردازش شوند

3-تمامی کارها در ابتدای افق زمانبندی در دسترس نمی باشد به عبارتی پردازش کار نمی تواند قبل از زمان دسترسی آغاز شود

4-تمامی ماشینها به طور مستمر دسترس هستند و امکان خرابی ماشینها وجود ندارد

5-هر ماشین در هر لحظه قادر به پردازش تنها یک کار می باشد

6-هر کار در طول زمان پردازش خود تنها بر روی یک ماشین پردازش می شود

7-زمانهای پردازش،نصب،موعد تحویل و ضرایب هزینه زود کرد و دیر کرد زمانی معین می باشد

8-بیکاری ماشینها مجاز است

1-8- ضرورت انجام تحقیق :

با توجه به اهمیت روزافزون مسائل ماشین های موازی در نظر گرفتن معیارهای مختلف مورد توجه محققان این علم می باشد.