کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
482754 | 1446217 | 2006 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The routing open-shop problem on a network: Complexity and approximation
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: The routing open-shop problem on a network: Complexity and approximation The routing open-shop problem on a network: Complexity and approximation](/preview/png/482754.png)
چکیده انگلیسی
In the routing open-shop problem, jobs are located at nodes of an undirected transportation network, and the machines travel on the network to execute jobs in the open-shop environment. The machines are initially located at the same node (depot) and must return to the depot after completing all the jobs. It is required to find a nonpreemptive schedule that minimizes the makespan. We prove that the problem is NP-hard even on a two-node network with two machines, and even on a two-node network with two jobs and m machines. We develop polynomial-time approximation heuristics and obtain bounds on their approximation performance.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 173, Issue 2, 1 September 2006, Pages 531–539
Journal: European Journal of Operational Research - Volume 173, Issue 2, 1 September 2006, Pages 531–539
نویسندگان
Igor Averbakh, Oded Berman, Ilya Chernykh,