.png){kind=icon}
返回
A 6/5-approximation algorithm for the two-machine routing open-shop problem on a two-node network
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2003.06.050.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
In the routing open-shop problem, jobs are located at nodes of a transportation network, and the machines travel on the network to execute jobs. For the makespan-minimizing two-machine routing open-shop problem on a two-node network (which is NP-hard) we prove that the optimum objective value of any instance lies within the interval [(C) over tilde, 6/5 (C) over tilde] and this interval is tight. (C) over tilde is a trivial lower bound on the optimum objective value. Based on this result, we obtain a linear time approximation algorithm for this problem with approximation ratio not greater than 6/5. From the tightness of the interval above it follows that this algorithm gives the best possible approximation in terms of (C) over tilde. The problem is equivalent to a variant of the two-machine open-shop problem with batch setup times with two batches. (c) 2004 Elsevier B.V. All rights reserved.
Keyword:
scheduling
combinatorial optimization
approximation algorithms
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
2.2W
被引数:
6.4W
机构
暂无机构信息
引用论文
.png){kind=icon}
C-Reactive Protein to Albumin Ratio in Patients with Prediabetes and Diabetes Mellitus: HbA1c and InflammationC-反应蛋白与白蛋白比值在糖耐量减低和糖尿病 mellitus 患者中的研究：糖化血红蛋白和炎症
PREAI
分享收藏分享收藏
Optimization of silicon-germanium TFT's through the control of amorphous precursor characteristics
PREAI
分享收藏Understanding and Optimizing Workloads for Unified Resource Management in Large Cloud Platforms
PREAI
分享收藏 没有更多内容
没有更多内容