| 谢志强,邵侠,杨静.存在设备有关延迟约束的综合调度算法[J].高技术通讯(中文),2012,22(3):309~314 |
| 存在设备有关延迟约束的综合调度算法 |
| An integrated scheduling algorithm with device dependence deferred constraint |
| 修订日期：2010-10-26 |
| DOI： |
| 中文关键词: 延迟约束， 设备有关延迟约束（DDC）， 综合调度， 拟关键路径法（ACPM）， 算法 |
| 英文关键词: deferred constraint, device dependent deferred constraint(DDC), integrated scheduling, allied critical path method (ACPM), algorithm |
| 基金项目:国家自然科学基金(60873019，61073043),黑龙江省自然科学基金(F200901，F201101),中国博士后科学基金(20090460880)和哈尔滨市优秀学科带头人(2010RFXXG054，2011RFXXG015)资助项目 |
| 作者 | 单位 | | 谢志强 | 哈尔滨工程大学计算机科学与技术学院；哈尔滨理工大学计算机科学与技术学院 | | 邵侠 | 哈尔滨理工大学计算机科学与技术学院 | | 杨静 | 哈尔滨工程大学计算机科学与技术学院 |
|
| 摘要点击次数: 2690 |
| 全文下载次数: 2031 |
| 中文摘要: |
| 针对目前综合调度中没有考虑设备有关延迟约束(DDC)影响调度效果的问题，提出了存在设备有关延迟约束的综合调度的算法。该算法在标准工序、设备有关延迟工序(DDP)和包含设备有关延迟约束的加工工艺树等概念的基础上，将等待延迟时间转化为设备有关延迟工序，使存在DDC的调度问题转变为较易解决的一般综合调度问题，再用拟关键路径法(ACPM)确定工序的调度次序，最后用前沿贪心规则确定工序的开始时间。为了使设备有关延迟工序影响的工序尽早开始，进一步提出了设备有关延迟工序配合调整的策略。实验表明，该调度算法能够有效解决存在设备有关延迟约束的综合调度问题，可在不提高算法复杂度的前提下，提高调度结果的精度并减少产品总的加工时间。 |
| 英文摘要: |
| Aiming at the problem that the present integrated scheduling ignores the device dependent deferred constraint (DDC) thus the scheduling result is affected, an integrated scheduling algorithm with the device dependent deferred constraint is proposed. On the basis of the concepts of standard procedure, device dependent deferred procedure (DDP) and the processing tree with the device dependent deferred constraint, the algorithm converts the waitting delay time into the device dependent deferred procedure, thus the scheduling problems with the device dependent deferred constraint are converted into the general integrated scheduling problem being easy to solve. Then, the order of the procedures is determined by the allied critical path method (ACPM), and the start time of procedure is determined by the forward greedy rule. The strategy for device dependent delay procedure cooperating adjustment is proposed to make affected standard procedures start early. The experimental results show that the proposed algorithm can solve the integrated scheduling problems with device dependent deferred constraint. The scheduling result is more accurate, and the total processing time is reduced without increasing the algorithm complexity. |
|
查看全文
查看/发表评论 下载PDF阅读器 |
| 关闭 |
