带准备时间的任务单机学习效应排序问题

作者：王吉波; 刘璐

来源：大连理工大学学报, 2013, (06): 930-936.

• 排序
• 单机
• 学习效应
• 准备时间 scheduling
• single-machine
• learning effect
• release time

具有学习效应的任务的加工时间和带有准备时间的任务问题是排序论中的重要研究内容,它们对任务的完工时间有重要影响.研究了具有学习效应且带有准备时间的任务单机排序问题,其中学习效应指的是任务的实际加工时间是该已经排好的任务对数加工时间的递减函数,目标函数为最小化总完工时间.这个问题是NP-难问题.用分支定界法给出了此问题的最优解,为了提高分支定界法的运行效率,同时给出了一个启发式算法、几个优势性质和两个下界.计算结果表明分支定界法和启发式算法求解此问题非常有效.

• 单位
  西安交通大学机械制造系统工程国家重点实验室; 沈阳航空航天大学