论文部分内容阅读
在经典的排序问题中,工件的加工时间通常假设为固定的,不变的。然而,在实际生产活动中,工件的加工时间可能依靠可能依赖于起开始加工时间或分配给其的额外资源量。例如,在钢铁加工中铁块的温度在等待进入旋转的机器而降低,此时需要在旋转前重新给铁块加热。相同的情况也可能在包括国防任务或者清洗工作中发生,在完成这些任务的过程中任何的延误都将导致为了完成工作而花费额外的时间这样的惩罚。 本文在同时具有恶化效应(工件的实际加工时间是其开始加工时间的非减函数)和加工时间可控(可通过分配额外的资源量来缩小工件的加工时间)的生产环境下,研究两台机器上的序列流水车间排序问题。主要的目标是寻找最优的加工序列和资源分配策略来分别最小化即最大完成时间,总的完成时间,总的完成时间差和资源消耗费用的加权和,及最大完成时间,总的等待时间,总的等待时间差和资源消耗费用的加权和。分别通过将这两个问题拆分成两个子问题:a.对于给定序列下的最优资源分配策略问题;b.最优资源分配策略下的最优排序问题。尤其,这里将第二个问题变为最小化双向的图表理想匹配问题,可以用传统的KM(Kuhn-Munkres)算法。这两部分的解决说明了所研究的问题在本文所提供的模型下存在多项式的解决方案。