کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4952499 | 1442039 | 2016 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Semi-online scheduling on a single machine with unexpected breakdown
ترجمه فارسی عنوان
زمان بندی نیمه آنلاین بر روی یک دستگاه با شکست غیر منتظره
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
زمان بندی نیمه آنلاین، شکست غیرمنتظره، تحلیل رقابتی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In this paper, we consider a single machine scheduling problem where a breakdown period occurs in an online way. Two main objective functions are studied: the makespan and the maximum lateness. We propose two approximation algorithms for the makespan minimization for solving two variants of the problem: with different release dates or without release dates. We show that the competitive ratio of the two algorithms is 3/2 and that this bound is the best possible for the makespan minimization. For the maximum lateness minimization we propose a (1+2/2)â1.70-approximation algorithm capable to solve the problem with delivery times but no release dates. This ratio is tight for the proposed algorithm and allows us to establish a precise window for the best possible ratio, which belongs to [3/2,1+2/2]â[1.50,1.70].
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 646, 20 September 2016, Pages 40-48
Journal: Theoretical Computer Science - Volume 646, 20 September 2016, Pages 40-48
نویسندگان
Imed Kacem, Hans Kellerer,