مساله تسریع در کوتاهترین مسیرهای متغیر زمانی با زمانهای انتظار دلخواه

Abstract

مسائل شبکه جریان، شاخه حیاتی در تحقیق در عملیات هستند. این مسائل به حالتهای متغیر زمانی و ایستا طبقه‌بندی می‌گردند. مسائل شبکه جریان در کاربردهای واقعی، متغیر زمانی هستند، زیرا هر جریان برای عبور از یک کمان باید یک مقدار زمان داده شده را اتخاذ کند، همچنین همه پارامترها در شبکه می توانند به جریان وابسته باشد. در این مقاله، مساله تسریع روی کوتاهترین مسیر متغیر زمانی مطالعه می گردد. در ابتدا، ما کوتاهترین مسیر متغیر زمانی را توضیح می‌دهیم. این مساله یافتن مسیرهایی از یک راس مشخص شده (که مبدا نامیده می شود) به سایر رئوس است به‌طوریکه هزینه این مسیر کمترین گردد و مجموع زمان‌های عبور و زمان‌های انتظار حداکثر T شود، که T یک عدد صحیح مثبت داده شده است. سپس مساله تسریع برای یک مساله کوتاهترین مسیر شرح داده شده است.