| 平行机上带有前瞻区间的不相容工件组在线排序问题 |
| |
| 作者姓名： | 李文华 柴幸 袁航 杨素芳 |
| |
| 作者单位： | 1. 郑州大学数学与统计学院, 郑州 450001;2. 浙江大学经济学院, 杭州 310027 |
| |
| 基金项目： | 1.国家自然科学基金(No. 11171313),
2.河南省教育厅科技研究重点项目(No. 14A110025),
3.郑州大学自主创新项目(No. 14LD00610) |
| |
| 摘 要： | 研究当不相容工件组的个数与机器数相等时,具有前瞻区间的单位工件平行机无界平行分批在线排序问题.工件按时在线到达, 目标是最小化 最大完工时间. 具有前瞻区间是指在时刻t, 在线算法能预见到时间区间(t,t+\beta) 内到达的所有工件的信息.不可相容的工件组是指属于不同组的工件不能被安排在同一批中加工. \beta\geq 1 时, 提供了一个最优的在线算法; 当0\leq \beta < 1时, 提供了一个竞争比为1+\alpha 的最好可能的在线算法, 其中\alpha是方程\alpha^{2}+(1+\beta) \alpha+\beta-1=0的一个正根.最后, 给出了当\beta =0 时稠密算法竞争比的下界,并提供了达到该下界的最好可能的稠密算法.
|
| 关 键 词： | 在线排序 平行分批 不相容工件组 最大完工时间 竞争比 |
| 收稿时间： | 2014-12-01 |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
|
点击此处可从《运筹学学报》下载全文 |
|
