Optimale Stauraumnutzung: Losungsverfahren zum zweidimensionalen homogenen Packproblem

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

Die Aufgabe, möglichst viele gleichdimensionierte Packungen auf einer rechteckigen Grundfläche anzuordnen, wird als zweidimensionales homogenes Packproblem bezeichnet. Die lagenweise Anordnung gleich großer Packungen in einem container, auf einer Palette oder einem anderen Ladungsträger sind ebenso praktische Umsetzungen von Lösungen des homogenen Packproblems wie die Entwicklung von Verpackungen z. B. für Kaffee, Kekse oder Pralines, um eine bessere Nutzung des Palettenstauraums zu erreichen. Eine bessere Nutzung des stauraums der eingesetzten Ladungsträger eröffnet ökonomische wie ökologische vorteile: Bei gleicher Produktmenge lassen sich die genutzten Lager- und Transportkapazitäten reduzieren. Auch aus theoretischer Sicht bietet dieses kombinatorische Problem einen besonderen Reiz. Zur Lösung praxisrelevanter Problemstellungen werden trotz der hohen Leistungsfähigkeit der Rechner keine exakten Verfahren eingesetzt: Die Rechenzeit ist zu groß. In der hier vorliegenden Monographie zeigt Gerd Naujoks, daß für nahezu alle praxisrelevanten Problemstellungen der Einsatz exakter Verfahren gar nicht notwendig ist, sofern die richtige Heuristik eingesetzt wird. Damit ist das Spannungsfeld dieser spannenden Arbeit skizziert: - Welche Verfahren zu Ermittlung von Obergrenzen für die Anzahl der auf der rechteckigen Grundfläche anzuordnenden Packungen sind heranzuziehen, um eine möglichst gute hinreichende Bedingung für die optimalität einer heuristisch ermittelten Anordnung einzusetzen ? Welche Heuristiken dominieren auf der Basis der Güte ihrer Anordnungen andere Heuristiken ? Welche Heuristiken generieren für bestimmte Problemklassen stets optimale Anordnungen ? - VI - Bislang gab es viele Problemstellungen, für die nur durch den Einsatz exakter Verfahren eine optimale Anordnung generiert bzw. der Optimalitätsnachweis für eine heuristisch ermittelte Anordnung geführt werden konnte.