摘要
针对具有到达时间和运输延迟的两机器流水车间排序问题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.
出处
《复旦学报（自然科学版）》
CAS
CSCD
北大核心
2007年第4期427-430,436,共5页
Journal of Fudan University：Natural Science
基金
国家自然科学基金资助项目(70432001)
关键词
排序
流水车间
多项式时间近似算法
运输时间
scheduling
flow-shop
polynomial time approximation scheme
transportation times
