|
|||||
|
|
| 无限批量调度中最小化加权完工时间和问题的一个线性时间近似方案 | |
| 引用本文： | 李曙光,李国君,赵浩.无限批量调度中最小化加权完工时间和问题的一个线性时间近似方案[J].运筹学学报,2004,8(4):27-32. |
| 作者姓名： | 李曙光 李国君 赵浩 |
| 作者单位： | 1. 烟台大学数学与信息科学系,烟台,264005 2. 中国科学院软件研究所,北京,100080;山东大学数学与系统科学学院,济南,250100 3. 山东大学计算机科学与技术学院,济南,250100 |
| 基金项目： | ThisworkwassupportedbythefundfromNSFCunderfundnumbers10271065 60373025 |
| 摘 要： | 本文考虑n个工件的无限批量机器调度问题．一台机器可以同时加工B≥n个工件．每个工件具有一个正权因子、一个释放时间和一个加工时间．一个批次的加工时间是该批次所包含所有工件的加工时间的最大者．在同一批次中加工的工件有相同的完工时间，即它们的共同开始时间加上该批次的加工时间．对于最小化加权完工时间和问题，本文给出了第一个多项式时间近似方案(PTAS)．对任意给定精度，该算法的运行时间为线性的． |
| 关 键 词： | 完工时间 近似 线性 加工时间 加权 调度问题 多项式时间 批次 最小化 批量 |
A Linear Time Approximation Scheme for Minimizing Total Weighted Completion Time of Unbounded Batch Scheduling |
|
| Abstract.A Linear Time Approximation Scheme for Minimizing Total Weighted Completion Time of Unbounded Batch Scheduling[J].OR Transactions,2004,8(4):27-32. | |
| Authors: | Abstract |
| Abstract: | We study the unbounded batch machine scheduling of n jobs. A batch machine canhandle up to B ≥ n jobs simultaneously. Each job is characterized by a positive weight,a release time and a processing time. The processing time of a batch is the longestprocessing time among jobs in the batch. Jobs processed in the same batch have thesame completion time, i.e., their common starting time plus the processing time of thebatch. Our goal is to find a schedule for the jobs so that the total weighted completiontime is minimized. We present the first polynomial time approximation scheme (PTAS)that runs in linear time for any fixed accuracy. |
| Keywords: | OR approximation algorithms unbounded batch scheduling release times total weighted completion time linear time approximation scheme |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |