论文部分内容阅读
本文研究一个供应商为多个制造商供货的供应链管理中供应商对工件(原料)进行加工,并分批发送给下游制造商的集成排序问题.供应商有m台平行机可以同时进行加工,以工件的总流程时间作为生产排序费用,集成排序问题的目标是使生产排序费用加上分批发送费用的总和为最小.对这个问题建立模型,证明是强-NP难问题,给出建立在动态规划基础上的多项式时间的近似算法,并证明近似算法的界是2-1/m.此外,还考虑生产排序费用与交货期有关的两个集成排序问题的NP-难解性.