Das Multiprocessor Scheduling-Problem mit reihenfolgeabhängigen Rüstzeiten: Heuristische Lösungsverfahren

مشکلات بارگذاری ماشین به طور گسترده برای چندین دهه مورد مطالعه قرار گرفته است. مشکل زمان‌بندی چند پردازنده با زمان‌های راه‌اندازی وابسته به توالی تا کنون تا حد زیادی نادیده گرفته شده است، علی‌رغم اهمیت زیادی که برای علم و عمل دارد، می‌توان به کیفیت راه‌حل، استحکام و زمان محاسباتی مورد نیاز دست یافت. بررسی ویژگی‌های فرآیند بر اساس تعداد زیادی نمونه مشکل با ویژگی‌های مختلف است که با کمک یک مولد مشکل جدید ایجاد می‌شوند. پیشرفت قابل توجهی نیز در مرزهای پایین مورد نیاز برای ارزیابی کیفیت راه حل انجام شده است.

Maschinenbelegungsprobleme werden seit Jahrzehnten intensiv untersucht. Dabei wurde das Multiprocessor Scheduling-Problem mit reihenfolgeabhängigen Rüstzeiten trotz seiner großen Bedeutung für Wissenschaft und Praxis bisher weitgehend vernachlässigt.

Jörg Heuer entwickelt für diese Problemstellung neue heuristische Lösungsverfahren, mit denen sich gegenüber den existierenden Heuristiken erhebliche Verbesserungen im Hinblick auf Lösungsqualität, Robustheit und erforderliche Rechenzeit erzielen lassen. Die Untersuchung der Verfahrenseigenschaften erfolgt anhand einer Vielzahl von Probleminstanzen mit unterschiedlichen Merkmalen, die mit Hilfe eines neu erstellten Problemgenerators erzeugt werden. Auch bei den Lower Bounds, die zur Beurteilung der Lösungsqualität erforderlich sind, werden wesentliche Fortschritte erzielt.