زمان­بندی شامل تخصیص[3] منابع محدود به فعالیت­هاست با هدف بهینه­سازی یك یا چند معیار اندازه­گیری[4] [1]. از طرفی، ماهیت برخی منابع همچون ماشین­آلات و نیروی انسانی بگونه­ای است كه قادر به انجام همزمان بیش از یك فعالیت نیستند. بنابراین، تعریف دیگری برای زمان­بندی به این شرح ارائه می­شود: زمان­بندی، یافتن توالی[5] مناسب انجام فعالیت­ها توسط ماشین­ها و یا نیروی انسانی است بنحوی كه یك یا چند معیار اندازه­گیری بهینه شوند. برای تحلیل سیستم زمان­بندیِ تولیدِ جاری و یافتن راه­های بهبود آن، آگاهی از روش­های زمان­بندی تولید بسیار مهم است. دو مسألهء كلیدی در زمان­بندیِ تولید اولویت و ظرفیت هستند [2]. بعبارت دیگر، “چه كاری باید ابتدا انجام شود؟” و “چه كسی باید آن را انجام دهد؟” وایت [2] زمان­بندی را اینگونه تعریف می­كند: “تعیین زمان برای انجام یك فعالیت”. او همچنین، در یك شركت تولیدی زمان­بندیِ تفصیلی[6] در سطح یك كارگاه را درنظر می­گیرد. یعنی، زمان­بندی كه در آن زمان شروع و پایان هر عملیات معلوم است. كوكس و همكاران [3] زمان­بندی تفصیلی را اینگونه تعریف می­كنند: “تخصیص واقعی زمان شروع و یا پایان فعالیت­ها یا گروهی از فعالیت­ها بنحوی كه سفارش تولید در موعد مقرر تكمیل شود.” آن­ها همچنین از زمان­بندی عملیات[7]، زمان­بندی سفارش[8] و زمان­بندی كارگاه[9] بطور معادل یاد می­كنند.

مطالعه بر روی زمان­بندی به دههء 1950 برمی­گردد كه محققان در پژوهش عملیاتی[10]، مهندسی صنایع و مدیریت با مسألهء اداره كردن فعالیت­های مختلفی كه در یك كارگاه رخ می­دادند مواجه بودند. در آن زمان، الگوریتم­های زمان­بندی خوب می­توانستند هزینهء تولید را در فرآیند ساخت كاهش داده و توان رغابتی شركت­ها را بالا ببرند. در اواخر دههء 1960، دانشمندان كامپیوتر نیز با مسألهء زمان­بندی در توسعه سیستم­های عملیاتی روبرو شدند. چراكه، در آن روزها منابع محاسباتی همچون پردازشگرها و حافظه­ها محدود بودند و بهره­برداری مؤثر از این منابع محدود می­توانست هزینهء‌ اجرای برنامه­های كامپیوتری را كاهش دهد. بنابراین، مطالعه بر روی زمان­بندی توجیه اقتصادی پیدا كرد [4].

خرید متن کامل این پایان نامه در سایت nefo.ir

مسأله­های زمان­بندی در دههء 1950 بسیار ساده بودند و تعدادی الگوریتم­های كارا برای رسیدن به جواب بهینه توسعه یافتند كه كارهای جكسون [5،6]، جانسون [7] و اسمیت [8] از مهمترین آن­ها هستند. با گذشت زمان، مسأله­ها پیچیده­تر شده و دیگر محققان قادر به توسعه الگوریتم­های كارا برای آن­ها نبودند. بیشتر محققان تلاش كردند روش­های شاخه و كران[11] را كه عمدتاً الگوریتم­هایی با زمان نمایی[12] بودند را گسترش دهند. با ظهور تئوری پیچیدگی[13] [11-9]، محققان دریافتند كه بسیاری از این مسأله­ها ذاتاً برای حل سخت هستند. در دههء 1970 نشان داده شد كه بیشتر مسأله­های زمان­بندی NP-hard هستند [15-12] یعنی زمان حل آن­ها شدیداً غیر چندجمله­ای[14] است. در دههء 1980، چندین زمینهء مختلف در دانشگاه و صنعت مورد بررسی قرار گرفت. یكی از این زمینه­ها توسعه و تحلیل الگوریتم­های تقریبی[15] و دیگری افزایش توجه به مسأله­های زمان­بندی اتفاقی[16] بود. از آن پس، تحقیق در زمینهء تئوری زمان­بندی با فراز و نشیب­هایی همراه بوده­است. بعد از گذشت بیش از 60 سال، هنوز ابهاماتی در این شاخه از علم وجود دارد.

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

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

[1] Efficiency

[2] Scheduling

[3] Allocation

[4] Performance measures

[5] Sequence

[6] Detailed scheduling

[7] Operations scheduling

[8] Order scheduling

[9] Shop scheduling

[10] Operations research

[11] Branch-and-bound

[12] Exponential-time

[13] Complexity theory