• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >A Tabu search algorithm for the open shop scheduling problem with sequence dependent setup times.
【24h】

A Tabu search algorithm for the open shop scheduling problem with sequence dependent setup times.

机译：一种禁忌搜索算法，用于解决开放式车间调度问题，其顺序取决于设置时间。

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

摘要

The impact of setup on manufacturing performance, and the scarce research on the scheduling of the open shop with sequence dependent setup times have motivated this research. The open shop consist of a set of n jobs each one requiring m operations to be processed on a set of m machines, one operation per machine. Each operation has a fixed duration time. To process a job on a machine a setup is required whose duration depends on both the job just processed and the job to be processed. The problem consist on fording an order of processing operations of jobs on the machines with the objective to minimize the longest time to finish the schedule or the makespan. The problem is modeled by a disjunctive graph. To find the best solution for this problem an algorithm combining Tabu search and a longest path algorithm is proposed.; The initial solution is generated by a proposed dispatching rule and by random. On every iteration a critical path is computed. The algorithm is based on the selection of moves from blocks of operations along this critical path. The neighborhood is generated by moves whose operations are processed by the same machine and by moves whose operations belong to the same job. A procedure to reduce the amount of computations resulting in the evaluation of each move is implemented. For this end we have developed a procedure based on the inverse topological order of operations in a graph. At the end of every iteration the best move is selected.; To further improve the search an intensification strategy is implemented by restarting the search from previous best solutions. The algorithm detect potential cycles in the solution, stopping the search once a probable cycle is detected, and transferring the search to the intensification strategy.; The algorithm has been tested with a set of random generated problems and two benchmark problems from literature.
机译：设置对制造性能的影响，以及对与序列相关的设置时间的开放式车间调度的研究很少，这激发了这一研究的动机。公开车间由一组 n 个工作组成，每个工作需要在一组 m 机器上处理 m 个操作，每台机器一个操作。每个操作都有固定的持续时间。要在机器上处理作业，需要进行设置，其持续时间取决于刚处理的作业和要处理的作业。问题在于强制执行机器上作业的处理顺序，目的是最大程度地减少完成计划或工期的最长时间。该问题由析取图建模。为了找到这个问题的最佳解决方案，提出了一种结合禁忌搜索和最长路径算法的算法。初始解决方案是通过提议的调度规则生成的，并且是随机生成的。在每次迭代中，都会计算一条关键路径。该算法基于沿着此关键路径从操作块中选择移动。邻域由其操作由同一台机器处理的移动以及其操作属于同一作业的移动生成。实现了减少计算量的过程，该计算量导致对每个动作的评估。为此，我们根据图形中操作的逆拓扑顺序开发了一个过程。在每次迭代结束时，将选择最佳移动。为了进一步改善搜索，通过从以前的最佳解决方案重新开始搜索，可以实施强化策略。该算法检测溶液中的潜在循环，一旦检测到可能的循环就停止搜索，并将搜索转移至强化策略。该算法已通过一系列随机产生的问题和文献中的两个基准问题进行了测试。

著录项

  • 作者

    Aguirre-Solis, Jesus Jose.;

  • 作者单位

    New Mexico State University.;

  • 授予单位 New Mexico State University.;
  • 学科 Engineering Industrial.
  • 学位 Ph.D.
  • 年度 2003
  • 页码 255 p.
  • 总页数 255
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 一般工业技术;
  • 关键词

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号