文献类型：期刊文献

中文题名：在线可中断二台机器流水作业问题

英文题名：Online Preemptive Scheduling of Two-machine Flow Shops

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

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

年份：2011

卷号：20

期号：5

起止页码：27

中文期刊名：运筹与管理

外文期刊名：Operations Research and Management Science

收录：CSTPCD;;国家哲学社会科学学术期刊数据库;北大核心:【北大核心2008】；CSCD:【CSCD_E2011_2012】；

基金：国家自然科学基金资助项目资助(10771067);上海市自然科学基金资助项目资助(09ZR1407200)

语种：中文

中文关键词：组合最优化;流水作业;在线算法;可中断;竞争比

外文关键词：combinatorial optimization; flow shop; online algorithm; preemptive; competitive ratio

摘要：本文研究了可中断的二台机器流水作业排序问题,目标函数为最小化最大完工时间,工件实时到达,工件信息在工件到达之前不可知。我们给出了该在线问题的下界,并对问题中只有两个到达时间的特殊情况给出了3/2竞争的在线算法。
We investigate the problem of online preemptive scheduling of two-machine flow shops with the objective of minimizing the makespan.Jobs arrive independently over time and the information of a job is not known until its arrival.We present a lower bound of the problem.For the special case with only two arrival times we provide a algorithm which is-3/2 competitive.