خوارزمية التوفيق المتعدد

يُثبت كلٌّ من كوفمان وغاري وجونسون الحدود العليا التالية على${\displaystyle r_{n}}$: ^{[ 1 ]}

• ${\displaystyle r_{n}\leq 8/7\approx 1.14}$لـ n = 2؛
• ${\displaystyle r_{n}\leq 15/13\approx 1.15}$لـ n = 3؛
• ${\displaystyle r_{n}\leq 20/17\approx 1.176}$لـ n = 4، 5، 6، 7؛
• ${\displaystyle r_{n}\leq 122/100=1.22}$لجميع قيم n ≥ 8.

أثناء خوارزمية MultiFit، يكون الحد الأدنى L دائمًا سعةً يستحيل معها تعبئة S في n صندوقًا. لذلك،${\displaystyle L<r_{n}\cdot OPT(S,n)}$في البداية، كان الفرق${\displaystyle UL}$هو على الأكثر مجموع ( S ) / n ، وهو على الأكثر${\displaystyle OPT(S,n)}$بعد تشغيل خوارزمية MultiFit لـ k تكرار، يتقلص الفرق بمقدار k مرة إلى النصف، لذلك${\displaystyle UL\leq (1/2)^{k}\cdot OPT(S,n)}$. لذلك،${\displaystyle U\leq (r_{n}+(1/2)^{k})\cdot OPT(S,n)}$لذلك، فإن الجدولة التي يُرجعها MultiFit لها مدة تنفيذ قصوى لا تتجاوز${\displaystyle r_{n}+(1/2)^{k}}$مضروبًا في المدة الزمنية المثلى للإنجاز. عندما${\displaystyle k}$إذا كانت قيمة كبيرة بما يكفي، يمكن جعل عامل التقريب في MultiFit قريبًا بشكل تعسفي من${\displaystyle r_{n}}$، وهو على الأكثر 1.22 .

أجرت أوراق بحثية لاحقة تحليلًا أكثر تفصيلًا لخوارزمية MultiFit، وأثبتت أن نسبة تقريبها لا تتجاوز 6/5 = 1.2 ، ^{[ 2 ]} ثم لاحقًا، لا تتجاوز 13/11 ≈ 1.182 . ^{[ 3 ]} أغفل البرهان الأصلي بعض الحالات؛ ^{[ 4 ]} وقدّم برهانًا كاملًا وأبسط. لا يمكن تحسين نسبة 13/11: انظر الحد الأدنى أدناه. ^{[ 2 ]}

بالنسبة لـ n = 4 : يوضح ما يلي ^{[ 5 ] أن}${\displaystyle r_{n}\geq 20/17}$وهو أمر ضيق. المدخلات هي 9، 7، 6، 5، 5، 4، 4، 4، 4، 4، 4، 4، 4. يمكن تعبئتها في 4 صناديق سعة كل منها 17 كما يلي:

• 9، 4، 4
• 7، 6، 4
• 5، 4، 4، 4
• 5، 4، 4، 4

لكن إذا قمنا بتشغيل FFD بسعة حاوية أقل من 20، فإن الحاويات الممتلئة ستكون كالتالي:

• 9.7 [4 لا يناسب]
• 6،5،5 [4 لا يناسب]
• 4,4,4,4 [الرقم 4 لا يناسب]
• 4,4,4,4
• 4

لاحظ أن مجموع كل خانة من الخانات الأربع الأولى هو 16، لذا لا يمكننا وضع 4 أخرى داخلها. وبالتالي، فإن 4 خانات غير كافية.

بالنسبة لـ n = 13 : يوضح ما يلي ^{[ 2 ] أن}${\displaystyle r_{n}\geq 13/11}$وهو أمر ضيق. يمكن تعبئة المدخلات في 13 صندوقًا بسعة 66 على النحو التالي:

• 40،13،13 {8 مرات}
• 25،25،16 {3 مرات}
• 25، 24، 17 {مرتين}

لكن إذا قمنا بتشغيل FFD بسعة خانات أصغر من 66*13/11 = 78، فإن الخانات الممتلئة هي:

