کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6875455 1441955 2018 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An approximation scheme for minimizing the makespan of the parallel identical multi-stage flow-shops
ترجمه فارسی عنوان
یک طرح تقریبی برای به حداقل رساندن مگاپن یک جریان چند مرحله ای موازی یکسان است
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
In the parallel k-stage flow-shops problem, we are given m identical k-stage flow-shops and a set of jobs. Each job can be processed by any one of the flow-shops but switching between flow-shops is not allowed. The objective is to minimize the makespan, which is the finishing time of the last job. This problem generalizes the classical parallel identical machine scheduling (where k=1) and the classical flow-shop scheduling (where m=1) problems, and thus it is NP-hard. We present a polynomial-time approximation scheme (PTAS) for the problem, when m and k are fixed constants. The key technique is to partition the jobs into big jobs and small jobs, enumerate over all feasible schedules for the big jobs, and handle the small jobs by solving a linear program and employing a “sliding” method. Such a technique has been used in the design of PTAS for several flow-shop scheduling variants. Our main contributions are the non-trivial application of this technique and a valid answer to the open question in the literature.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 734, 22 July 2018, Pages 24-31
نویسندگان
, , , ,