序列错位限制下最小化完工时间和的继列分批重新排序

摘要

在单机分批排序中,一个原始工件集已经分好批排好顺序,使得给定的目标函数最小.当一个新的工件集到来时,决策者需要插入这些新工件到原来的顺序中,这样使得原始工件就会产生一些错位.但为了满足对原始工件集的要求而不过分的打乱它们的顺序的条件下,使得新的目标值为最优.本文主要研究的是在序列错位量限制的条件下,继列分批最小化总完工时间的重新排序问题,对于最大序列错位和总序列错位的不同约束情况下,研究可行排序和最优排序的结构性质,进而设计了它们的多项式时间算法.%In the rescheduling on a single batching machine, a set of the original jobs has already been scheduled,in order to make a given objective function is minimal. The decision maker needs to insert the new jobs into the existing schedule without excessively disrupting it. We consider the total completion time of the series hatching under the a limit on the sequence disruption, and give the polynomial time algorithms to the maximum sequence disruption and the total sequence disruptions.