• 40.25 {8 مرات}
• 24، 24، 17
• 17، 16، 16، 16
• 13، 13، 13، 13، 13 {3 مرات}
• 13

لاحظ أن مجموع كل خانة من الخانات الـ 13 الأولى هو 65، لذا لا يمكننا وضع 13 خانة أخرى داخلها. وبالتالي، فإن 13 خانة غير كافية.

يمكن أيضًا استخدام MultiFit في الإعداد الأكثر عمومية المسمى جدولة الآلات المتجانسة ، حيث قد تمتلك الآلات سرعات معالجة مختلفة. ^{[ 6 ]} عندما تكون هناك آلتان متجانستان، يكون عامل التقريب هو${\displaystyle {\sqrt {6}}/2}$عند دمج MultiFit مع خوارزمية LPT ، تتحسن النسبة إلى${\displaystyle {\sqrt {2}}+1/2}$.

يتمثل أحد الأهداف المزدوجة لتقليل أكبر مجموع (مدة الإنجاز) في زيادة أصغر مجموع. ويزعم ديورماير وفريزن ولانغستون أن برنامج MultiFit لا يمتلك عامل تقريب جيد لهذه المشكلة: ^{[ 7 ]}

في حل مشكلة زمن الإنجاز باستخدام خوارزمية MULTIFIT، من السهل إنشاء أمثلة لا يُستخدم فيها معالج واحد مطلقًا. يُعد هذا الحل مقبولًا لمشكلة زمن الإنجاز، ولكنه غير مقبول بتاتًا لمشكلتنا _{[لأن أصغر مجموع هو صفر]} . يمكن ابتكار تعديلات على خوارزمية MULTIFIT تكون أكثر ملاءمة لمشكلتنا، ولكننا لم نجد أي تعديل يُنتج حدًا أفضل في أسوأ الحالات من حد خوارزمية LPT .

الحدود العليا لـ${\displaystyle r_{n}}$يتم إثباتها بالتناقض. لأي عددين صحيحين p ≥ q، إذا${\displaystyle r_{n}>p/q}$إذن، يوجد مثال مضاد من الرتبة ( p / q )، يُعرَّف بأنه حالة S وعدد n من الخانات بحيث

• يمكن تعبئة S في n صندوقًا بسعة q ؛
• لا تستطيع خوارزمية FFD تعبئة S في n صندوقًا بسعة p .

إذا وُجد مثال مضاد كهذا، فإنه يوجد أيضًا مثال مضاد أدنى (p/q) ، وهو مثال مضاد ( p / q ) يحتوي على أقل عدد من العناصر في المجموعة S وأقل عدد من الصناديق n . في المثال المضاد الأدنى (p/q) ، تقوم خوارزمية FFD بتعبئة جميع العناصر في المجموعة S باستثناء العنصر الأخير (الأصغر) في n صندوقًا بسعة p . بالنظر إلى المثال المضاد الأدنى (p/q) ، نرمز بـ P₁ _, ..., Pₙ _إلى التعبئة (غير الكاملة) لخوارزمية FFD في هذه الصناديق n ذات السعة p ، وبـ _Pₙ₊₁ إلى الصندوق الذي يحتوي على العنصر الأصغر، وبـ Q₁ _, ..., Qₙ _إلى التعبئة المثلى (الكاملة) في n صندوقًا بسعة q . يمكن إثبات الليمات التالية:

