پیشینه تحقیق زمان بندی و مسألهء زمانبندی کارگاه باز  دارای ۳۰ صفحه می باشد  فایل پیشینه تحقیق به صورت ورد  word و قابل ویرایش می باشد. بلافاصله بعد از پرداخت و خرید لینک دنلود فایل نمایش داده می شود و قادر خواهید بود  آن را دانلود و دریافت نمایید . ضمناً لینک دانلود فایل همان لحظه به آدرس ایمیل ثبت شده شما ارسال می گردد.

فهرست مطالب

۱-مقدمه    ۴
۲-تعاریف زمانبندی    ۵
۲-۱- نمادها    ۵
۲-۲- محیط ماشینها و نوع کارگاه    ۶
۲-۳- مشخصههای کاری و محدودیتهای زمانبندی    ۷
۲-۴- معیارهای بهینهسازی    ۹
۳-نظریهء زمانبندی    ۱۱
۴-برنامهریزی ریاضی    ۱۱
۵-زمانبندی چند هدفه    ۱۲
۶-الگوریتمهای فرا ابتکاری در بهینهسازی    ۱۳
۶-۱ الگوریتم ژنتیک    ۱۴
۷-طراحی آزمایشات    ۱۵
۸-مسألهء زمانبندی کارگاه باز    ۱۵
۹- مقدمه    ۱۸
۱۰- معیارهای اندازهگیری و تابع هدف    ۱۸
۱۱- مجاز نبودن بریدگی کارها    ۲۱
۱۲- نگهداری و تعمیرات دورهای و محدودیت عدم دسترسی ماشینها    ۲۱
۱۳- زمانهای حمل و نقل    ۲۲
۱۴- زمانهای آمادهسازی و جداسازی    ۲۳
۱۵- روشهای حل    ۲۳
۱۶- طراحی آزمایشات    ۲۵
مراجع    ۲۷

مراجع

 HERRMANN J.W., Handbook of Production Scheduling, Springer Science + Business Media, Inc, ISBN-10:0-387-33115-8 (HB) (2006).

Wight O.W., Production and Inventory Management in the Computer Age, Van Nostrand Reinhold Company, Inc., New York (1984).

Cox J.F., Blackstone J.H., Spencer M.S., APICS Dictionary, American Production and Inventory Control Society, Falls Church, Virginia (1992).

Leung J.Y.T., Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Chapman & Hall/CRC Computer and Information Science Series (2004).

Jackson J.R., Scheduling a production line to minimize maximum tardiness, Research Report 43, Management Science Research Project, University of California, Los Angeles (1955).

Jackson J.R., An extension of Johnson’s results on job lot scheduling, Naval Research Logistics Quarterly 3 (1956) 201–۲۰۳٫

Johnson S.M., Optimal two and three-stage production schedules with setup times included, Naval Research Logistics Quarterly 1 (1954) 61–۶۷٫

Smith W.E., Various optimizers for single stage production, Naval Research Logistics Quarterly 3 (1956) 59–۶۶٫

Cook S.A., The complexity of theorem-proving procedures, in Procedings of the 3rd Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, New York (1971) 151–۱۵۸٫

Garey M.R., Johnson D.S., Computers and Intractability: A Guide to the Theory of NPCompleteness, H. Freeman, New York (1979).

Karp R.M., Reducibility among combinatorial problems, Miller R.E., Thatcher J.W. (eds), Complexity of Computer Computations, Plenum Press, New York (1972) pp. 85–۱۰۳٫

Brucker P., Scheduling Algorithms, 3rd ed., Springer-Verlag, New York (2001).

Lenstra J.K., Rinnooy Kan A.H.G., Computational complexity of scheduling under precedence constraints, Operations Research 26 (1978) 22–۳۵٫

Lenstra J.K., Rinnooy Kan A.H.G., Brucker P., Complexity of machine scheduling problems, Annals of Discrete Mathematics 1 (1977) 343–۳۶۲٫

Pinedo M., Scheduling: Theory, Algorithms, and Systems, 2nd ed., Prentice Hall, New Jersey (2002).

Graham R.L., Lawler E.L., Lenstra J.K., RinnooyKan A.H.G., Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics 5 (1979) 287–۳۲۶٫

کنت آر. بیکر، توالی عملیات و زمانبندی، ترجمهء فرهاد قاسمی طاری، محمدتقی فاطمی قمی، دانشگاه صنعتی شریف، مؤسسات انتشارات علمی (۱۳۷۶).

کاتا جی. مورتی، برنامه­ریزی خطی، ترجمهء ابراهیم محمودآبادی، همدان، انتشارات دانشگاه بوعلی سینا (۱۳۸۹).

