...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Application of an optimization problem in Max-Plus algebra to scheduling problems
【24h】

Application of an optimization problem in Max-Plus algebra to scheduling problems

机译：Max-Plus代数中的优化问题在调度问题中的应用

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

摘要

The problem tackled in this paper deals with products of a finite number of triangular matrices in Max-Plus algebra, and more precisely with an optimization problem related to the product order. We propose a polynomial time optimization algorithm for 2 x 2 matrices products. We show that the problem under consideration generalizes numerous scheduling problems, like single machine problems or two-machine flow shop problems. Then, we show that for 3 x 3 matrices, the problem is NP-hard and we propose a branch-and-bound algorithm, lower bounds and upper bounds to solve it. We show that an important number of results in the literature can be obtained by solving the presented problem, which is a generalization of single machine problems, two- and three-machine flow shop scheduling problems. The branch-and-bound algorithm is tested in the general case and for a particular case and some computational experiments are presented and discussed. (c) 2006 Elsevier B.V. All rights reserved.
机译：本文解决的问题涉及Max-Plus代数中有限数量的三角矩阵的乘积，更确切地说，涉及与产品订单有关的优化问题。我们提出了2 x 2矩阵乘积的多项式时间优化算法。我们表明，所考虑的问题概括了许多调度问题，例如单机问题或两机流水车间问题。然后，我们证明对于3 x 3矩阵，问题是NP难的，我们提出了一种分支定界算法，下界和上限来解决它。我们表明，通过解决提出的问题可以得到大量的文献结果，这是单机问题，两机和三机流水车间调度问题的概括。在一般情况下和特定情况下对分支定界算法进行了测试，并提出并讨论了一些计算实验。 （c）2006 Elsevier B.V.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号