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

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

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

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

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