ملیحه نیک سیرت - دانشگاه صنعتی امیرکبیر، دانشکده ریاضی و علوم کامپیوتر
صادق محمدپور - دانشگاه صنعتی امیرکبیر، دانشکده مهندسی برق

مسیله زمان بندی ناوگان چندپایانه ای MDVSP یکی از مسایل مهم در فرآیند مدیریت سیستم حمل ونقل است که هدف آن انجام سفرهای برنامه ریزی شده با استفاده بهینه از منابع موجود می باشد. در کاربردهای واقعی مسیله MDVSP، محدودیت های دیگری مانند محدودیت بودجه مطرح می شود. با توجه به اینکه بودجه اختصاص یافته، سوخت وسایل نقلیه و سایر فاکتورهایی که در بودجه اثرگذار هستند، محدود می باشد، در نظر گرفتن این محدودیت مهم به نظر می رسد. در این مقاله، یک مدل زمانبندی جدید برای مسیله زمان بندی ناوگان با در نظر گرفتن محدودیت بودجه پیشنهاد شده است. همچنین در زمینه پیچیدگی مسیله تحقیق شده است. در این راستا در این مقاله ثابت شده است که مسیله گسترش یافته زمانبندی ناوگان با محدودیت بودجه نه تنها NP - سخت است بلگه هیچ الگوریتم تقریبی زمان چندجمله ای با فاکتور تقریب ثابت برای این مسیله وجود ندارد.

مسیله زمانبندی ناوگان چندپایانه ای، محدودیت بودجه، الگوریتم تقریبی، پیچیدگی الگوریتم