وبلاگ

در جهان رقابتی حاضر، توالی و زمانبندی مناسب، ضرورتی برای بقا در فضای بازار است. زمانبندی، ابزاری است كه استفاده از منابع در دسترس را بهینه می­كند. منابع و كارها در زمانبندی ممكن است انواع گوناگونی داشته باشد [1]. با توسعه جهان صنعتی، منابع بحرانی­تر می­شوند. زمانبندی این منابع، افزایش كارایی و بهره ­برداری از ظرفیت، كاهش زمان مورد نیاز برای تكمیل كارها و نهایتاً افزایش سوددهی یک سازمان را به دنبال خواهد داشت. در نتیجه، زمانبندی مناسب و مؤثر منابع مانند ماشین­ها، نیروی انسانی و غیره در محیط به شدت رقابتی امروز الزامیست [1،2].

 

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

 

مسأله زمانبندی ماشین، زمینه­ای غنی و مناسب برای تحقیقات است كه كاربردهای فراوانی در تولید، پشتیبانی، معماری كامپیوتر و مانند این را به همراه خواهد داشت. حوزه مورد بررسی در این پایان نامه ، مسأله ماشین­های موازی[2] است. زمانبندی ماشین­های موازی در ارتباط با چگونگی زمانبندی گروهی از كارها بر روی تعدادی از ماشین­ها به منظور اطمینان از پردازش كارها در مدت زمانی منطقی می­باشد. ماشین­های موازی از دو دیدگاه تئوری و عملی دارای اهمیت می­باشند. از دیدگاه تئوری، تعمیمی از تك ماشین[3] و حالت خاصی از محیط جریان كارگاهی انعطاف­پذیر[4] است. از دیدگاه عملی به این جهت كه در دنیای واقعی بسیار معمول هستند دارای اهمیت می­باشند [1]. علاوه بر این، روش­هایی كه در محیط ماشین­های موازی مورد استفاده قرار می­گیرند، قابل استفاده در فرایندهای تجزیه برای سیستم­های چند مرحله­ ای نیز می­باشد. زمانبندی صنایع به طور كلی از كاربرد مدل ماشین­های موازی سود برده است. ماشین­های موازی توانایی انجام عملیات یكسان با داشتن ظرفیت­ها و استعدادهای متفاوت را دارا می­باشند. در واقع ماشین­های موازی، افزایش ظرفیت و انعطاف­پذیری سیستم را با پردازش كارهای متفاوت به همراه خواهند داشت.

 

عموماً ماشین­ها در محیط موازی قادر به پردازش گروه یكسانی از كارها می­باشند، اما بر اساس زمان پردازش كار به سه دسته عمده طبقه ­بندی می­شوند: ماشین­های یكسان[5]، ماشین­های یكنواخت[6] و ماشین­های نامرتبط[7]. در حالتی­كه زمان پردازش كار بر روی همه ماشین­ها یكسان باشد، ماشین­های موازی یكسان نامیده می­شوند. اگر ماشین­ها دارای سرعت متفاوت باشند، یعنی زمان پردازش كارها

/%d8%af%d8%a7%d9%86%d9%84%d9%88%d8%af-%d9%be%d8%a7%db%8c%d8%a7%d9%86-%d9%86%d8%a7%d9%85%d9%87-%da%a9%d8%a7%d8%b1%d8%b4%d9%86%d8%a7%d8%b3%db%8c-%d8%a7%d8%b1%d8%b4%d8%af%d9%86%d8%b8%d8%b1%db%8c%d9%87/

 

 بر روی ماشین­ها متناسب با میزان سرعت در نظر گرفته شده باشد، ماشین­های موازی یكنواخت نامیده می­شوند. در حالتی كه زمان­های پردازش یک كار بر روی ماشین­های مختلف به طور دلخواه متفاوت باشند، ماشین­های موازی نامرتبط نامیده می­شوند [3]. در این پایان نامه ، مسأله ماشین­های موازی یکنواخت مورد بررسی قرار می­گیرد.

 

در ادامه به معرفی كار و نظریه زمانبندی و نحوه تعامل آن با برنامه ­ریزی خواهیم پرداخت. با توجه به این كه مدل­های زمانبندی معمولاً بر اساس تركیب ماشین­ها، نوع محدودیت­ها و معیارهای در نظر گرفته شده مشخص می­شوند، سپس به معرفی انواع متداولی از موارد بالا خواهیم پرداخت.

 

 

 

1-2- کار زمان­بندی

 

زمانبندی شامل برنامه ­ریزی و اولویت­دهی فعالیت­هایی است كه لازم است به ترتیب عملیات انجام شوند [2]. در بیشتر موارد عمل زمانبندی پس از حل برخی مسائل مربوط به برنامه ­ریزی اصولی مورد توجه قرار می­گیرد و باید همواره این نكته را مد نظر داشت كه تصمیمات مربوط به زمانبندی اهمیت كمتری نسبت به مجموعه وسیع­تری از تصمیمات مدیریتی دارد. برای مثال، در حل مسائل مربوط به ساخت، مسائل اساسی مدیریتی مربوط به انتخاب محصولی كه باید ساخته شود و تعیین میزان تولید هر محصول اولویت دارد. بعد از به­كارگیری بررسی بازار و تحلیل­های اقتصادی برای حل این­گونه مسائل، برنامه ­ریزی تكنولوژیكی به این مسأله كه محصول چگونه باید ساخته شود متمركز می­ شود و تنها بعد از اینكه جواب سوالات مربوط به برنامه ­ریزی داده شد و در دسترس بودن منابع دانسته شد، زمان برای توجه به مسائل زمانبندی مناسب است. تصمیمات اصولی مدیریت به مسائل سه گانه زیر مرتبط می­شوند.

 

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

 

2- در چه مقیاسی قرار است عرضه شود؟

 

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

 

پاسخ دادن به این پرسش­ها كار برنامه ­ریزی است. در مقابل، در كار زمانبندی فرض بر این است كه جواب پرسش­ها از پیش فراهم شده است. بنابراین كار زمانبندی صرفاً به وضعیتی مربوط می­ شود كه در آن طبیعت كارهایی كه باید زمانبندی شود توصیف شده و تركیب منابع موجود تعیین شده باشد[4]. در واقع زمانبندی ابزاری است كه استفاده از منابع در دسترس را بهینه می­كند.

 

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

 

[1] Due Date

 

[2] Parallel Machines

 

[3] Single Machine

 

[4] Flexible Flow Shop

 

[5] Identical Machines

 

[6] Uniform Machines

 

[7] Unrelated Machines