Multiagent Scheduling: Models and Algorithms

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

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

Scheduling theory has received a growing interest since its origins in the second half of the 20th century. Developed initially for the study of scheduling problems with a single objective, the theory has been recently extended to problems involving multiple criteria. However, this extension has still left a gap between the classical multi-criteria approaches and some real-life problems in which not all jobs contribute to the evaluation of each criterion.

In this book, we close this gap by presenting and developing multi-agent scheduling models in which subsets of jobs sharing the same resources are evaluated by different criteria. Several scenarios are introduced, depending on the definition and the intersection structure of the job subsets. Complexity results, approximation schemes, heuristics and exact algorithms are discussed for single-machine and parallel-machine scheduling environments. Definitions and algorithms are illustrated with the help of examples and figures.