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

关键词：调度 单机 makespan 资源分配 释放时间 

单位：合肥工业大学管理学院 合肥230009 过程优化与智能决策教育部重点实验室 合肥230009 武汉大学软件工程国家重点实验室 武汉430072