文献类型：期刊文献

中文题名：工件带到达时间的两阶段柔性流水作业的近似算法

英文题名：Approximation Algorithms for Two-stage Flexible Flow Shop Scheduling Subject to Release Dates

作者：王辉[1];鲁习文[1]

机构：[1]华东理工大学应用数学研究所,上海200237

年份：2007

卷号：11

期号：3

起止页码：86

中文期刊名：运筹学学报

外文期刊名：Operations Research Transactions

收录：CSTPCD;;北大核心:【北大核心2004】；CSCD:【CSCD2011_2012】；

基金：回国人员科研启动基金和校科研基金.

语种：中文

中文关键词：运筹学;柔性流水作业;到达时间;时间表;性能比

外文关键词：Operations research, flexible flow shop, release dates, scheduling, performance ratio

摘要：研究了工件带到时间的两阶段柔性流水作业的排序问题,基于求解流水作业和平行机问题的算法思想,提出两个相应的近似算法H(R)和H(MR(?)),证明了这两个算法的最坏情况性能比分别为3-1/m和2/5-1/m,讨论了界的紧性,并利用数值模拟以分析算法与最优值的近似性能比.
Consider a two-stage flexible flow shop scheduling problem subject to release dates. Based on the idea of solving the flow-shop problem and parallel machine problem, we provide two approximation algorithms H（R） and H（MRJ＇）. The worst-case performance ratios for the two algorithms are proven to be 3 - 1 5 1/ m and 5/2-1/m respectively. We discuss the tightness of the bound and do numerical simulation to analyze the approximation performance ratio between the algorithm and the optimal solution.