کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6895761 1445981 2016 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Optimal restricted due date assignment in scheduling
ترجمه فارسی عنوان
تعیین زمان دقیق بهینه در برنامه ریزی
کلمات کلیدی
برنامه ریزی، تعیین زمان تحویل، الگوریتم های تقریبی، دوران عقب ماندگی،
ترجمه چکیده
در مسائل برنامه ریزی کلاسیک معمول است فرض کنیم که تاریخ های به دست آمده از پارامترهای پیش تعیین شده برای زمانبندی است. با این حال، در سیستم های یکپارچه، تصمیم گیری های مربوط به زمان بندی و تصمیم گیری های زمان بندی باید با دقت هماهنگ شوند تا اطمینان حاصل شود که شرکت بتواند با تعیین تاریخ تعیین شده مواجه شود. بنابراین، اخیرا تلاش های بزرگی برای ارائه ابزارهایی برای بهینه سازی یکپارچه سازی زمانبندی تعیین شده و تصمیم گیری در زمانبندی انجام شده است. در بیشتر موارد، فرض بر این است که تاریخ تعیین شده (محدودیت ها) محدود نمی شود. با این حال، در بسیاری از موارد عملی، اختصاص دادن تاریخ های به موقع در آینده، ممکن است توافق های اولیه بین تولید کننده و مشتریانش را نقض کند. بنابراین، در این مقاله، ادبیات فعلی را برای مقابله با چنین محدودیتی گسترش می دهیم. این کار با تجزیه و تحلیل یک مدل انجام شده است که ادغام زمان تعیین شده و تصمیم گیری زمانی که هر کار ممکن است یک تاریخ متفاوتی تعیین کند که ارزش آن نمی تواند از یک آستانه از پیش تعریف شده تجاوز کند، انجام می شود. هدف این است که به طور کلی وزن زودهنگام، ضعف، و مجازات های تعیین شده از زمان به حداقل برسد. ما نشان می دهیم که این مشکل به معنی یک مشکل دوبعدی وزن است و بنابراین برای مجموعه ای بزرگ از موارد خاص بسیار سخت است، حتی زمانی که برنامه ریزی بر روی یک ماشین انجام می شود. سپس چندین مورد خاص را ارائه می کنیم که می تواند در زمان چند جمله ای حل شود و نتایج تقریبی را برای یک مشکل کمی اصلاح شده (و معادل آن) در تنظیمات دستگاه مختلف ارائه دهد.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش مقاله
تعیین زمان دقیق بهینه در برنامه ریزی
چکیده انگلیسی
In classical scheduling problems it is common to assume that the due dates are predefined parameters for the scheduler. In integrated systems, however, due date assignment and scheduling decisions have to be carefully coordinated to make sure that the company can meet the assigned due dates. Thus, a huge effort has been made recently to provide tools to optimally integrate due date assignment and scheduling decisions. In most cases it is common to assume that the assigned due date(s) are not restricted. However, in many practical cases, assigning due dates too far into the future may violate early agreements between the manufacturer and his customers. Thus, in this paper we extend the current literature to deal with such a constraint. This is done by analyzing a model that integrates due date assignment and scheduling decisions where each job may be assigned a different due date whose value cannot exceed a predefined threshold. The objective is to minimize the total weighted earliness, tardiness and due date assignment penalties. We show that the problem is equivalent to a two stepwise weighted tardiness problem, and thus for a large set of special cases it is strongly NP-hard, even when the scheduling is done on a single machine. We then provide several special cases that can be solved in polynomial time, and present approximation results for a slightly modified (and equivalent) problem on various machine settings.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 252, Issue 1, 1 July 2016, Pages 79-89
نویسندگان
,