两台可中断同类机可拒绝半在线排序问题的近似算法.pdf

浙江大学学报理学版

第卷第期://..../ .
.
年月
:./.....
两台可中断同类机可拒绝半在线排序问题的近似算法
闵啸,刘静,王玉青
嘉兴学院数学与信息工程学院,浙江嘉兴
摘要:研究一个两台同类机可拒绝半在线排序问题,机器速度一个为,另一个为, 。。,
工件达时,可以将其接受加工,占用一定的机器负荷,也可以将其拒绝,付出相应的罚值,目标为使被接受工件集

度,各自独立决策,,得到其关于的参数竞争比为
, 优
;暑,上下界的最大差距在一时达到。.
关键词:同类机;半在线;可拒绝;竞争比
中图分类号: 文献标志码: 文章编号:———
,, ,
,,,
—.
,,:—
:.
∈,∞,.,
,,
.
.,—
. .
,“.。。
。.¨。。篙,。
..
:;—;;
述如下:设机器集为一,,其中的速度
引言为;工件集为一,,,⋯,,工件,带有两
个参数,,,,表示工件长度,
排序问题是组合最优化中的一类件‘,,到达后,需要立即作出决策,可以被接受加工,
重要问题,它在计算机系统控制,硬件设计,机器加消耗一定的加工时间,,进一步通过规范化,可
工制造业,生产计划调度管理等方面有着广泛的实以假定:,一∈,。。.加工允许中断—
际应用背景,在理论上它又与算法设计和计算复杂,即可将一个工件拆分成若干部分放在不
性密切相关,,但其在不同机器上的各部分在时间
论一个两台同类机可拒绝半在线排序问题,问题描上不能出现重叠;也可以被拒绝,但要付出相应的罚
收稿日期:—.
基金项目:浙江省高校优秀青年教师资助计划项目资助.
作者简介:闵啸,男,硕士,副教授,主要从事运筹学——组合优化研究
浙江大学学报理学版第卷
值,其目标是使被加工工件集的最晚完工时间
一——≈.,

型进一步在每个工件的拒绝环节上允许有两种方案于机器数为,提出算法其竞争比为,下界为
独立运行,最后选择目标较好的一种. ..对于在线的不可中断可拒绝同类机排序问题
根据事先掌握工件信息的多少,平行机排序又,文献针对机器数为和时设计出一个在
分为离线—、在线和半在线线算法,得到其关于机器速度之比≥
—.离线状况为工件信息事先完全已知,排序的参数竞争比,并且当一时在—以及≥
者可充分利用工件信息设计算法;在线为工件一个
, 当时,在≥
一个到达,当且仅当安排完当前工件后,下一个工件
才到达,且工件一经安排,不得临时改变;而日常生
在≤≤中将算法作了适当改进,并在区间
活中的实际情况往往介于这两种极端情况之间,工
件的确切信息虽然未知,但一些局部信息可事先获.,.—分别讨
取,如:工件总长度,最大工件,各工件论了一类