أنظمة المهام المترية

أنظمة المهام هي كائنات رياضية تُستخدم لنمذجة مجموعة التكوينات الممكنة للخوارزميات المتصلة بالإنترنت . وقد طُرحت هذه الأنظمة من قِبل بورودين ، ولينال ، وساكس ( 1992) لنمذجة مجموعة متنوعة من المشكلات المتصلة بالإنترنت. يحدد نظام المهام مجموعة من الحالات وتكاليف تغييرها. ويتلقى نظام المهام كمدخل سلسلة من الطلبات، بحيث يُخصص كل طلب أوقات معالجة للحالات. يهدف نظام المهام المتصل بالإنترنت إلى إنشاء جدول زمني يُقلل التكلفة الإجمالية المتكبدة نتيجة معالجة المهام بالنسبة للحالات، وكذلك تكلفة تغيير الحالات.

إذا كانت دالة تكلفة تغيير الحالات مقياسًا ، فإن نظام المهام يُسمى نظام مهام متري (MTS). وهذا هو النوع الأكثر شيوعًا من أنظمة المهام. تُعمم أنظمة المهام المترية المشكلات الآنية مثل الترحيل ، والوصول إلى القوائم، ومشكلة الخوادم المتعددة (في المساحات المحدودة).

نظام المهام هو زوج${\displaystyle (S,d)}$أين${\displaystyle S=\{s_{1},s_{2},\dotsc ,s_{n}\}}$هي مجموعة من الولايات و${\displaystyle d:S\times S\rightarrow \mathbb {R} }$هي دالة مسافة. إذا${\displaystyle d}$هو مقياس،${\displaystyle (S,d)}$هو نظام مهام متري. المدخلات لنظام المهام عبارة عن تسلسل${\displaystyle \sigma =T_{1},T_{2},\dotsc ,T_{l}}$بحيث يكون لكل${\displaystyle i}$،${\displaystyle T_{i}}$هو متجه من${\displaystyle n}$المدخلات غير السالبة التي تحدد تكاليف المعالجة لـ${\displaystyle n}$الولايات عند معالجة${\displaystyle i}$المهمة رقم 1.

تقوم خوارزمية نظام المهام بإنتاج جدول زمني${\displaystyle \pi }$وهذا ما يحدد تسلسل الحالات. على سبيل المثال،${\displaystyle \pi (i)=s_{j}}$يعني ذلك أن${\displaystyle i}$المهمة${\displaystyle T_{i}}$يتم تشغيله في الولاية${\displaystyle s_{j}}$تكلفة معالجة الجدول الزمني هي ${\displaystyle \mathrm {cost} (\pi ,\sigma )=\sum _{i=1}^{l}d(\pi (i-1),\pi (i))+T_{i}(\pi (i)).}$

الهدف من الخوارزمية هو إيجاد جدول زمني بحيث يتم تقليل التكلفة إلى الحد الأدنى.

كما هو معتاد في المسائل المتعلقة بالأنظمة الإلكترونية، فإن المقياس الأكثر شيوعًا لتحليل الخوارزميات لأنظمة المهام المترية هو التحليل التنافسي ، حيث تتم مقارنة أداء خوارزمية إلكترونية بأداء خوارزمية مثالية غير متصلة بالإنترنت. بالنسبة للخوارزميات الإلكترونية الحتمية، يوجد حد فاصل دقيق.${\displaystyle 2n-1}$على أساس النسبة التنافسية وفقًا لـ Borodin et al. (1992).

بالنسبة للخوارزميات العشوائية عبر الإنترنت، فإن نسبة التنافس تكون محدودة من الأسفل بـ${\displaystyle \Omega (\log n/\log \log n)}$وحدودها العليا${\displaystyle O\left((\log n)^{2}\right)}$يعود الحد الأدنى إلى بارتال وآخرون (2006، 2005). أما الحد الأعلى فيعود إلى بوبيك وكوهين ولي ولي (2018) الذين حسّنوا نتيجة فيات ومندل (2003).

توجد نتائج عديدة لأنواع مختلفة من المقاييس المقيدة.

• نموذج الخصم
• التحليل التنافسي
• مشكلة خادم K
• خوارزمية الإنترنت
• خوارزمية استبدال الصفحات
• الحوسبة في الوقت الحقيقي

• يائير بارتال؛ أفريم بلوم؛ كارل بيرش وأندرو تومكينز (1997). "خوارزمية تنافسية متعددة اللوغاريتمات (n) لأنظمة المهام المترية". وقائع الندوة السنوية التاسعة والعشرين لجمعية الحوسبة الآلية (ACM) حول نظرية الحوسبة . الصفحات 711-719 . doi : 10.1145/258533.258667 . 

• يائير بارتال، بيلا بولوباس ، مانور مندل (2006). "نظريات من نوع رامزي للفضاءات المترية مع تطبيقات على المسائل الآنية". مجلة علوم الحاسوب والنظم . 72 (5): 890-921 . arXiv : cs/0406028 . doi : 10.1016/j.jcss.2005.05.008 . S2CID 1450455 . {{cite journal}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )

• يائير بارتال، ناثان لينال، مانور مندل، آساف ناور (2005). "حول ظواهر رامزي المترية". حوليات الرياضيات . 162 (2): 643-709 . arXiv : math/0406353 . doi : 10.4007/annals.2005.162.643 .{{cite journal}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )

• آلان بورودين وران اليانيف (1998).الحوسبة عبر الإنترنت والتحليل التنافسي. مطبعة جامعة كامبريدج. الصفحات 123-149 . 
• ألان بورودين ، ناتي لينال ، ومايكل ساكس (1992). "خوارزمية مثلى عبر الإنترنت لأنظمة المهام المترية" . مجلة ACM . 39 (4): 745-763 . doi : 10.1145/146585.146588 . S2CID 18783826 . {{cite journal}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )

• آموس فيات ومانور مندل (2003). "خوارزميات أفضل لأنظمة وتطبيقات المهام المترية غير العادلة". مجلة SIAM للحوسبة ، 32 (6): 1403-1422 . arXiv : cs/0406034 . doi : 10.1137/S0097539700376159 .

• بوبيك، سيباستيان؛ كوهين، مايكل ب.؛ لي، جيمس؛ ولي، ين تات (2019). "أنظمة المهام المترية على الأشجار عبر الهبوط المرآوي واللصق غير العادل". وقائع الندوة السنوية الثلاثين لجمعية ACM-SIAM حول الخوارزميات المنفصلة . arXiv : 1807.04404 .