کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
479244 1445977 2016 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Scheduling under linear constraints
ترجمه فارسی عنوان
زمان‌بندی تحت محدودیت‌های خطی
کلمات کلیدی
فهرست مطالب مقاله
چکیده

کلمات کلیدی

1.مقدمه

جدول 1. مثالی برای مسئله تولید صنعتی.

جدول 2. مالی برای مسئله انتخاب رسانه‌های تبلیغاتی.

جدول 3.  خلاصه‌ای از نتایج

2. توضیح مسئله

3. ماشین واحد یا محدودیت تکی 

3.1 ماشین واحد

4. تعداد ماشین‌ها ثابت (m ≥2)

4.1 تعداد محدودیت‌ها ثابت (k ≥2)

4.2 تعداد محدودیت دلخواه (k ≥2)

5. تعداد دلخواه ماشین (m ≥2)

5.1  دو محدودیت (k = 2)

جدول 4. مقادیر K و نسبت تقریبی برای k و m متفاوت.

6. نتیجه‌گیری 

 

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


• We study scheduling problems where the processing times are also decision variables.
• We consider the case where the processing times must satisfy some linear constraints.
• We investigate the computational complexity of such problems under various settings.
• We propose algorithms/approximation algorithms for such problems.
• This seemingly harder problem could be easier than the NP-Hard scheduling problem.

We introduce a parallel machine scheduling problem in which the processing times of jobs are not given in advance but are determined by a system of linear constraints. The objective is to minimize the makespan, i.e., the maximum job completion time among all feasible choices. This novel problem is motivated by various real-world application scenarios. We discuss the computational complexity and algorithms for various settings of this problem. In particular, we show that if there is only one machine with an arbitrary number of linear constraints, or there is an arbitrary number of machines with no more than two linear constraints, or both the number of machines and the number of linear constraints are fixed constants, then the problem is polynomial-time solvable via solving a series of linear programming problems. If both the number of machines and the number of constraints are inputs of the problem instance, then the problem is NP-Hard. We further propose several approximation algorithms for the latter case.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 253, Issue 2, 1 September 2016, Pages 290–297
نویسندگان
, , ,