运筹学学报
運籌學學報
운주학학보
OR TRANSACTIONS
2009年
4期
83-89
,共7页
运筹学%排序%半在线%平行机%竞争比
運籌學%排序%半在線%平行機%競爭比
운주학%배서%반재선%평행궤%경쟁비
Operations research%scheduling%semi-online%parallel machine%competitive ratio
本文研究了预知两种信息,带机器准备时间的两台同型平行机复合半在线排序问题,即已知所有工件加工时间总和和工件按加工时间非增顺序到达,目标为极小化最大机器完工时间的半在线排序模型.我们分析了它的下界,并给出了竞争比为7/6的最优算法.
本文研究瞭預知兩種信息,帶機器準備時間的兩檯同型平行機複閤半在線排序問題,即已知所有工件加工時間總和和工件按加工時間非增順序到達,目標為極小化最大機器完工時間的半在線排序模型.我們分析瞭它的下界,併給齣瞭競爭比為7/6的最優算法.
본문연구료예지량충신식,대궤기준비시간적량태동형평행궤복합반재선배서문제,즉이지소유공건가공시간총화화공건안가공시간비증순서도체,목표위겁소화최대궤기완공시간적반재선배서모형.아문분석료타적하계,병급출료경쟁비위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.
