主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
李曙光,李国君,王秀红.极小化加权完工时间和的无界批量机器并行调度问题.软件学报,2006,17(10):2063-2068
极小化加权完工时间和的无界批量机器并行调度问题
Minimizing Total Weighted Completion Time on Parallel Unbounded Batch Machines
投稿时间:2004-05-08  修订日期:2005-07-08
DOI:
中文关键词:  多项式时间近似方案  调度  无界批量并行机  加权完工时间和  释放时间
英文关键词:polynomial time approximation scheme  scheduling  parallel unbounded batch machines  total weighted completion time  release times
基金项目:Supported by the National Natural Science Foundation of China under Grant Nos.10271065,60373025(国家自然科学基金);the Science and Technology Development Foundation of Tianjin Municipal Education Commission of China under Grant No.20051519(天津市教委科技发展基金)
作者单位
李曙光 山东大学,数学与系统科学学院,山东,济南,250100
烟台大学,数学与信息科学系,山东,烟台,264005 
李国君 山东大学,数学与系统科学学院,山东,济南,250100
烟台大学,数学与信息科学系,山东,烟台,264005 
王秀红 鲁东大学,数学与信息学院,山东,烟台,264025 
摘要点击次数: 3170
全文下载次数: 2824
中文摘要:
      考虑无界批量机器并行调度中极小化加权完工时间和问题.设有n个工件和m台批加工同型机.每个工件具有一个正权因子、一个释放时间和一个加工时间.每台机器可以同时加工Bn个工件.一个批次的加工时间是该批次所包含的所有工件的加工时间的最大者.在同一批次中加工的工件有相同的完工时间,即它们的共同开始时间加上该批次的加工时间.给出了一个多项式时间近似方案(PTAS).
英文摘要:
      This paper considers the problem of scheduling n jobs on m parallel unbounded batch machines to minimize the total weighted completion time. Each job is characterized by a positive weight, a release time and a processing time. Each unbounded batch machine can process up to B (Bn) jobs as a batch simultaneo usly. The processing time of a batch is the longest processing time among jobs in the batch. Jobs processed in the same batch have the same completion time, I.e., their common starting time plus the processing time of the batch. A polynomial time approximation scheme (PTAS) for this problem is presented.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利