一类三阶段供应链排序问题的近似算法 (2012年)

主要研究一类三阶段供应链排序问题。储存工件的仓库和工厂在不同的地点,工件加工前需要从仓库运到工厂,加工完后再运回仓库。文中分别考虑了两个模型,第一个是两辆有容量限制的同类型车和单台机;第二个是一辆车和两台平行机。目标函数是极小化最后一个工件运回仓库的时间。针对两个模型,提出了相应的近似算法并证明其最坏情况界分别为2和2+ 1 /2λ-1 (其中λ>1)。