پیشینه تحقیق زمان بندی و مسألهء زمانبندی کارگاه باز دارای ۳۰ صفحه می باشد فایل پیشینه تحقیق به صورت ورد 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 هستند:
زمان پردازش[۱۷] (pij): مدت زمان پردازش کار i توسط ماشین j است که در صورت عدم استفاده از ماشین j در فرآیند تکمیل کار i ، این مقدار صفر درنظر گرفته میشود و چنانچه قرار باشد کار i تنها توسط یکی از m ماشین (هرکدام) پردازش شود زیر نویس j حذف میشود.
زمان آمادهسازی[۱۸] (Sij): زمان آمادهسازی کار i روی ماشین j مدت زمانی است که طول میکشد تا کار روی ماشین قرار گرفته، تثبیت شده و آمادهء پردازش شود. عملیات پردازش بلافاصله پس از اتمام آمادهسازی شروع میشود.
زمان جداسازی[۱۹] (Rij): زمان جداسازی کار i از روی ماشین j مدت زمانی است که طول میکشد تا کار پس از تکمیل پردازش از روی ماشین برداشته شود. این زمان بدلیل جدا کردن ابزار تثبیت از قطعه درنظر گرفته میشود. اتمام زمان جداسازی بمنزله اتمام کار است.
زمان آماده به کار بودن[۲۰] (ri): نقطهای از زمان که کار i به سیستم وارد میشود و در حقیقت زودترین زمانی است که میتوان شروع به پردازش کار i نمود.
موعد تحویل[۲۱] (di): نقطهای از زمان که طبق قرار قبلی با مشتری باید کار i تحویل شود. باتوجه به تعریف مذکور، تکمیل کار زودتر از موعد تحویل، هزینههای نگهداری و تأخیر از موعد تحویل، هزینههای دیرکرد را میتواند ناشی شود.
در این تحقیق از نمادگذاری برای کلاسه بندی مسألههای زمانبندی استفاده میشود [۱۶]. در این نمادگذاری، α نمایندهء محیط ماشینها و نوع کارگاه بوده و شامل یک ورودی منفرد است. نماد β مشخصههای کاری و محدودیتهای زمانبندی را بیان میکند که میتواند چندین ورودی داشته باشد و یا تهی باشد. نماد γ نیز شامل تابع هدفی است که میبایست بهینه گردد که عمدتاً یک ورودی منفرد دارد. در ادامه به تشریح مقادیر ممکن هریک از نمادهای مذکور میپردازیم.
در یک واحد صنعتی و یا به تعبیری کارگاه، ترکیبهای مختلف ماشینها اعم از نوع ماشینها و عملیاتی که میتوانند انجام دهند، چگونگی انجام عملیات و نیز نحوهء چیدمان آنها منجر به ایجاد سیستمها مختلفی میشود. درحقیقت مزیت چنین دستهبندیهایی این است که امکان تحلیل بهتر برای محققین فراهم میشود. پارامتر α که پیشتر به آن اشاره شد، بیانگر این دستهبندی بوده و مقادیری بشرح زیر را میتواند داشته باشد:
تک ماشین[۲۲] (۱): در این محیط تنها یک ماشین در سیستم وجود دارد. این محیط حالت خاصی از تمامی محیطهای پیچیدهء دیگر است.
m ماشین موازی یکسان[۲۳] (Pm): m ماشین کاملاً یکسان بصورت موازی در سیستم وجود دارند. هر کار i دارای یک عملیات است که باید تنها توسط یکی از این ماشینها پردازش شود.
m ماشین موازی با سرعتهای متفاوت[۲۴] (Qm): m ماشین با سرعتهای متفاوت بصورت موازی در سیستم وجود دارند. با درنظرگرفتن پارامتر sj بعنوان سرعت ماشین j ، زمان پردازش کار i درصورت قرار گرفتن روی ماشین j (pij) از تقسیم pi/Sj حاصل میشود.
m ماشین موازی نامرتبط[۲۵] (Rm): m ماشین بصورت موازی در سیستم وجود دارند که هر یک از آنها کارهای مختلف را با سرعتهای متفاوتی انجام میدهند. ماشین j کار i را با سرعت sij پردازش میکند. زمان پردازش کار i روی ماشین j (pij) برابر با pi/Sj خواهد بود.
کار کارگاهی[۲۶] m ماشینه (Jm): در کار کارگاهی با m ماشین، هرکار مسیر از پیش تعیین شدهء خود را دارد که ممکن است توسط برخی از ماشینها چندین بار پردازش شود و یا روی ماشینی هرگز قرار نگیرد.
جریان کارگاهی[۲۷] m ماشینه (Fm): در جریان کارگاهی با m ماشین، ماشینها بصورت خطی و پشت سر هم قرار گرفتهاند و تمامی کارها از اولین تا آخرین ماشین مسیر یکسانی دارند.
کارگاه باز[۲۸] m ماشینه (Om): در کارگاه باز با 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
تمامی فایل های پیشینه تحقیق و پرسشنامه و مقالات مربوطه به صورت فایل دنلودی می باشند و شما به محض پرداخت آنلاین مبلغ همان لحظه قادر به دریافت فایل خواهید بود. این عملیات کاملاً خودکار بوده و توسط سیستم انجام می پذیرد. جهت پرداخت مبلغ شما به درگاه پرداخت یکی از بانک ها منتقل خواهید شد، برای پرداخت آنلاین از درگاه بانک این بانک ها، حتماً نیاز نیست که شما شماره کارت همان بانک را داشته باشید و بلکه شما میتوانید از طریق همه کارت های عضو شبکه بانکی، مبلغ را پرداخت نمایید.
ارسال نظر