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

Approximation Algorithms for a Three-Stage Supply Chain Scheduling Problem

作　　者：胡觉亮[1] 查聪[1] 蒋义伟[1] 

机构地区：[1]浙江理工大学理学院,杭州310018

出　　处：《浙江理工大学学报（自然科学版）》2012年第5期709-713,共5页Journal of Zhejiang Sci-Tech University(Natural Sciences)

基　　金：国家自然科学基金项目(11001242;11071220);浙江省自然科学基金项目(Y6090554;Y6090175;Y6110091)

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

关 键 词：供应链排序 近似算法 最坏情况界 

分 类 号：O233[理学—运筹学与控制论]