计算数学
       首页 |  期刊介绍 |  编委会 |  投稿指南 |  期刊订阅 |  下载中心 |  留言板 |  联系我们 |  在线办公 | 
计算数学  2017, Vol. 39 Issue (4): 421-430    DOI:
论文 最新目录 | 下期目录 | 过刊浏览 | 高级检索 Previous Articles  |  Next Articles  
一类具有资源约束和优先加工顺序约束极小化加权总完工时间调度优化问题研究
李金权
北京师范大学珠海分校应用数学学院, 珠海 519087
MINIMIZING THE TOTAL WEIGHTED COMPLETION TIME FOR THE RELOCATION SCHEDULING PROBLEMS WITH PRECEDENCE CONSTRAINTS
Li Jinquan
School of Applied Mathematics, Beijing Normal University, Zhuhai 519087, China
 全文: PDF (365 KB)   HTML (1 KB)   输出: BibTeX | EndNote (RIS)      背景资料
摘要 本文针对工件间具有链状优先约束和relocation资源约束的极小化加权总完工时间调度优化问题展开研究.针对这一NP难问题,利用relocation约束的性质和贪婪算法的思想,设计了一个多项式近似算法,并证明了当链不可中断,每个链具有相同工件数和工件间具有相同加工时间时,2为该算法的紧界.
服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
关键词Relocation资源约束   优先加工约束   调度   加权总完工时间     
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.
Key wordsRelocation resource constraints   Precedence constraints   Scheduling   Total weighted completion time   
收稿日期: 2017-01-08;
基金资助:

国家自然科学基金资助项目(11401030);广东省高等学校优秀青年教师培养计划项目(2014年度,Yq2014228);珠海市智能控制重点实验室建设项目.

引用本文:   
. 一类具有资源约束和优先加工顺序约束极小化加权总完工时间调度优化问题研究[J]. 计算数学, 2017, 39(4): 421-430.
. MINIMIZING THE TOTAL WEIGHTED COMPLETION TIME FOR THE RELOCATION SCHEDULING PROBLEMS WITH PRECEDENCE CONSTRAINTS[J]. Mathematica Numerica Sinica, 2017, 39(4): 421-430.
 
[1] Mohammad Ranjbar, Saeed Hosseinabadi, Foroogh Abasian. Minimizing total weighted late work in the resource-constrained project scheduling problem[J]. Applied Mathematical Modelling, 2013, 37:9776-9785.
[2] Junzilan Cheng, JohnFowler, KarlKempf, ScottMason. Multi-mode resource-constrained project scheduling problems with non-preemptive activity splitting[J]. Computers & Operations Research, 2015, 53:275-287.
[3] Haitao Li, Norman K. Womer. Solving stochastic resource-constrained project scheduling problems by closed-loop approximate dynamic programming[J]. European Journal of Operational Research, 2015, 246:20-33.
[4] Dvir Shabtay, George Steiner, Rui Zhang. Optimal coordination of resource allocation, due date assignment and scheduling decisions[J]. Omega, 2016, 65:41-54.
[5] Kaplan E H. Relocation models for public housing redevelopment programs[J]. Environment and Planning B:Planning and Design, 1986, 13:5-19.
[6] Kaplan E H, Amir A. A fast feasibility test for relocation problems[J]. European Journal of Operational Research, 1988, 35:201-206.
[7] Kaplan E H, Berman O. OR hits the heights:Relocation planning at the orient heights housing project[J]. Interfaces, 1988, 18:14-22.
[8] Amir A, Kaplan, E H. Relocation problems are hard. International Journal of Computer Mathematics, 1988, 25:101-110.
[9] Xie J X. Polynomial algorithms for single machine shceduling problems with financial constraints[J]. Operations Research Letters, 1997, 21:39-42.
[10] Kononov A V, Lin B M T. On relocation problems with multiple identical working crews[J]. Discrete Optimization, 2006, 3:366-381.
[11] Kononov A V, Lin B M T. Minimizing the total weighted completion time in the relocation problem. Journal of Scheduling, 2010, 13:123-129.
[12] Laborie P. Algorithms for propagating resource constraints in AI planning and scheduling:Existing approaches and new results[J]. Artificial Intelligence, 2003, 143:151-188.
[13] Neumann K, Schwindt C. Project scheduling with inventory constraints[J]. Mathematical Methods of Operations Research, 2002, 56:513-533.
[14] Lin B M T, Hwang F J, Kononov A V. Relocation scheduling subject to finxed processing sequences[J]. Journal of Scheduling, 2016, 19:153-163.
[15] Martin Skutella. A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective[J]. Operations Research Letters, 2016, 44:676-679.
[16] Wang Ji-Bo, Wang Jian-Jun. Single-machine scheduling problems with precedence constraints and simple linear deterioration[J]. Applied Mathematical Modelling, 2015, 34:1172-1182.
[17] Yuan Junling, Li Wenhua, Yuan Jinjiang. A best possible online algorithm for scheduling equallength jobs on two machines with chain precedence constraints[J]. Theoretical Computer Science,2012, 457:174-180.
没有找到本文相关文献

Copyright 2008 计算数学 版权所有
中国科学院数学与系统科学研究院 《计算数学》编辑部
北京2719信箱 (100190) Email: gxy@lsec.cc.ac.cn
本系统由北京玛格泰克科技发展有限公司设计开发
技术支持: 010-62662699 E-mail:support@magtech.com.cn
京ICP备05002806号-10