...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Approximations for the two-machine cross-docking flow shop problem
【24h】

Approximations for the two-machine cross-docking flow shop problem

机译：两机交叉停放流水车间问题的近似值

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We consider in this article the Two-Machine Cross-Docking Flow Shop Problem, which is a special case of scheduling with typed tasks, where we have two types of tasks and one machine per type. Precedence constraints exist between tasks, but only from a task of the first type to a task of the second type. The precedence relation is thus a directed bipartite graph. Minimizing the makespan is strongly NP-hard even with unit processing times, but any greedy method yields a 2-approximation solution. In this paper, we are interested in establishing new approximability results for this problem. More specifically, we investigate three directions: list scheduling algorithms based on the relaxation of the resources, the decomposition of the problem according to the connected components of the precedence graph, and finally the search of the induced balanced subgraph with a bounded degree.
机译：我们在本文中考虑了“两机交叉对接流水车间问题”，这是使用类型化任务进行调度的一种特例，其中我们有两种类型的任务，每种类型有一台机器。优先约束在任务之间存在，但仅限于从第一类任务到第二类任务。因此，优先级关系是有向二部图。即使使用单位处理时间，最小化制造跨度也具有很强的NP困难性，但是任何贪婪的方法都会产生2个近似解。在本文中，我们有兴趣为该问题建立新的近似结果。更具体地说，我们研究了三个方向：基于资源松弛的列表调度算法，根据优先级图的连接组件分解问题，最后搜索有界度的诱导平衡子图。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号