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

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

Approximation Algorithms for a Three-Stage Supply Chain Scheduling Problem

In this paper, we study a three-stage supply chain scheduling problem. The warehouse that stores all materials and finished jobs, as well as the machines that process the jobs are located at different places. The jobs travel between the factory and warehouse. The paper mainly considers two models： one involves two vehicles and a single machine; the other involves a vehicle and two parallel machines. The ob- jective is to minimize the makespan of the schedule, i. e. , the period within which all jobs are transported back to the warehouse after processing. For both models, we present algorithms and show that their worst-case ratios are 2 and 2＋2λ-1^-1（λ〉1）,respectively.