|
|||||
|
|
| 一类具有资源约束和优先加工顺序约束极小化加权总完工时间调度优化问题研究 | |
| 引用本文： | 李金权. 一类具有资源约束和优先加工顺序约束极小化加权总完工时间调度优化问题研究[J]. 计算数学, 2017, 39(4): 421-430 |
| 作者姓名： | 李金权 |
| 作者单位： | 北京师范大学珠海分校应用数学学院, 珠海 519087 |
| 基金项目： | 国家自然科学基金资助项目（11401030）；广东省高等学校优秀青年教师培养计划项目（2014年度，Yq2014228）；珠海市智能控制重点实验室建设项目. |
| 摘 要： | 本文针对工件间具有链状优先约束和relocation资源约束的极小化加权总完工时间调度优化问题展开研究.针对这一NP难问题,利用relocation约束的性质和贪婪算法的思想,设计了一个多项式近似算法,并证明了当链不可中断,每个链具有相同工件数和工件间具有相同加工时间时,2为该算法的紧界. |
| 关 键 词： | Relocation资源约束 优先加工约束 调度 加权总完工时间 |
MINIMIZING THE TOTAL WEIGHTED COMPLETION TIME FOR THE RELOCATION SCHEDULING PROBLEMS WITH PRECEDENCE CONSTRAINTS |
|
| Li Jinquan. MINIMIZING THE TOTAL WEIGHTED COMPLETION TIME FOR THE RELOCATION SCHEDULING PROBLEMS WITH PRECEDENCE CONSTRAINTS[J]. Mathematica Numerica Sinica, 2017, 39(4): 421-430 | |
| Authors: | Li Jinquan |
| Affiliation: | School of Applied Mathematics, Beijing Normal University, Zhuhai 519087, China |
| Abstract: | In this paper, the relocation scheduling problem with precedence constraints is investigated, where objective function is total weighted completion time. A polynomial algorithm is proposed for this kind of NP-hard scheduling problems based on the properties of relocation constraints and greedy rule. Also, it is proved that the performance ratio of the algorithm is 2 when each of chains is not nonpreemptive, and has the same jobs with the same processing times. |
| Keywords: | Relocation resource constraints Precedence constraints Scheduling Total weighted completion time |
| 本文献已被 CNKI 等数据库收录！ | |
| 点击此处可从《计算数学》浏览原始摘要信息 | |
| 点击此处可从《计算数学》下载全文 | |