کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6895694 | 1445980 | 2016 | 32 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Min-max regret version of a scheduling problem with outsourcing decisions under processing time uncertainty
ترجمه فارسی عنوان
حداقل حداکثر پشیمانی نسخه یک مشکل برنامه ریزی با تصمیمات برون سپاری در زمان عدم اطمینان پردازش
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
برنامه ریزی، عدم قطعیت، برون سپاری، پیچیدگی محاسباتی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
We consider the min-max regret version of a single-machine scheduling problem to determine which jobs are processed by outsourcing under processing time uncertainty. The performance measure is expressed as the total cost for processing some jobs in-house and outsourcing the rest. Processing time uncertainty is described through two types of scenarios: either an interval scenario or a discrete scenario. The objective is to minimize the maximum deviation from optimality over all scenarios. We show that when the cost for in-house jobs is expressed as the makespan, the problem with an interval scenario is polynomially solvable, while the one with a discrete scenario is NP-hard. Thus, for the discrete scenario case, we develop a 2-approximation algorithm and investigate when the problem is polynomially solvable. Since the problem minimizing the total completion time as a performance measure for in-house jobs is known to be NP-hard for both scenarios, we consider the problem with a special structure for the processing time uncertainty and develop a polynomial-time algorithm for both scenarios.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 252, Issue 2, 16 July 2016, Pages 367-375
Journal: European Journal of Operational Research - Volume 252, Issue 2, 16 July 2016, Pages 367-375
نویسندگان
Byung-Cheon Choi, Kwanghun Chung,