۱-مقدمه

از مهمترین شرط­های ارتقای وضعیت فعلی در هر سازمان می­توان به استفادهء مناسب از سرمایه­ها و جلوگیری از هدر رفت آن­ها اشاره کرد. منظور از ” استفادهء مناسب ” در اینجا مفهومِ واژهء کارایی[۱] یعنی سرعت عمل در استفاده از ظرفیت است که بدون داشتن برنامهء از پیش تعیین شده ممکن نیست. افزون بر آن، هرچه دقت در برنامه بیشتر و مطالعه مکفی­تر باشد سرعت عمل بیشتر شده و توان رقابتی بالاتر می­رود. وقتی صحبت از سرمایه­های یک سازمان به میان می­آید ممکن است ذهن­ها به سمت سرمایه­های فیزیکی مثل ماشین­آلات و دستگاه­های گران­قیمت منحرف شود. حال آنکه، مفهوم مورد انتظار ما بطور خاص “زمان” است. استفادهء مناسب از زمان بعنوان یک سرمایه و جلوگیری از هدر رفت آن از جمله ابزارهای مهم مدیرانِ سازمان­ها در عرصه­های رقابتی است. زمان را می­توان منبعی دانست که باید بطور صحیح تقسیم­بندی و مدیریت شده و با برنامهء خاص به فعالیت­ها تخصیص داده شود و این همان چیزیست که به آن زمان­بندی[۲] اطلاق می­شود.

زمان­بندی شامل تخصیص[۳] منابع محدود به فعالیت­هاست با هدف بهینه­سازی یک یا چند معیار اندازه­گیری[۴] [۱]. از طرفی، ماهیت برخی منابع همچون ماشین­آلات و نیروی انسانی بگونه­ای است که قادر به انجام همزمان بیش از یک فعالیت نیستند. بنابراین، تعریف دیگری برای زمان­بندی به این شرح ارائه می­شود: زمان­بندی، یافتن توالی[۵] مناسب انجام فعالیت­ها توسط ماشین­ها و یا نیروی انسانی است بنحوی که یک یا چند معیار اندازه­گیری بهینه شوند. برای تحلیل سیستم زمان­بندیِ تولیدِ جاری و یافتن راه­های بهبود آن، آگاهی از روش­های زمان­بندی تولید بسیار مهم است. دو مسألهء کلیدی در زمان­بندیِ تولید اولویت و ظرفیت هستند [۲]. بعبارت دیگر، “چه کاری باید ابتدا انجام شود؟” و “چه کسی باید آن را انجام دهد؟” وایت [۲] زمان­بندی را اینگونه تعریف می­کند: “تعیین زمان برای انجام یک فعالیت”. او همچنین، در یک شرکت تولیدی زمان­بندیِ تفصیلی[۶] در سطح یک کارگاه را درنظر می­گیرد. یعنی، زمان­بندی که در آن زمان شروع و پایان هر عملیات معلوم است. کوکس و همکاران [۳] زمان­بندی تفصیلی را اینگونه تعریف می­کنند: “تخصیص واقعی زمان شروع و یا پایان فعالیت­ها یا گروهی از فعالیت­ها بنحوی که سفارش تولید در موعد مقرر تکمیل شود.” آن­ها همچنین از زمان­بندی عملیات[۷]، زمان­بندی سفارش[۸] و زمان­بندی کارگاه[۹] بطور معادل یاد می­کنند.

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

مطالعه بر روی زمان­بندی به دههء ۱۹۵۰ برمی­گردد که محققان در پژوهش عملیاتی[۱۰]، مهندسی صنایع و مدیریت با مسألهء اداره کردن فعالیت­های مختلفی که در یک کارگاه رخ می­دادند مواجه بودند. در آن زمان، الگوریتم­های زمان­بندی خوب می­توانستند هزینهء تولید را در فرآیند ساخت کاهش داده و توان رغابتی شرکت­ها را بالا ببرند. در اواخر دههء ۱۹۶۰، دانشمندان کامپیوتر نیز با مسألهء زمان­بندی در توسعه سیستم­های عملیاتی روبرو شدند. چراکه، در آن روزها منابع محاسباتی همچون پردازشگرها و حافظه­ها محدود بودند و بهره­برداری مؤثر از این منابع محدود می­توانست هزینهء‌ اجرای برنامه­های کامپیوتری را کاهش دهد. بنابراین، مطالعه بر روی زمان­بندی توجیه اقتصادی پیدا کرد [۴].

