کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
427089 686442 2016 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Complexity of problem TF2|v=1,c=2|CmaxTF2|v=1,c=2|Cmax
ترجمه فارسی عنوان
پیچیدگی مسئله TF2 | v = 1، c = 2 | CmaxTF2 | v = 1، c = 2 | Cmax
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی


• We study a flow shop scheduling problem with two machines and one transporter.
• Each time, the transporter can carry at most 2 jobs between two machines.
• We prove the problem is strongly NP-hard in by 4-partition problem.

In this paper, we study a flow shop scheduling problem with an interstage transporter, in which there are a set of n jobs, two machines A and B, and one transporter located at machine A initially. Each job has to be processed on machine A first, then transported by a vehicle to machine B, finally processed on machine B. The interstage transporter can carry at most two jobs between the machines at a time. When the transporter carries items from machine A to machine B, it will take time τ; when it is back from machine B to machine A, it will take zero time. And there is an unlimited buffer on each machine to store jobs that will be processed. The objective is to minimize the completion time on machine B. The complexity of the problem is open in Journal of Scheduling 2001 [5]. We prove the problem is NP-hard in the strong sense by 4-partition problem.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 116, Issue 1, January 2016, Pages 65–69
نویسندگان
, , , , ,