Abstract
Optimization of a discrete event systems including (non)linear cost in local states is mainly solved either by heuristic search methods or mathematical programming. In this paper the second approach is further elaborated, including guarantees on both optimal performance and logical correctness. An integrated algorithm is developed utilizing both Operations Research (OR) and Constraint Programming (CP). The majority of integrated approaches have up till now focused on solving linear problems. In this paper we use our integrated algorithm to optimize discrete event systems with nonlinear cost and logical constraints. We present a straightforward method to incorporate OR functionality into an existing CP algorithm such that it can process nonlinear expressions, otherwise too complex for the CP algorithm to handle. Evaluation of the algorithm's performance is done by comparison to that of state of the art Mixed Integer Nonlinear Programming (MINLP) methods. The benchmark shows that our integrated approach finds the optimal solution in roughly the same time as existing MINLP methods. However, when also proof of optimality is required, the integrated algorithm outperforms the best MINLP algorithm by roughly a factor of ten
چکیده
بهینه‌سازی سیستم‌های رویداد گسسته که شامل هزینه‌ای (غیر) خطی در وضعیت‌های محلی می‌باشد را می‌توان به‌وسیله‌ی متدهای جستجوی هیروستیک و یا برنامه‌نویسی ریاضی حل کرد. در این مقاله قصد داریم روش دوم را استفاده کنیم که می‌تواند کارائی بهینه و صحت منطقی را تضمین سازد. یک الگوریتم ادغام یافته نیز با استفاده از پژوهش عملیاتی (OR) و برنامه‌نویسی محدودیت (cp) توسعه‌یافته است اغلب روش‌های ادغام یافته‌ای که تا به امروز پیشنهادشده‌اند بر روی حل مسائل خطی متمرکز بوده‌اند. در این مقاله، از الگوریتم ادغام یافته‌مان برای بهینه‌سازی سیستم‌های رویداد گسسته‌ای که با هزینه‌ی خطی همراه می‌باشند و محدودیت‌های منطقی استفاده می‌کنیم. متد آسانی را برای بکار گیری عملکرد OR در داخل الگوریتم CP ارائه می‌دهیم به‌طوری‌که بتواند عبارت‌های غیرخطی را پردازش کند، چراکه انجام این کار برای الگوریتم CP بسیار پیچیده است. ارزیابی کارائی الگوریتم نیز به‌وسیله‌ی مقایسه‌ی روش‌های برنامه‌نویسی خطی صحیح ترکیبی (MINLP) صورت گرفته است. بنچ مارک‌ها نشان می‌دهد که روش ادغام یافته‌ی ما یک‌راه حل بهینه‌ای مشابه با متدهای MINLP می‌باشد. اگرچه درزمانی که اثبات بهینگی نیاز باشد، الگوریتم ادغام یافته‌ی ما عملکرد بهتری نسبت به بهترین الگوریتم MINLP (تقریباٌ 10 برابر) دارد.
1- مقدمه
یافتن یک دنباله‌ی بهینه‌ای از رویدادها و زمان‌بندی رویداد برای یک سیستم رویداد گسسته DES) )به‌خودی‌خود یک مسئله‌ی مشکل است. درصورتی‌که یک عددی از چنین DES هایی به رویدادهای مشترک متصل بوده و مورد سنکرون سازی قرار گیرد، وظیفه‌ی انتخاب یک‌زمان‌بندی بهینه از این رویدادها نیز امری مشکل‌تر خواهد شد. یک DES زمان‌بندی‌شده، که شامل هزینه‌ی خطی می‌باشد را می‌توان به یک برنامه‌ی جدا سازنده مبدل کرده که ارتباط نزدیکی با برنامه‌نویسی محدودیت و ریاضی دارد..