قوانين الحفظ، البوليماترويدات الممتدة ومشكلات اللصوص متعدد الذراعين؛ نهج متعددة الأوجه للأنظمة القابلة للفهرسة

نظهر أنه إذا كانت مقاييس الأداء في مشاكل الجدولة العشوائية والديناميكية تفي بقوانين الحفظ العامة، فإن المنطقة الممكنة للأداء القابل للتحقيق هي بوليهدرا تسمى بوليماترويد موسع، الذي يعمم البوليماترويدات الكلاسيكية التي قدمها إدموندز. يتم حل تحسين هدف خطي على بوليماترويد موسع بواسطة خوارزمية جشعة تكيفية، مما يؤدي إلى حل أمثل له خاصية القابلية للفهرسة (أنظمة قابلة للفهرسة). تحت شرط معين، تمتلك المؤشرات خاصية تحليل أقوى (أنظمة قابلة للتفكيك). يمكن تحليل المشاكل التالية باستخدام نظريتنا: مشكلات اللصوص متعدد الذراعين، لصوص التفرع، جدولة قوائم متعددة الفئات (مع أو بدون تغذية راجعة)، جدولة دفعة من الوظائف. تشمل نتائجنا: (1) تصنيف الأنظمة القابلة للفهرسة كنظم تلبي قوانين الحفظ العامة، (2) شرط كافٍ لكي تكون الأنظمة القابلة للفهرسة قابلة للتفكيك، (3) إثبات جديد برمجة خطية لخاصية التفكيك لمؤشرات غيتينز في مشكلات اللصوص متعدد الذراعين، (4) نهج لتحليل الحساسية للأنظمة القابلة للفهرسة، (5) تصنيف مؤشرات الأنظمة القابلة للفهرسة كمجموعات من المتغيرات الثنائية وتفسير اقتصادي لمؤشرات لصوص التفرع من حيث خيارات التقاعد، (6) تحليل القابلية للفهرسة للصوص التفرع غير المخصوم، (7) خوارزمية جديدة لحساب مؤشرات الأنظمة القابلة للفهرسة (وبخاصة مؤشرات غيتينز)، بسرعة تصل إلى أسرع خوارزمية معروفة، (8) توحيد خوارزمية كليموف لجدولة للقوائم متعددة الفئات وخوارزمية غيتينز لمشكلات اللصوص متعدد الذراعين كحالات خاصة من نفس الخوارزمية، (9) صيغة مغلقة لأقصى مكافأة لمشكلة اللصوص متعدد الذراعين، مع إثبات جديد للخصائص الفرعية و(10) فهم ثبات المؤشرات بالنسبة لبعض معلمات المشكلة. يوفر نهجنا معالجة متعددة الأوجه للعديد من المشاكل الكلاسيكية في الجدولة العشوائية والديناميكية وهو قادر على معالجة المتغيرات مثل: معيار تكلفة مخصومة مقابل غير مخصومة، مكافآت مقابل ضرائب، زمن متقطع مقابل مستمر، ودوال هدف خطية مقابل غير خطية.