مسأله­های زمان­بندی در دههء ۱۹۵۰ بسیار ساده بودند و تعدادی الگوریتم­های کارا برای رسیدن به جواب بهینه توسعه یافتند که کارهای جکسون [۵،۶]، جانسون [۷] و اسمیت [۸] از مهمترین آن­ها هستند. با گذشت زمان، مسأله­ها پیچیده­تر شده و دیگر محققان قادر به توسعه الگوریتم­های کارا برای آن­ها نبودند. بیشتر محققان تلاش کردند روش­های شاخه و کران[۱۱] را که عمدتاً الگوریتم­هایی با زمان نمایی[۱۲] بودند را گسترش دهند. با ظهور تئوری پیچیدگی[۱۳] [۱۱-۹]، محققان دریافتند که بسیاری از این مسأله­ها ذاتاً برای حل سخت هستند. در دههء ۱۹۷۰ نشان داده شد که بیشتر مسأله­های زمان­بندی NP-hard هستند [۱۵-۱۲] یعنی زمان حل آن­ها شدیداً غیر چندجمله­ای[۱۴] است. در دههء ۱۹۸۰، چندین زمینهء مختلف در دانشگاه و صنعت مورد بررسی قرار گرفت. یکی از این زمینه­ها توسعه و تحلیل الگوریتم­های تقریبی[۱۵] و دیگری افزایش توجه به مسأله­های زمان­بندی اتفاقی[۱۶] بود. از آن پس، تحقیق در زمینهء تئوری زمان­بندی با فراز و نشیب­هایی همراه بوده­است. بعد از گذشت بیش از ۶۰ سال، هنوز ابهاماتی در این شاخه از علم وجود دارد.

۲-تعاریف زمان ­بندی

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

۲-۱- نمادها

در زیر به برخی پارامترها و نمادهایی که در طول این تحقیق استفاده می­شوند اشاره می­کنیم.

تعداد کارها n و تعداد ماشین­ها m درنظر گرفته می­شود. زیر نویس­های i و k به کار و زیرنویس­های j و h به ماشین اشاره دارند. بدین­ترتیب، اصطلاحات زیر مربوط به کار i هستند:

زمان پردازش[۱۷] (p_ij): مدت زمان پردازش کار i توسط ماشین j است که در صورت عدم استفاده از ماشین j در فرآیند تکمیل کار i ، این مقدار صفر درنظر گرفته می­شود و چنانچه قرار باشد کار i تنها توسط یکی از m ماشین (هرکدام) پردازش شود زیر نویس j حذف می­شود.

زمان آماده­سازی[۱۸] (S_ij): زمان آماده­سازی کار i روی ماشین j  مدت زمانی است که طول می­کشد تا کار روی ماشین قرار گرفته، تثبیت شده و آمادهء پردازش شود. عملیات پردازش بلافاصله پس از اتمام آماده­سازی شروع می­شود.

زمان جداسازی[۱۹] (R_ij): زمان جداسازی کار i از روی ماشین j  مدت زمانی است که طول می­کشد تا کار پس از تکمیل پردازش از روی ماشین برداشته شود. این زمان بدلیل جدا کردن ابزار تثبیت از قطعه درنظر گرفته می­شود. اتمام زمان جداسازی بمنزله اتمام کار است.

زمان آماده به کار بودن[۲۰] (r_i): نقطه­ای از زمان که کار i به سیستم وارد می­شود و در حقیقت زودترین زمانی است که می­توان شروع به پردازش کار i نمود.

موعد تحویل[۲۱] (d_i): نقطه­ای از زمان که طبق قرار قبلی با مشتری باید کار i تحویل شود. باتوجه به تعریف مذکور، تکمیل کار زودتر از موعد تحویل، هزینه­های نگهداری و تأخیر از موعد تحویل، هزینه­های دیرکرد را می­تواند ناشی شود.

در این تحقیق از نمادگذاری  برای کلاسه بندی مسأله­های زمان­بندی استفاده می­شود [۱۶]. در این نمادگذاری، α نمایندهء محیط ماشین­ها و نوع کارگاه بوده و شامل یک ورودی منفرد است. نماد β مشخصه­های کاری و محدودیت­های زمان­بندی را بیان می­کند که می­تواند چندین ورودی داشته باشد و یا تهی باشد. نماد γ نیز شامل تابع هدفی است که می­بایست بهینه گردد که عمدتاً یک ورودی منفرد دارد. در ادامه به تشریح مقادیر ممکن هریک از نمادهای مذکور می­پردازیم.

۲-۲- محیط ماشین­ها و نوع کارگاه

