Lösungsverfahren für das Standardproblem eindimensionalen Zuschneidens

نویسنده با مسئله استاندارد برش تک بعدی سر و کار دارد، و در اینجا به ویژه با سؤالاتی در مورد سودمندی و ارزیابی روش های حل برای هر دو حالت آرام و صحیح می پردازد. بر اساس احتمالات جایگزین مدل‌سازی و بهره‌برداری از معادل‌سازی با مسئله بسته‌بندی bin، چندین روش اکتشافی تجزیه پیشنهاد شده‌اند که از طریق استفاده ترکیبی از آنها نویسنده موفق به تعیین یک راه‌حل عدد صحیح بهینه برای 11959 از 12000 نمونه مسئله در نظر گرفته شده است. . علاوه بر این، روش تولید ستون گیلمور و Gomory، که بخش اساسی این اکتشافات تجزیه است، برای اولین بار با چنین جزئیاتی تحلیل و مورد بحث قرار می گیرد. p>

Der Verfasser setzt sich mit dem Standardproblem eindimensionalen Zuschneidens auseinander, und hier im besonderen mit Fragen der Vorteilhaftigkeit und der Beurteilung von Lösungsverfahren sowohl für den relaxierten als auch für den ganzzahligen Fall. Ausgehend von alternativen Möglichkeiten der Modellierung und der Ausnutzung der Äquivalenz zum bekannteren Bin Packing Problem werden mehrere Dekompositionsheuristiken vorgeschlagen, durch deren kombinierten Einsatz es dem Verfasser gelungen ist, für 11.959 der betrachteten 12.000 Probleminstanzen eine optimale, ganzzahlige Lösung zu bestimmen. Des Weiteren wird das spaltenerzeugende Verfahren von Gilmore und Gomory, das wesentlicher Bestandteil dieser Dekompositionsheuristiken ist, erstmalig in derartiger Ausführlichkeit analysiert und diskutiert.