具有最大总加权满意度的单机调度问题的dynasearch算法
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:


Dynasearch algorithms for single machine scheduling problem with total weighted satisfaction
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    研究了总加权满意程度最大化的单机调度问题.对最优解的性质进行分析和证明,提出该类问题的统治规则.提出该问题新的基于dynasearch邻域的迭代局域搜索算法(ILS).算法主要特点:1)dynasearch是基于多摄动的思想,即一次可以做多个相互独立的交换(或插入);2)用动态规划获得最优dynasearch移动;3)ILS采用随机kick策略对局部最优解进行摄动,然后继续迭代.实现了该问题的两种dynaearch算法;把两种dynasearch算法与统治规则相结合;在进行kick时引入误差限制.实验表明:嵌入统治规则的算法优于没有统治规则的算法;基于dynasearch交换的ILS优于基于dynasearch插入的ILS;dynaearch算法要优于以交换为邻域的多初始点改进算法

    Abstract:

    The paper extends the dynasearch algorithm to single machine scheduling problem to maximize the total weighted satisfaction level (SMTWSL). It gives an analysis and proof about the character of optimal solution based on which we propose a dominance rule for the problem. For this problem, it presents a new iterated local search algorithm based on dynasearch neighborhood with the following characters: 1 ) While traditional local search algorithms make a single move at each iteration, dynasearch allows a series of independent moves to be performed. 2) A dynasearch move, composed of several optimal independent moves, is obtained by dynamic programming in the expanded neighborhood. 3) A local optimal solution, obtained from an initial one by ILS algorithm, is disturbed by a random kick tactic and then is searched again by dynasearch algorithm. While dynasearch algorithm was applied to the SMTWSL problem, three pieces of work has been done: Two dynasearch algorithms are carried out. Combination of dominance rule with the algorithm speeding up the dynasearch algorithm. An error limit that restricts the difference between the local optimal solution and the solution after perturbation, also speeds up the dynasearch algorithm. The conclusions are: The combination of ILS dyasearch algorithm and dominance rule is superior to the ILS dynasearch algorithm alone. The dynasearch swap algorithm is superior to that of the dyansearch insert algorithm. Both of the swap and insert dynasearch algorithms are better than the multi-start improving algorithm based on swap

    参考文献
    相似文献
    引证文献
引用本文

冯大光 唐立新.具有最大总加权满意度的单机调度问题的dynasearch算法[J].管理科学学报,2006,9(4):0

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期:
  • 出版日期:
您是第位访问者
管理科学学报 ® 2024 版权所有
通讯地址:天津市南开区卫津路92号天津大学第25教学楼A座908室 邮编:300072
联系电话/传真:022-27403197 电子信箱:jmsc@tju.edu.cn