• لا يوجد اتحاد لمجموعات فرعية من k من المجموعة {Q1 _,..., Qn _} يهيمن عليه اتحاد لمجموعات فرعية من k من المجموعة {P1 _,..., Pn ₊₁ } ("يُقصد بـ "مهيمن" أن كل عنصر في المجموعة الفرعية المهيمنة يُقابله عنصر أكبر منه بشكل طفيف في المجموعة الفرعية المهيمنة). وإلا، يُمكننا الحصول على مثال مضاد أصغر كما يلي: [1] حذف جميع العناصر في Pi _. من الواضح أن تعبئة FFD غير المكتملة تحتاج الآن إلى n - k خانة، ولا يزال أصغر عنصر (أو خانة كاملة) غير مُعبأ. [2] في التعبئة المثلى Qi _، يتم تبديل كل عنصر مع العنصر المهيمن عليه. الآن، المجموعات الفرعية k _{من Qi} أكبر (ربما أكبر من q )، لكن جميع المجموعات الفرعية الأخرى n - k أصغر (على وجه الخصوص، q على الأكثر ). لذلك، بعد حذف جميع العناصر في _Pi ، يُمكن تعبئة العناصر المتبقية في n - k خانة على الأكثر بحجم q .
• تحتوي كل مجموعة من المجموعات Q1 _{، ...،} Qn على 3 عناصر على الأقل. وإلا _، لكانت لدينا حالة هيمنة، وبحسب اللمة السابقة، لكان بإمكاننا الحصول على مثال مضاد أصغر. وذلك لأن: [أ] كل مجموعة Qi _تحتوي على عنصر واحد تهيمن عليها المجموعة Pj _التي تحتوي على ذلك العنصر؛ [ب] لكل مجموعة Qi _تحتوي على عنصرين x و y ، إذا كان كل من x و y ينتميان إلى نفس المجموعة Pj _، فإن Qi _تهيمن عليها هذه المجموعة Pj _؛ [ج] لنفترض أن x ≥ y، وأن x ينتمي إلى مجموعة Pj _، وأن y ينتمي إلى مجموعة Pk _على يمينها. هذا يعني أن y لا ينتمي إلى Pj _. ولكن x + y ≤ q. هذا يعني أن Pj _يجب أن تحتوي على عنصر z ≥ y. إذن، Qi _تهيمن عليها Pj _. [ د] لنفترض أن x ≥ y، وأن x ينتمي إلى مجموعة Pj _، وأن y ينتمي إلى مجموعة Pk _على يسارها. هذا يعني أنه يجب أن يكون هناك عنصر سابق z ≥ x. إذن، فإن Q _i يهيمن عليه P _k .
• تحتوي كل مجموعة من المجموعات P1 _{، ...،} Pn على عنصرين على الأقل. وذلك لأنه إذا احتوت إحدى المجموعات P1 _على عنصر واحد فقط، فهذا يعني أن العنصر الأخير (الأصغر) لا يتسع لها. وهذا يعني أن هذا العنصر الوحيد يجب أن يكون منفردًا في مجموعة مثالية، مما يناقض اللمة السابقة.
• لنفترض أن s هو حجم أصغر عنصر. إذن${\displaystyle s>{\frac {n}{n-1}}(pq)}$البرهان : بما أن s لا تتناسب مع الحزم n الأولى ، فإننا نحصل على${\displaystyle sum(P_{i})+s>p}$، لذا${\displaystyle \sum _{i=1}^{n}sum(P_{i})+n\cdot s>n\cdot p}$من ناحية أخرى، بما أن جميع العناصر تتناسب مع n صندوقًا بسعة q ، فإننا نحصل على${\displaystyle \sum _{i=1}^{n}sum(P_{i})+s\leq n\cdot q}$بطرح المتباينات نحصل على${\displaystyle s>{\frac {n}{n-1}}(pq)}$.
• حجم كل عنصر هو على الأكثر${\displaystyle q-2s}$وذلك لأن هناك ما لا يقل عن 3 عناصر في كل صندوق مثالي (بسعة q ).
• مجموع العناصر في كل صندوق P1 _{، ...،} Pn أكبر _من${\displaystyle ps}$وإلا فبإمكاننا إضافة أصغر عنصر.

انطلاقاً من اللمات المذكورة أعلاه، من الممكن بالفعل إثبات حد أعلى غير دقيق${\displaystyle r_{n}\leq 5/4=1.25}$البرهان . ليكن S ، n مثالًا مضادًا مصغرًا من النوع (5/4). تشير الليمات السابقة إلى أن -

• ${\displaystyle s>{\frac {n}{n-1}}(5-4)>1}$بما أن السعة المثلى هي 4، فلا يمكن لأي صندوق مثالي أن يحتوي على 4 عناصر أو أكثر. لذلك، يجب أن يحتوي كل صندوق مثالي على 3 عناصر على الأكثر، وعدد العناصر هو 3n على الأكثر .
• حجم كل عنصر هو على الأكثر${\displaystyle 4-2s}$وحجم كل صندوق من صناديق FFD أكبر من${\displaystyle 5-s}$إذا احتوت إحدى صناديق FFD على عنصرين فقط، فسيكون مجموعها على الأكثر${\displaystyle 8-4s=5+(3-3s)-s<5-s}$لذا، يجب أن يحتوي كل صندوق من صناديق FFD على 3 عناصر على الأقل. لكن هذا يعني أن FFD ينتج عنه n صندوقًا بالضبط - وهو تناقض.

لإثبات حدود أدق، يلزم إلقاء نظرة فاحصة على تعبئة FFD للمثال المضاد الأدنى ( p / q ). تُسمى العناصر وحاويات FFD P1 _، ...، Pn _{كما يلي:}

• العنصر العادي هو عنصر يُضاف إلى صندوق P _i قبل فتح الصندوق التالي P _{i+1 . وبعبارة أخرى، العنصر العادي هو عنصر في P i} لا يقل حجمه عن حجم أي عنصر في أي صندوق P _j، حيث j > i .
• العنصر الاحتياطي هو عنصر يُضاف إلى صندوق P _i بعد فتح الصندوق التالي P _{i+1 . وبعبارة أخرى، العنصر الاحتياطي هو عنصر في P i} أصغر من أكبر عنصر في P _i+1 .
• الحاوية العادية من نوع k هي حاوية تحتوي على k من العناصر العادية ولا تحتوي على عناصر احتياطية.
• صندوق k الاحتياطي هو صندوق يحتوي على k من العناصر العادية وبعض العناصر الاحتياطية.

تترتب اللمات التالية مباشرة من هذه التعريفات وعملية FFD.

• إذا كان _k1 < k2 ، فإن جميع الصناديق التي _{تحتوي على} k1 تقع على يسار جميع الصناديق التي _{تحتوي على} k2 . وذلك لأن جميع الصناديق لها نفس السعة، لذا إذا كانت هناك عناصر أكثر انتظامًا تتسع في صندوق ما، فيجب أن تكون هذه العناصر أصغر حجمًا، وبالتالي يجب تخصيصها لاحقًا.
• إذا كانت P _{i عبارة عن مجموعة} من k خانة، فإن مجموع العناصر k المنتظمة في P _i يكون أكبر من${\displaystyle {\frac {k}{k+1}}\cdot p}$وإلا فإنه يمكننا إضافة عنصر آخر قبل فتح صندوق جديد.
• إذا كان كل من P _i و P _{i+1 عبارة عن} k خانة، فإن مجموع العناصر العادية k في P _i يكون على الأقل بنفس حجمها في P _i+1 (وذلك لأن العناصر مرتبة حسب تناقص الحجم).
• تقع جميع صناديق التخزين العادية (k- bins) على يسار صناديق التخزين الاحتياطية (k -bins). والسبب في ذلك هو أن جميع الصناديق لها نفس السعة، لذا إذا اتسع صندوق واحد لعدد أكبر من العناصر الاحتياطية، فيجب أن تكون هذه العناصر أصغر حجمًا، وبالتالي يجب تخصيصها لاحقًا.

في مثال مضاد بسيط، لا توجد صناديق منتظمة تحتوي على عنصر واحد (لأن كل صندوق يحتوي على عنصرين على الأقل)، لذلك وفقًا للنتائج المذكورة أعلاه، يتم ترتيب صناديق FFD P ₁ ، ...، P _{n حسب النوع:}

• صفر أو أكثر من صناديق الاحتياط ذات القيمة 1؛
• ثم، صفر أو أكثر من الصناديق العادية ذات الصندوقين؛
• ثم، صفر أو أكثر من صناديق الاحتياط الثنائية؛
• ثم، صفر أو أكثر من الصناديق العادية ذات الثلاث خانات؛
• ثم، صفر أو أكثر من صناديق الاحتياط الثلاثية؛
• وهكذا دواليك.

الحد الأعلى${\displaystyle r_{n}\leq 1.22}$^{[ 1 ]} يُثبت بافتراض مثال مضاد أدنى (122/100). يُعطى كل عنصروزنًابناءً على حجمه ومكانه في حاوية التعبئة FFD. تُحدد الأوزان بحيث يكون الوزن الإجمالي في كل حاوية FFD على الأقلx، ويكون الوزن الإجمالي في كل حاوية مثالية تقريبًا على الأكثرx(لقيمةx). هذا يعني أن عدد حاويات FFD هو على الأكثر عدد الحاويات المثالية، وهو ما يتناقض مع افتراض أنه مثال مضاد.

بناءً على اللمات المذكورة أعلاه، نعلم أن:

• حجم أصغر عنصر يحقق الشرط s > p - q = 22، لذا فإن s = 22 + D لبعض D > 0.
• تحتوي كل حاوية مثالية على 4 عناصر على الأكثر (الجزء السفلي (100/22))، وتحتوي كل حاوية FFD على 5 عناصر على الأكثر (الجزء السفلي (122/22)).
• حجم كل عنصر هو على الأكثر q -2 s = 56-2 D.
• يكون المجموع في كل خانة من خانات FFD أكبر من p - s = 100- D.
• لا توجد صناديق ذات 1 عنصر، لأنه في الصندوق ذي 1 عنصر، يجب أن يكون حجم العنصر العادي على الأقل p /2=61، بينما هنا حجم كل عنصر أقل من 56.

إذا كانت D > 4، فإن حجم كل عنصر أكبر من 26، لذا يجب أن يحتوي كل صندوق مثالي (بسعة 100) على 3 عناصر على الأكثر. كل عنصر أصغر من 56 - 2D ، ومجموع كل صندوق FFD أكبر من 100 - D ، لذا يجب أن يحتوي كل صندوق FFD على 3 عناصر على الأقل. بالتالي، يوجد على الأكثر n صندوق FFD - وهذا تناقض. لذا، من الآن فصاعدًا، نفترض أن D ≤ 4. يتم تحديد أنواع العناصر وأوزانها كما يلي.

• يحتوي كل صندوق عادي ثنائي، باستثناء الصندوق الأخير ربما، على عنصرين بحجم أكبر من (100 - D )/2 لكل منهما. تُسمى جميع هذه العناصر من النوع X2 _، ويُخصص لها وزن يساوي (100 - D )/2. أما الصندوق العادي الثنائي الأخير فهو حالة خاصة: إذا كان حجم كلا العنصرين فيه أكبر من (100 - D )/2، فإنهما يُصنفان أيضًا ضمن النوع X2 _؛ وإلا، يُطلق عليهما النوع Z ، ويكون وزنهما مساويًا لحجمهما.
• العنصران العاديان في كل صندوق احتياطي ثنائي له حجم إجمالي أكبر من 2*122/3؛ ويطلق عليهما النوع Y ₂ ، ووزنهما يساوي حجمهما مطروحًا منه D.
• تحتوي كل حاوية ثلاثية منتظمة، باستثناء الحاوية الأخيرة ربما، على ثلاثة عناصر يزيد حجم كل منها عن (100 - D )/3. تُسمى جميع هذه العناصر من النوع X ₃ ، ويُخصص لها وزن يساوي (100 - D )/3. أما الحاوية الثلاثية المنتظمة الأخيرة فهي حالة خاصة: إذا كان حجم جميع العناصر فيها أكبر من (100 - D )/3، فإنها تُصنف أيضاً ضمن النوع X ₃ ؛ وإلا، تُسمى من النوع Z ويكون وزنها مساوياً لحجمها.
• العناصر الثلاثة العادية في كل صندوق احتياطي ثلاثي لها حجم إجمالي أكبر من 3*122/4؛ وتسمى من النوع Y ₃ ، ووزنها يساوي حجمها مطروحًا منه D.
• تحتوي كل حاوية رباعية منتظمة، باستثناء الحاوية الأخيرة ربما، على أربعة عناصر يزيد حجم كل منها عن (100 - D )/4. تُسمى جميع هذه العناصر من النوع X- ₄ ، ويُخصص لها وزن يساوي (100 - D )/4. أما الحاوية الرباعية المنتظمة الأخيرة فهي حالة خاصة: إذا كان حجم جميع العناصر فيها أكبر من (100 - D )/4، فإنها تُصنف أيضاً ضمن النوع X- ₄ ؛ وإلا، تُسمى من النوع Z، ويكون وزنها مساوياً لحجمها.
• تُسمى العناصر المتبقية (بما في ذلك جميع العناصر الاحتياطية في صناديق الاحتياط الثنائية والثلاثية، وجميع صناديق الاحتياط الرباعية، وجميع صناديق العناصر الخمسة الأخرى) بالنوع X ₅ ، ووزنها يساوي 22 (إذا كان D ≤ 12/5) أو (100 - D )/4 (في غير ذلك). تم حساب العتبة 12/5 بحيث يكون الوزن دائمًا على الأكثر 22 + D ، أي أن الوزن دائمًا أصغر من الحجم.

لاحظ أن وزن كل عنصر لا يتجاوز حجمه (يمكن اعتبار الوزن بمثابة الحجم بعد تقريبه إلى أقرب عدد صحيح أصغر). ومع ذلك، فإن الوزن الإجمالي للعناصر في كل صندوق من صناديق FFD لا يقل عن 100- D .

• بالنسبة للحاويات العادية ذات 2 حاوية، والحاويات العادية ذات 3 حاويات، والحاويات العادية ذات 4 حاويات:
  • أما بالنسبة لغير الأخيرين، فهذا فوري.
  • تحتوي هذه الصناديق الأخيرة على عناصر من النوع Z فقط، والتي يساوي وزنها حجمها، لذا فإن الوزن الإجمالي لهذه الصناديق يساوي حجمها الإجمالي، وهو أكثر من 100- D.
• تحتوي صناديق الاحتياط الثنائية على عنصرين من النوع Y ₂ بوزن إجمالي أكبر من 2*122/3-2 D ، بالإضافة إلى عنصر واحد على الأقل من النوع X ₅ بوزن لا يقل عن 22 (إذا كان D ≤ 12/5) أو (100- D )/4 (في غير ذلك). في كلتا الحالتين ، يكون الوزن الإجمالي أكبر من 100- D.
• تحتوي صناديق الاحتياط الثلاثية على ثلاثة عناصر من النوع Y ₃ بوزن إجمالي أكبر من 3*122/4-3 D ، بالإضافة إلى عنصر واحد على الأقل من النوع X ₅ بوزن لا يقل عن 22. لذا فإن الوزن الإجمالي أكبر من 3*122/4+22-3 D = 113.5-3 D ≥ 105.5- D > 100- D ، لأن D≤ 4.
• تحتوي الصناديق المكونة من 5 عناصر على 5 عناصر بحجم لا يقل عن 22+ D ووزن لا يقل عن 22، لذا فإن وزنها الإجمالي من الواضح أنه أكثر من 100- D.

يبلغ الوزن الإجمالي للعناصر في الصناديق الأكثر مثالية 100- د على الأكثر :

• يتضح هذا بالنسبة لأي صندوق مثالي يحتوي على عنصر من النوع -Y ₂ أو عنصر من النوع -Y ₃ ، لأن وزنها هو حجمها مطروحًا منه D ، وأوزان العناصر الأخرى هي على الأكثر حجمها، والحجم الإجمالي للصندوق المثالي هو على الأكثر 100.
• بالنسبة للصناديق المثلى التي تحتوي فقط على عناصر من النوع -X ₂ ، والنوع -X ₃ ، والنوع -X ₄ ، والنوع -X ₅ ، فمن الممكن التحقق من جميع التكوينات الممكنة (جميع التركيبات التي تتناسب مع صندوق مثالي بحجم 100)، والتحقق من أن الوزن الإجمالي في كل تكوين لا يتجاوز 100- D.
• قد يكون للصناديق المثلى التي تحتوي على عناصر من النوع Z وزن إجمالي أكبر من 100 - D. وبما أن الوزن الإجمالي لا يتجاوز 100، فإن هناك "وزنًا زائدًا" لا يتجاوز D لكل صندوق من هذه الصناديق. ومع ذلك، فإن عدد عناصر النوع Z محدود.
  • إذا كانت قيمة D أكبر من 12/5، فإن عدد العناصر من النوع Z لا يتجاوز 5 عناصر (عنصران في آخر صندوق ثنائي منتظم، و3 عناصر في آخر صندوق ثلاثي منتظم؛ أما العناصر في آخر صندوق رباعي منتظم فهي جميعها من النوع X ₎ . وبالتالي، فإن الوزن الزائد لا يتجاوز 5D . وبمقارنة الوزن الإجمالي للصناديق المُعدّلة (FFD) مع الصناديق المُثلى، نحصل على s < 5D ≤ 20 < 22، وهو تناقض.
  • بخلاف ذلك، يوجد على الأكثر 9 عناصر من النوع Z (2+3+4). لذا، فإن الوزن الزائد لا يتجاوز 9 D. وبمقارنة الوزن الإجمالي لـ FFD مع الصناديق المثلى، نحصل على s < 9 D ≤ 108/5 < 22، وهو تناقض.

الحد الأعلى${\displaystyle r_{n}\leq 13/11\approx 1.182}$^{[ 3 ]} يتم إثباته بافتراض مثال مضاد أدنى ((120-3d)/100)، مع بعضd<20/33، واستنباط تناقض.

إليك مثال. ^{[ 5 ] : مثال 5.2} لنفترض أن هناك أربعة وكلاء، ولديهم تقييمات من نوعين:

يمكن لكلا النوعين تقسيم المهام إلى 4 أجزاء بقيمة إجمالية قدرها 75. النوع أ:

• 51، 12، 12
• 27.5، 27.5، 10، 10
• 27.5، 27.5، 10، 10
• 25، 10، 10، 10، 10، 10

النوع ب:

• 51، 24
• 27.5، 27.5، 20
• 27.5، 27.5، 20
• 8.33 {9 مرات}

إذا كان جميع العملاء الأربعة من نفس النوع، فإن خوارزمية FFD ذات العتبة 75 تملأ الخانات الأربع المثلى. ولكن لنفترض وجود عميل واحد من النوع B، والآخرين من النوع A. في الجولة الأولى، يأخذ العميل من النوع B الحزمة 51، 24 (لا يمكن للعملاء الآخرين أخذها لأن قيمهم هي 51، 25 ومجموعها أكبر من 75). في الجولات التالية، تُملأ الحزم التالية للعملاء من النوع A:

• 27.5، 27.5، 12 [المجموع هو 67 - لا يوجد مكان لـ 10 أخرى]
• 27.5، 27.5، 12 [المجموع هو 67 - لا يوجد مكان لـ 10 أخرى]
• 10، 10، 10، 10، 10، 10، 10 [المجموع 70 - لا يوجد مكان لـ 10 أخرى]

لذا فإن المهمتين الأخيرتين لا تزالان دون تخصيص.

باستخدام حساب عتبة أكثر تعقيدًا، يمكن ضمان حصول كل وكيل على 11/9 ≈ 1.22 كحد أقصى من قيمته المثلى إذا كانت القيمة المثلى معروفة، و5/4 ≈ 1.25 كحد أقصى من قيمته المثلى (باستخدام خوارزمية زمنية متعددة الحدود) إذا كانت القيمة المثلى غير معروفة. ^{[ 5 ]}

باستخدام حجج أكثر تفصيلاً، من الممكن ضمان نفس نسبة MultiFit لكل وكيل. ^{[ 9 ]}