反相容工件系统的加权完工时间和的重新排序问题

摘要：

重新排序问题是指在原始工件已经安排好的情形下,新到的工件集与原始工件集一起重新再排序,这是实际工作中常见一类优化问题.本文考虑了单机上当工件加工时间与权重反相容时,在最大错位量约束下的加权完工时间和最小化的重新排序问题.对于提出的四个问题,即在最大序列错位、最大时间错位、总序列错位和总时间错位约束下的加权完工时间和重新排序,基于问题的结构性质,运用动态规划方法分别给出了这些问题的多项式时间或拟多项式时间算法.

关键词：重新排序、单机、完工时间、错位量、反相容

所属期刊栏目：27

分类号：O223(运筹学)

资助基金：NSFC10671183;NSFHN082300410190;NSF of the Education Department of Henan Province2008Al10004;the Science Foundation07XJC002;Doctor Science Foundation of Henan University of Technology

在线出版日期：2010-04-28（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：152-160