哈尔滨工业大学学报
哈爾濱工業大學學報
합이빈공업대학학보
JOURNAL OF HARBIN INSTITUTE OF TECHNOLOGY
2008年
5期
836-840
,共5页
同类机%半在线%竞争比
同類機%半在線%競爭比
동류궤%반재선%경쟁비
研究了已知总加工时间的两台同类机半在线问题.假设工件是分别独立地到达加工机器,并且工件的总加工时间是已知的,目标函数为极大化最小机器负载.将总加工时间标准化后,给出近似算法及其竞争比,并证明此竞争比是紧的.给出此问题竞争比的一个下界1.6180,并由此推出当两台机器的速度比为1.6180时,算法是最优的,算法的竞争比与最优算法的竞争比之差小于0.089.
研究瞭已知總加工時間的兩檯同類機半在線問題.假設工件是分彆獨立地到達加工機器,併且工件的總加工時間是已知的,目標函數為極大化最小機器負載.將總加工時間標準化後,給齣近似算法及其競爭比,併證明此競爭比是緊的.給齣此問題競爭比的一箇下界1.6180,併由此推齣噹兩檯機器的速度比為1.6180時,算法是最優的,算法的競爭比與最優算法的競爭比之差小于0.089.
연구료이지총가공시간적량태동류궤반재선문제.가설공건시분별독입지도체가공궤기,병차공건적총가공시간시이지적,목표함수위겁대화최소궤기부재.장총가공시간표준화후,급출근사산법급기경쟁비,병증명차경쟁비시긴적.급출차문제경쟁비적일개하계1.6180,병유차추출당량태궤기적속도비위1.6180시,산법시최우적,산법적경쟁비여최우산법적경쟁비지차소우0.089.