系统科学与数学
繫統科學與數學
계통과학여수학
JOURNAL OF SYSTEMS SCIENCE AND MATHEMATICAL SCIENCES
2009年
10期
1381-1389
,共9页
实例转换%在线调度%竞争分析%单机调度%总加权完工时间
實例轉換%在線調度%競爭分析%單機調度%總加權完工時間
실례전환%재선조도%경쟁분석%단궤조도%총가권완공시간
针对工件动态到达的在线调度模型提出了一种基于实例转换的竞争分析方法,该方法从问题的一个任意实例出发,逐步沿着性能比增加的方向修改工件的各种参数而得到结构更加简单特殊的实例,最后所导出的简单实例的性能比可以直接计算,且是算法竞争比的一个上界.该方法为在线调度算法的竞争比分析提供了一种新颖的、规律性的思路,以最小化总加权完工时间的单机在线调度问题为例,使用提出的分析方法为该问题一个已有的竞争分析结论提供了更加简洁明了的替代性证明.
針對工件動態到達的在線調度模型提齣瞭一種基于實例轉換的競爭分析方法,該方法從問題的一箇任意實例齣髮,逐步沿著性能比增加的方嚮脩改工件的各種參數而得到結構更加簡單特殊的實例,最後所導齣的簡單實例的性能比可以直接計算,且是算法競爭比的一箇上界.該方法為在線調度算法的競爭比分析提供瞭一種新穎的、規律性的思路,以最小化總加權完工時間的單機在線調度問題為例,使用提齣的分析方法為該問題一箇已有的競爭分析結論提供瞭更加簡潔明瞭的替代性證明.
침대공건동태도체적재선조도모형제출료일충기우실례전환적경쟁분석방법,해방법종문제적일개임의실례출발,축보연착성능비증가적방향수개공건적각충삼수이득도결구경가간단특수적실례,최후소도출적간단실례적성능비가이직접계산,차시산법경쟁비적일개상계.해방법위재선조도산법적경쟁비분석제공료일충신영적、규률성적사로,이최소화총가권완공시간적단궤재선조도문제위례,사용제출적분석방법위해문제일개이유적경쟁분석결론제공료경가간길명료적체대성증명.
