极小化最大完工时间的单机分批加工问题

• 作者: 亓兴勤 李曙光 杨振光
• 来源期刊: 运筹学学报
• 学科: 数学
• 关键词: 运筹学 近似算法 分批加工 排序 释放时间 最大完工时间
• 年，卷（期）: 2006,（1）
• 页码范围: 31-37
• 页数: 7页
• 分类号: O22
• 语种: 中文
• DOI: 10.3969/j.issn.1007-6093.2006.01.003

摘要

本文考虑极小化最大完工时间的单机分批加工问题.设有n个工件和一台批加工机器.每个工件有一个释放时间和一个加工时间.批加工机器可以同时加工b(b＜n)个工件.一个批次的加工时间是该批次所包含所有工件的加工时间的最大者.在同一批次中加工的工件有相同的完工时间,即它们的共同开始时间加上该批次的加工时间.对于极小化最大完工时间问题,本文给出了一个多项式时间近似方案(PTAS).该算法的总运行时间为O(nlog nC·n),C仅与精度ε有关.这一结果改进了已有的两个多项式时间近似方案.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李曙光	山东大学数学与系统科学学院	37	167	7.0	11.0
5	亓兴勤	山东大学数学与系统科学学院	8	14	2.0	3.0
6	杨振光	鲁东大学数学与信息学院	6	26	3.0	5.0