در یک واحد صنعتی و یا به تعبیری کارگاه، ترکیب­های مختلف ماشین­ها اعم از نوع ماشین­ها و عملیاتی که می­توانند انجام دهند، چگونگی انجام عملیات و نیز نحوهء چیدمان آن­ها منجر به ایجاد سیستم­ها مختلفی می­شود. درحقیقت مزیت چنین دسته­بندی­هایی این است که امکان تحلیل بهتر برای محققین فراهم می­شود. پارامتر α که پیشتر به آن اشاره شد، بیانگر این دسته­بندی بوده و مقادیری بشرح زیر را می­تواند داشته باشد:

تک ماشین[۲۲] (۱): در این محیط تنها یک ماشین در سیستم وجود دارد. این محیط حالت خاصی از تمامی محیط­های پیچیدهء دیگر است.

m ماشین­ موازی یکسان[۲۳] (P_m): m ماشین­ کاملاً یکسان بصورت موازی در سیستم وجود دارند. هر کار i دارای یک عملیات است که باید تنها توسط یکی از این ماشین­ها پردازش شود.

m ماشین­ موازی با سرعت­های متفاوت[۲۴] (Q_m): m ماشین­ با سرعت­های متفاوت بصورت موازی در سیستم وجود دارند. با درنظرگرفتن پارامتر s_j بعنوان سرعت ماشین j ، زمان پردازش کار i درصورت قرار گرفتن روی ماشین  j (p_ij) از تقسیم p_i/S_j حاصل می­شود.

m ماشین­ موازی نامرتبط[۲۵] (R_m): m ماشین­ بصورت موازی در سیستم وجود دارند که هر یک از آن­ها کارهای مختلف را با سرعت­های متفاوتی انجام می­دهند. ماشین  j کار i را با سرعت s_ij پردازش می­کند. زمان پردازش کار i روی ماشین  j (p_ij) برابر با p_i/S_j خواهد بود.

کار کارگاهی[۲۶] m ماشینه (J_m): در کار کارگاهی با m ماشین­، هرکار مسیر از پیش تعیین شدهء خود را دارد که ممکن است توسط برخی از ماشین­ها چندین بار پردازش شود و یا روی ماشینی هرگز قرار نگیرد.

جریان کارگاهی[۲۷] m ماشینه (F_m): در جریان کارگاهی با m ماشین­، ماشین­ها بصورت خطی و پشت سر هم قرار گرفته­اند و تمامی کارها از اولین تا آخرین ماشین مسیر یکسانی دارند.

کارگاه باز[۲۸] m ماشینه (O_m): در کارگاه باز با m ماشین­، هر کار باید دقیقاً یکبار توسط هر یک از ماشین­ها پردازش شود ولی ترتیب آن­ها دلخواه است.

۲-۳- مشخصه­ های کاری و محدودیت­های زمان­بندی

مشخصه­های کاری و محدودیت­های زمان­بندی در هر یک از انواع کارگاه­ها شرایط خاصی را بوجود می­آورند. در برخی موارد ممکن است فضای حل مسأله کوچک­تر و رسیدن به بهینگی را در سیستم تسریع ببخشند و در مواردی نیز می­توانند منجر به افزایش پیچیدگی محاسباتی مسأله­ها شوند. این مشخصه­ها و محدودیت­ها که توسط نماد β نشان داده می­شوند بقرار زیرند:

بریدگی[۱] (pmtn): پردازش کارها می­تواند قطع شده و بعداً روی ماشین دیگری ادامهء آن پردازش شود. درصورت مجاز بودن بریدگی، عبارت pmtn در قسمت مربوط به نماد β نمایش داده می­شود.

توقف ماشین با بریدگی[۲] (r-a): ماشین­ها در زمان­هایی قابل استفاده نبوده و کارها در صورت قطع شدن مجدداً از نقطهء قطع شده پردازش می­شوند.

[۱] Preemption

[۲] Resumable availability constraint

[۳] Non-resumable availability constraint

[۴] Semiresumable Type-I availability constraint

[۱] Efficiency

[۲] Scheduling

[۳] Allocation

[۴] Performance measures

[۵] Sequence

[۶] Detailed scheduling

[۷] Operations scheduling

[۸] Order scheduling

[۹] Shop scheduling

[۱۰] Operations research

[۱۱] Branch-and-bound

[۱۲] Exponential-time

[۱۳] Complexity theory

[۱۴] Non-polynomial

[۱۵] Approximation algorithms

[۱۶] Stochastic

[۱۷] Processing time

[۱۸] Setup time

[۱۹] Removal time

[۲۰] Release date

[۲۱] Due date

[۲۲] Single machine

[۲۳] Identical parallel machines

[۲۴] Uniform machines

[۲۵] Unrelated machines

[۲۶] Job-shop

[۲۷] Flow-shop

[۲۸] Open-shop

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