研究了作业释放时间具有凸减资源消耗函数约束的单机调度问题,调度的目标是在限定Makespan的条件下使得作业消耗资源总量最小化.对于此类强NP-hard问题,定义了作业右移和左移两种基本运算以及交换和插入两种邻域生成方式,并在此基础上构造了模拟退火算法.为评价算法的性能,将此问题松弛成指派问题,从而用匈牙利方法得到松弛问题的最优解,并进一步改进下界的质量.实验表明所构造的模拟退火算法能够在合理的时间内提供高质量的满意解.
科研之友
微信
新浪微博
Facebook
分享链接
