Job-Shop-Scheduling: Planung durch probabilistische lokale Suchverfahren

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

برای برنامه‌ریزی فرآیند در تولید کارگاهی، به‌اصطلاح زمان‌بندی کار فروشگاه، Jukka Siedentopf روش‌های مختلف جستجوی محلی مبتنی بر آستانه را بر اساس یک الگوی روش مدولار بررسی می‌کند. او در مقایسه‌های گسترده اثربخشی و کارایی، تسلط روشی را نشان می‌دهد که می‌توان آن را به راحتی و مستقل از مسئله پارامترسازی کرد. این نیاز اساسی برای استفاده انعطاف پذیر در محیط های عملی را برآورده می کند. در نهایت، نویسنده رفتار همگرایی روش را با استفاده از نظریه مارکوف بررسی می کند.

Metaheuristiken, insbesondere Verfahren der lokalen Suche, werden mit zunehmendem Erfolg zur approximativen Lösung kombinatorischer Optimierungsprobleme eingesetzt. Bei der Konzeption operativer Systeme erweist sich die Vielfalt existierender Verfahrensvarianten jedoch oftmals als Hindernis, denn es gibt keine verallgemeinerbaren Handlungsempfehlungen zur Auswahl geeigneter Basisverfahren und zur probleminstanzunabhängigen Parametrisierung dieser Verfahren.

Für die Ablaufplanung in der Werkstattfertigung, das sogenannte Job-Shop-Scheduling, untersucht Jukka Siedentopf auf der Basis einer modular aufgebauten Verfahrensschablone verschiedene schwellenwertbasierte lokale Suchverfahren. In umfangreichen Effektivitäts- und Effizienzvergleichen demonstriert er die Dominanz eines Verfahrens, das einfach und problemunabhängig parametrisierbar ist. Damit ist die Grundvoraussetzung für einen flexiblen Einsatz auch in praktischen Umgebungen erfüllt. Abschließend untersucht der Autor das Konvergenzverhalten des Verfahrens mit Hilfe der Markov-Theorie.