Scheduling with Time-Changing Effects and Rate-Modifying Activities

در نظریه زمان‌بندی، مدل‌هایی که در طول دو دهه اخیر توجه قابل توجهی را به خود جلب کرده‌اند، اجازه می‌دهند زمان‌های پردازش متغیر باشد، یعنی تحت تأثیرات مختلفی قرار گیرد که زمان پردازش واقعی یک کار را به آن وابسته می‌کند. مکان در یک برنامه تأثیر این تأثیرات شامل، اما نه محدود به، زوال و یادگیری است. تحت تأثیر نوع اول، هر چه یک کار دیرتر برنامه ریزی شود، زمان پردازش واقعی آن طولانی تر می شود. در مورد یادگیری، به تعویق انداختن یک کار منجر به زمان پردازش کوتاه‌تر می‌شود. زمان‌بندی با اثرات تغییر زمان و فعالیت‌های تغییر نرخ تحقیقات پیشرفته در این زمینه را پوشش می‌دهد و پیشرفت می‌دهد.

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

In scheduling theory, the models that have attracted considerable attention during the last two decades allow the processing times to be variable, i.e., to be subjected to various effects that make the actual processing time of a job dependent on its location in a schedule. The impact of these effects includes, but is not limited to, deterioration and learning. Under the first type of effect, the later a job is scheduled, the longer its actual processing time becomes. In the case of learning, delaying a job will result in shorter processing times. Scheduling with Time-Changing Effects and Rate-Modifying Activities covers and advances the state-of-the-art research in this area.

The book focuses on single machine and parallel machine scheduling problems to minimize either the maximum completion time or the sum of completion times of all jobs, provided that the processing times are subject to various effects. Models that describe deterioration, learning and general non-monotone effects to be considered include positional, start-time dependent, cumulative and their combinations, which cover most of the traditionally used models. The authors also consider more enhanced models in which the decision-maker may insert certain Rate-Modifying Activities (RMA) on processing machines, such as for example, maintenance or rest periods. In any case, the processing times of jobs are not only dependent on effects mentioned above but also on the place of a job in a schedule relative to an RMA. For most of the enhanced models described in the book, polynomial-time algorithms are presented which are based on similar algorithmic ideas such as reduction to linear assignment problems (in a full form or in a reduced form), discrete convexity, and controlled generation of options.