کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
435499 689911 2009 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Parallel-machine scheduling of simple linear deteriorating jobs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Parallel-machine scheduling of simple linear deteriorating jobs
چکیده انگلیسی

We consider parallel-machine scheduling problems in which the processing time of a job is a simple linear increasing function of its starting time. The objectives are to minimize the makespan, total machine load, and total completion time. We show that all the problems are strongly NP-hard with an arbitrary number of machines and NP-hard in the ordinary sense with a fixed number of machines. For the former two problems, we prove that there exists no polynomial time approximation algorithm with a constant worst-case bound when the number of machines is arbitrary unless P=NP. When the number of machines is fixed, we propose two similar fully polynomial-time approximation schemes for the former two problems.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 410, Issues 38–40, 6 September 2009, Pages 3761-3768