چکیده: در این پایان‌نامه به بررسی مسائل زمان‌بندی و زمان‌بندی معکوس پرداخته می‌شود‏، اهمیت مسائل زمان‌بندی امروزه در دنیای صنعت و تجارت و حتی در مواردی که با نیروی انسانی سر و کار داریم (مثلاً زمان‌بندی در بیمارستان‌ها یا مراکز آموزشی)‏، واضح است. زمان‌بندی در اغلب سازمان‌ها و ادارات و کارخانجات مورد نیاز است. یک زمان‌بندی مناسب می‌تواند به کاهش هزینه‌ها و افزایش بهره‌وری بیانجامد. همچنین توان رقابتی بالاتر برای تولیدکنندگان نیز از نتایج زمان‌بندی مؤثر است. هدف عمده زمان‌بندی ایجاد تعادل میان اهداف مغایر‏، به‌کارگیری مؤثر کارگران‏، تجهیزات و تسهیلات همزمان با کاهش زمان انتظار مشتریان و زمان فرآیندها است.‎ ‎ ضمن یادآوری این مهم‏، این رساله مسائل معکوس را مورد بررسی قرار می‌دهد‎ ‎.‎فرض کنید فرآیند تولید مستلزم بعضی مقدمات باشد که تولیدکننده می‌تواند قبل از شروع آنها را فراهم کند و سپس با توجه به اطلاعاتی که در اختیار دارد‏، بهترین دنباله را انتخاب ‌کند. ممکن است کارهایی که بعد از شروع فرآیند‏، وارد می‌شوند ویژگی‎‎های متفاوتی داشته باشند و در نتیجه جایگشت انتخابی دیگر بهینه نباشد و یا تغییری به یک‌باره در روند تولید و پردازش روی دهد. اگر به دلایل زیادی همچون محدودیت تکنولوژی جایگشت قابلیت تغییر نداشته باشد مثل هزینه بالا برای جابه‌جایی ایستگاه‌های کاری‏، تولیدکننده مجبور می‌شود سرعت انجام بعضی کارها را تنظیم کند‏، یعنی زمان پردازش را تنظیم کند. هزینه این تنیمات با استفاده از زمان‌بندی معکوس به حداقل خواهد رسید. در ادامه نشان می‌دهیم مسائل زمان‌بندی معکوس می‌توانند به صورت مسائل برنامه‌ریزی خطی ‏دربیایند‏، حتی در مورد مسائلی که مسئله زمان‌بندی آن‌ها در پیچیدگی زمانی چندجمله‌ای قابل حل نیست‏، نیز صادق است. ‎بهینه‌سازی معکوس در خیلی از مسائل‏، ازجمله در مسائل علوم ژئوفیزیک‏، عکس‌برداری پزشکی‏، مسائل مربوط به ترافیک و دیگر موارد کاربرد دارد.‎‎‏‎ ‎‎‏کاربرد‎‎ اصلی مسائل زمان‌بندی معکوس در شرایطی است که پارامترها می‌توانند بین تولیدی‌ها و مشتری‌ها تنظیم شوند. پارامترهای کار اصلی آن‌هایی هستند که مشتری‌ها ترجیح می‌دهند و مقادیر خطای متناظر با آنها‏، آنهایی هستند که مدیر تولیدی‌ها پیشنهاد می‌کنند. ‎ ‎یکی دیگر‎ از کاربردهای مسائل زمان‌بندی معکوس می‌تواند در سیستم‌هایی باشد‏ که کارها باید به صورت دنباله بیایند تا همواره موجود باشند‏، اما یک کنترل بر پارامترهای کار وجود دارد.‎‎‎ به‌طور خاص در این سیستم‌ها کسی که زمان‌بندی را انجام می‌دهد‏، زمانی که پارامترهای کار به سیستم داده می‌شوند اطلاعاتی در مورد آن‌ها به‌دست می‌آور‎د.‎‎ ‏زمان‌بند می‌تواند مقدار حقیقی پارامترها را با مشتری‌ها‏ تنظیم کند، به ترتیبی که حتی بعد از اینکه پارامترهای جدید به زمان‌بندی بهینه افزوده شد‏، آن‌ را بهینه نگه‌ دارد‏.‎‎ کاربرد زمان‌بندی معکوس کمترین مقدار تغییر در‎‎‎ پارامترهای کار ذکر شده‏ را تعیین‎ می‌کند. ‎