F2│r_j,t_j│C_(max)问题的多项式时间近似算法  

PTAS for a Two-machine Flow-shop Scheduling Problem with Release Dates and Transportation Times Delay

作　　者：张显东[1] 

机构地区：[1]复旦大学管理学院,上海200433

出　　处：《复旦学报（自然科学版）》2007年第4期427-430,436,共5页Journal of Fudan University：Natural Science

基　　金：国家自然科学基金资助项目(70432001)

摘　　要：针对具有到达时间和运输延迟的两机器流水车间排序问题F2│rj,tj│Cmax,证明了有运输时间约束的条件下,该问题最优排序是同顺序的,并给出了一种基于动态规划的多项式时间近似算法.The NP-hard problem of scheduling n jobs on a two-machine flow shop with release dates and arbitrary transportation times was addressed.If transportations times are constrained,permutation schedules are proved to be optimal.A(1+ε) polynomial time approximation scheme(PTAS) is developed which is based on dynamic programming.

关 键 词：排序 流水车间 多项式时间近似算法 运输时间 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]