کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
1705232 | 1012426 | 2015 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Scheduling linearly shortening jobs under precedence constraints
ترجمه فارسی عنوان
برنامه ریزی شغل خطی را کوتاه تر می کند با محدودیت های اولویت
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
زمان بندی وابسته به زمان، شغل کوتاه محدودیت های قضیه، الگوریتم چندجمله ای
موضوعات مرتبط
مهندسی و علوم پایه
سایر رشته های مهندسی
مکانیک محاسباتی
چکیده انگلیسی
We consider the problem of scheduling a set of dependent jobs on a single machine with the maximum completion time criterion. The processing time of each job is variable and decreases linearly with respect to the starting time of the job. Applying a uniform approach based on the calculation of ratios of expressions that describe total processing times of chains of jobs, we show basic properties of the problem. On the basis of these properties, we prove that if precedence constraints among jobs are in the form of a set of chains, a tree, a forest or a series–parallel digraph, the problem can be solved in O(n log n) time, where n denotes the number of the jobs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Mathematical Modelling - Volume 35, Issue 4, April 2011, Pages 2005–2015
Journal: Applied Mathematical Modelling - Volume 35, Issue 4, April 2011, Pages 2005–2015
نویسندگان
Stanisław Gawiejnowicz, Tsung-Chyan Lai, Ming-Huang Chiang,