应用科学学报
應用科學學報
응용과학학보
JOURNAL OF APPLIED SCIENCES
2007年
5期
535-540
,共6页
半在线%同型机%竞争比%松弛
半在線%同型機%競爭比%鬆弛
반재선%동형궤%경쟁비%송이
研究半在线模型的松弛,讨论以下半在线松弛模型:已知工件最大加工时间在某一区域内(known largest job interval),分别讨论了该模型下2台同型机的极小化Cmax问题和极大化Cmin问题.对这两个问题构造pInterval算法,给出其竞争比并证明它是紧的,还分析了上述两个问题的特征和LS算法的竞争比.
研究半在線模型的鬆弛,討論以下半在線鬆弛模型:已知工件最大加工時間在某一區域內(known largest job interval),分彆討論瞭該模型下2檯同型機的極小化Cmax問題和極大化Cmin問題.對這兩箇問題構造pInterval算法,給齣其競爭比併證明它是緊的,還分析瞭上述兩箇問題的特徵和LS算法的競爭比.
연구반재선모형적송이,토론이하반재선송이모형:이지공건최대가공시간재모일구역내(known largest job interval),분별토론료해모형하2태동형궤적겁소화Cmax문제화겁대화Cmin문제.대저량개문제구조pInterval산법,급출기경쟁비병증명타시긴적,환분석료상술량개문제적특정화LS산법적경쟁비.