کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
428945 686973 2013 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The complexity of two supply chain scheduling problems
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
The complexity of two supply chain scheduling problems
چکیده انگلیسی


• We consider an assembling manufacture system where several suppliers provide component parts to a manufacturer.
• We show that the suppliersʼ problem of minimizing the total weighted number of tardy parts is unary NP-hard.
• The suppliersʼ problem of minimizing the total late work of parts is also proved to be unary NP-hard.

We consider an assembling manufacture system where several suppliers provide component parts to a manufacturer, who assembles products from all the supplied component parts. The delivery time of any product is the maximum of the suppliersʼ delivery time of the parts needed for that product. We assume that the final stage is non-bottleneck. Chen and Hall (2007) show that the suppliersʼ problem of minimizing the total weighted number of tardy parts is binary (i.e., weakly) NP-hard and left open whether it is unary (i.e., strongly) NP-hard. In this paper we resolve this open problem by showing that it is unary NP-hard. Moreover we show that the suppliersʼ problem of minimizing the total late work of parts is also unary NP-hard.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 113, Issue 17, 30 August 2013, Pages 609–612
نویسندگان
, , ,