两台平行机的实时到达在线排序

作     者：陈仕平 张国川 CHEN SHIPING;ZHANG GUOCHUAN

作者机构：浙江大学应用数学系杭州310027 

基　　金：国家自然科学基金!19801032 

出 版 物：《应用数学学报》 (Acta Mathematicae Applicatae Sinica)

年 卷 期：2000年第23卷第1期

页      码：31-37页

摘      要：本文考虑一类新的在线平行机排序模型一实时到达在线问题．该模型中，工件是陆续到达的．工件的个数及到达时间是事先未知的，而且只有当工件到达，才知其加工时间，所求目标是使所有工件都加工完的时间达到最小．对两台平行机的情形，Ｃｈｅｎ与Ｖｅｓｔｊｅｎｓ［２］给出了近似比为３／２的在线ＬＰＴ算法，并证明不存在近似比小于（５－）／２的算法．我们利用黄金分割数设计了一个新的算法，其近似比不超过（１８－５）／１１．

主 题 词：排序 在线算法 平行机 组合最优化 实时到达 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 07[理学] 070105[070105] 0701[理学-数学类] 

核心收录：

D　O　I：10.3321/j.issn:0254-3079.2000.01.004

馆 藏 号：203942667...