中原工学院理学院, 郑州 450007
出版日期:2017-11-25发布日期:2017-12-29Rescheduling to Minimize the Maximum Weighted Completion Time
ZANG Xijie, LI Shisheng ,WANG XifengCollege of Science, Zhongyuan University of Technology, Zhengzhou 450007
Online:2017-11-25Published:2017-12-29摘要
图/表
参考文献
相关文章
编辑推荐
-->Metrics
本文评论
重新排序模型可以描述如下: 一组原始工件已经按照某个准则做好最优加工 ~(排序)~方案, 但是还没有开始加工. 此时, 另一组新工件突然到达, 需要与原始工件一起加工. 生产部门需要调整已有的加工方案, 使得在原始工件不打乱太多的情形下得到一个合理的排序. 本文研究最大加权完工时间的重新排序问题, 问题的目标是: 1) 在原始排序错位限制的条件下最小化最大加权完工时间; 2) 最小化最大加权完工时间与原始排序的错位的加权和. 在本文研究中我们假设所有工件在~0~时刻到达. 文章的主要结果:对于${\it \Gamma} \in \{D_{\max}(\pi^{\ast}), \Delta_{\max}(\pi^{\ast}) \}$, 给出了问题$1|{\it \Gamma} \leq k|\max w_{j}C_{j}$~和问题$1||\max w_{j}C_{j} +\mu {\it \Gamma}$~多项式时间的求解算法;证明了问题$1|\sum\Delta_{j}(\pi^{\ast}) \leq k|\max w_{j}C_{j}$~和问题$1||\max w_{j}C_{j}+\mu \sum\Delta_{j}(\pi^{\ast})$~是强~NP-困难的.
分享此文:
