• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Symposium on Digital Manufacture; 20061015-17; Wuhan(CN) >An Improved Ant Colony Algorithm for a Single-machine Scheduling Problem with Setup Times
【24h】

An Improved Ant Colony Algorithm for a Single-machine Scheduling Problem with Setup Times

机译：带有建立时间的单机调度问题的改进蚁群算法

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

摘要

Motivated by industrial applications we study a single-machine scheduling problem in which all the jobs are mutually independent and available at time zero. The machine processes the jobs sequentially and it is not idle if there is any job to be processed. The operation of each job cannot be interrupted. The machine cannot process more than one job at a time. A setup time is needed if the machine switches from one type of job to another. The objective is to find an optimal schedule with the minimal total jobs' completion time. While the sum of jobs' processing time is always a constant, the objective is to minimize the sum of setup times. Ant colony optimization (ACO) is a meta-heuristic that has recently been applied to scheduling problem . In this paper we propose an improved ACO-Branching Ant Colony with Dynamic Perturbation (DPBAC) algorithm for the single-machine scheduling problem . DPBAC improves traditional ACO in following aspects : introducing Branching Method to choose starting points; improving state transition rules; introducing Mutation Method to shorten tours; improving pheromone updating rules and introducing Conditional Dynamic Perturbation Strategy. Computational results show that DPBAC algorithm is superior to the traditional ACO algorithm.
机译：受工业应用的启发，我们研究了单机调度问题，其中所有作业都是相互独立的，并且在零时可用。机器按顺序处理作业，如果有要处理的作业，它不会处于空闲状态。每个作业的操作都不能中断。机器一次不能处理多个任务。如果机器从一种工作类型切换到另一种工作，则需要准备时间。目的是找到具有最少总作业完成时间的最佳计划。尽管作业的处理时间总和始终是恒定的，但目标是最大程度地减少设置时间的总和。蚁群优化（ACO）是一种最近启发式算法，已应用于调度问题。本文针对单机调度问题提出了一种改进的带有动态扰动的ACO分枝蚁群算法（DPBAC）。 DPBAC在以下几个方面对传统的ACO进行了改进：引入分支方法来选择起点；完善国家过渡规则；引入突变方法以缩短游览；改进信息素更新规则，并引入条件动态摄动策略。计算结果表明，DPBAC算法优于传统的ACO算法。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号