带机器准备时间的两台同型机复合半在线排序问题(英文)  

A Semi-online Scheduling Problem with the Combined Partial Information on Two Identical Machines with Non-simultaneous Machine Available Times

作　　者：谭金芝[1] 

机构地区：[1]温州大学数学与信息科学学院,温州325035

出　　处：《运筹学学报》2009年第4期83-89,共7页Operations Research Transactions

基　　金：浙江省教育厅资助项目(20070524)

摘　　要：本文研究了预知两种信息,带机器准备时间的两台同型平行机复合半在线排序问题,即已知所有工件加工时间总和和工件按加工时间非增顺序到达,目标为极小化最大机器完工时间的半在线排序模型.我们分析了它的下界,并给出了竞争比为7/6的最优算法.This paper investigates a semi-online scheduling problem with combination of two types of information on two identical parallel machines with non-simultaneous machine available times. The jobs arrive sorted by non-increasing sizes and the total processing time of all jobs is known in advance, the goal is to minimize the maximum machine completion time. Its lower bound is analyzed and an optimal algorithm with competitive ratio 7/6 is presented.

关 键 词：运筹学 排序 半在线 平行机 竞争比 

分 类 号：O223[理学—运筹学与控制论] TN710.2[理学—数学]