CAJ | 학술논문

在单机分批排序中,一个原始工件集已经分好批排好顺序,使得给定的目标函数最小.当一个新的工件集到来时,决策者需要插入这些新工件到原来的顺序中,这样使得原始工件就会产生一些错位.但为了满足对原始工件集的要求而不过分的打乱它们的顺序的条件下,使得新的目标值为最优.本文主要研究的是在序列错位量限制的条件下,继列分批最小化总完工时间的重新排序问题,对于最大序列错位和总序列错位的不同约束情况下,研究可行排序和最优排序的结构性质,进而设计了它们的多项式时间算法.
재단궤분비배서중,일개원시공건집이경분호비배호순서,사득급정적목표함수최소.당일개신적공건집도래시,결책자수요삽입저사신공건도원래적순서중,저양사득원시공건취회산생일사착위.단위료만족대원시공건집적요구이불과분적타란타문적순서적조건하,사득신적목표치위최우.본문주요연구적시재서렬착위량한제적조건하,계렬분비최소화총완공시간적중신배서문제,대우최대서렬착위화총서렬착위적불동약속정황하,연구가행배서화최우배서적결구성질,진이설계료타문적다항식시간산법.
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.