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

摘要：

研究有使用限制的二台机器流水作业排序问题,目标为最小化最大完工时间,工件加工可以被机器的不可用时间段中断.讨论两台机器上均有使用限制离线问题的可近似情形,并给出性能比为3/2的近似算法.同时还考虑在第二台机器上存在一个不可用时间段情况下的半在线问题,给出一个竞争比为3/2的半在线算法.

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

所属期刊栏目：15

分类号：O223(运筹学)

资助基金：上海自然科学基金09ZR1407200;国家自然科学基金11071072

在线出版日期：2012-02-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：62-69