|
|||||
|
|
| 极小化最大完工时间的单机分批加工问题 | |
| 引用本文： | 李曙光,杨振光,亓兴勤.极小化最大完工时间的单机分批加工问题[J].运筹学学报,2006,10(1):31-37. |
| 作者姓名： | 李曙光 杨振光 亓兴勤 |
| 作者单位： | 1. 山东大学数学与系统科学学院,济南,250100;烟台大学数学与信息科学系,烟台,264005 2. 鲁东大学数学与信息学院,烟台,264025 3. 山东大学数学与系统科学学院,济南,250100 |
| 基金项目： | Supported by the National Natural Science Foundation of China under fund numbers 10271065 and 60373025 the Science and Technology Research Key Item of the Ministry of Education of China the Science and Technology Development Foundation of Tianjin Municipal Education Commission under No.20051519. |
| 摘 要： | 本文考虑极小化最大完工时间的单机分批加工问题．设有n个工件和一台批加工机器．每个工件有一个释放时间和一个加工时间．批加工机器可以同时加工b(b |
| 关 键 词： | 运筹学 近似算法 分批加工 排序 释放时间 最大完工时间 |
| 收稿时间： | 2003-03-11 |
| 修稿时间： | 2003年3月11日 |
Minimizing Makespan in Single-Ma chine Batch Processing |
|
| Li Shuguang,Yang Zhenguang,Qi Xingqin.Minimizing Makespan in Single-Ma chine Batch Processing[J].OR Transactions,2006,10(1):31-37. | |
| Authors: | Li Shuguang Yang Zhenguang Qi Xingqin |
| Abstract: | We consider the problem of minimizing the maximum completion time (makespan)on a batch machine. In this problem, we are given n jobs and a bat ch machine. Each job is characterized by a release time and a processing time. The batch machine can process up to b (b ＜ n) jobs as a batch simultaneously. The processing time of a batch is equal to the longest processing time among all jobs in the batch. Jobs processed in the same batch have the same completion time, i.e., their common starting time plus the processmg time of the batch. We present a polynomial time approximation scheme (PTAS) for this only on the accuracy ε. The result improves the previous two PTASs for the problem. |
| Keywords: | Operation research Approximation algorithms batch processing scheduling release times makespan |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |