| 释放时间具有凸减函数约束的单机调度问题 |
| |
| 引用本文： | 李凯,罗庆,杨善林. 释放时间具有凸减函数约束的单机调度问题[J]. 系统工程理论与实践, 2013, 33(6): 1516-1522. DOI: 10.12011/1000-6788(2013)6-1516 |
| |
| 作者姓名： | 李凯 罗庆 杨善林 |
| |
| 作者单位： | 1. 合肥工业大学 管理学院, 合肥 230009;2. 过程优化与智能决策教育部重点实验室, 合肥 230009;3. 武汉大学 软件工程国家重点实验室, 武汉 430072 |
| |
| 基金项目： | 国家自然科学基金(71101040, 71131002, 71001032); 安徽省自然科学基金(11040606Q27);高等学校博士学科点专项科研基金(20120111120013); 武汉大学软件工程国家重点实验室开放基金(SKLSE2012-09-10) |
| |
| 摘 要： | 研究了作业释放时间具有凸减资源消耗函数约束的单机调度问题, 调度的目标是在限定Makespan的条件下使得作业消耗资源总量最小化. 对于此类强NP-hard问题, 定义了作业右移和左移两种基本运算以及交换和插入两种邻域生成方式, 并在此基础上构造了模拟退火算法. 为评价算法的性能, 将此问题松弛成指派问题, 从而用匈牙利方法得到松弛问题的最优解, 并进一步改进下界的质量. 实验表明所构造的模拟退火算法能够在合理的时间内提供高质量的满意解.
|
| 关 键 词： | 调度 单机 Makespan 资源分配 释放时间 |
| 收稿时间： | 2011-03-14 |
Single machine scheduling problem with release dates under the constraint of convex decreasing functions |
| |
| LI Kai , LUO Qing , YANG Shan-lin. Single machine scheduling problem with release dates under the constraint of convex decreasing functions[J]. Systems Engineering —Theory & Practice, 2013, 33(6): 1516-1522. DOI: 10.12011/1000-6788(2013)6-1516 |
| |
| Authors: | LI Kai LUO Qing YANG Shan-lin |
| |
| Affiliation: | 1. School of Management, Hefei University of Technology, Hefei 230009, China;2. Key Laboratory of Process Optimization and Intelligent Decision-making, Ministry of Education, Hefei 230009, China;3. State Key Laboratory of Software Engineering, Wuhan University, Wuhan 430072, China |
| |
| Abstract: | This paper considers a single machine scheduling problem, in which the release dates of the jobs are convex decreasing functions of the consumed resource. The objective is minimizing the total resource consumption with a limited Makespan. For the NP-hard problem in the strong sense, two basic operators, left-move and right-move, and two neighborhood generation methods, insert and swap, are defined to build a simulated annealing algorithm. To evaluate the accuracy of the proposed algorithm, the problem is relaxed to an assignment problem to obtain a lower bound by Hungary method. The computational results show that the presented simulated annealing algorithm can yield high-quality solutions for the considered scheduling problem. |
| |
| Keywords: | scheduling single machine Makespan resource allocation release dates |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《系统工程理论与实践》浏览原始摘要信息 |
|
点击此处可从《系统工程理论与实践》下载全文 |
|
