کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
478325 1446059 2013 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Outsourcing and scheduling for two-machine ordered flow shop scheduling problems
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
Outsourcing and scheduling for two-machine ordered flow shop scheduling problems
چکیده انگلیسی

This paper considers a two-machine ordered flow shop problem, where each job is processed through the in-house system or outsourced to a subcontractor. For in-house jobs, a schedule is constructed and its performance is measured by the makespan. Jobs processed by subcontractors require paying an outsourcing cost. The objective is to minimize the sum of the makespan and the total outsourcing cost. Since this problem is NP-hard, we present an approximation algorithm. Furthermore, we consider three special cases in which job j has a processing time requirement pj, and machine i a characteristic qi. The first case assumes the time job j occupies machine i is equal to the processing requirement divided by a characteristic value of machine i, that is, pj/qi. The second (third) case assumes that the time job j occupies machine i is equal to the maximum (minimum) of its processing requirement and a characteristic value of the machine, that is, max{pj, qi} (min{pj, qi}). We show that the first and the second cases are NP-hard and the third case is polynomially solvable.


► We consider a two-machine ordered flow shop problem with an outsourcing option.
► An approximation algorithm with the tight worst-case performance bound is presented.
► The special case with pj/qipj/qi is NP-hard.
► The special case with max{pj,qi}{pj,qi} is NP-hard.
► The special case with min{pj,qi}{pj,qi} is polynomially solvable.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 226, Issue 1, 1 April 2013, Pages 46–52
نویسندگان
, ,