供应链排序问题

摘要

所考虑的供应链排序系统为:若干个不同的元件供应商向一产品加工商供应产品元件,产品加工商等所有的元件都加工完成后再开始最后阶段的加工即成品加工;假定成品完工时间是所有元件中最后完工的元件的完工时间(即成品加工是无瓶颈的且将工时设为零);目标函数是极小化工件所有元件的带权的完工时间之和.对于问题As||sΣi=1 nΣj=1 WijCij,设计出了它的一个计算时间为(n2logn)的多项式时间算法.%Supply chain management has been one of the most active topics in manufacturing re-search over the last ten years. In our consider system, there are several suppliers and one manufac-ture. Each supplier provides component parts to the manufacturer. The manufacturer makes products that are depend on all the component parts. Therefore, the manufacturer waits until all the compo-nents for a job have arrived and then initiates a final stage of manufacturing stage, we assume that this final stage is non-bottleneck. The objective function is to minimize the total weighted completion time of the parts. ForAs ||sΣi=1 nΣj=1 WijCij, we firstly provide an efficient algorithm which solves it in time of (n2logn).