计划与排序问题的可逆性及其应用

摘要

本文论证了生产计划与排序问题的可逆性,即一般生产车间计划与排序问题(原问题)以及将其生产加工各个阶段反向条件下的逆问题的加工周期保持不变.这一可逆性意味着原问题的最优加工周期的上下界也是其逆问题的最优加工周期的上下界.这一性质可用于获取加工周期的上下界值,还可用于评价一个启发式算法所得到的生产加工顺序的近似最优解等方面。