文献类型：期刊文献

中文题名：有使用限制的二台机器流水作业问题

英文题名：Two-Machine Flow Shop Problems with Availability Constraints

作者：杨名[1];鲁习文[1]

机构：[1]华东理工大学理学院数学系,上海200237

年份：2011

卷号：15

期号：3

起止页码：62

中文期刊名：运筹学学报

外文期刊名：Operations Research Transactions

收录：CSTPCD;;CSCD:【CSCD2011_2012】；

基金：上海自然科学基金(09ZR1407200);国家自然科学基金(11071072)

语种：中文

中文关键词：排序;流水作业;使用限制;近似算法;竞争比

外文关键词：scheduling, flow shop, availability constraint, approximation algorithm, competitive ratio

摘要：研究有使用限制的二台机器流水作业排序问题,目标为最小化最大完工时间,工件加工可以被机器的不可用时间段中断.讨论两台机器上均有使用限制离线问题的可近似情形,并给出性能比为3/2的近似算法.同时还考虑在第二台机器上存在一个不可用时间段情况下的半在线问题,给出一个竞争比为3/2的半在线算法.
This paper investigates the problems for two-machine flow shop scheduling with availability constraints. A resumable scenario is assumed, i.e., if a job cannot be finished before the interval it is continued after the machine becomes available again. The objective is to minimize the makespan. This paper first considers an approximate case of the problem with several availabilitv constraints on both machines, oresents an algorithm with performance ratio of 3/2, then gives an algorithm with competitive ratio of 3/2for the semi-online problem with an availability constraint on the second machine.