| 机器带准备时间的平行机分批排序 |
| |
| 引用本文： | 孙志慧,刘明诚,张咸召.机器带准备时间的平行机分批排序[J].洛阳大学学报,2006,21(4):31-34. |
| |
| 作者姓名： | 孙志慧 刘明诚 张咸召 |
| |
| 作者单位： | 1. 曲阜师范大学,运筹与管理学院,山东,日照,276826
2. 黄岛六中,山东,青岛,266500 |
| |
| 基金项目： | 国家自然科学基金资助项目（项目编号：10671108）,山东省自然科学基金资助项目（项目编号：Y2005A04） |
| |
| 摘 要： | 首次研究了机器带准备时间的平行机上的分批排序问题,这里的目标函数为极小化工件的最大完工时间,这类问题是NP-难的.我们根据FBLPT算法、Multifit算法和LPT算法,分别对机器是同型机和同类机的两种情形设计出两个近似算法,并证明它们的最差性能比分别不超过(2-1B)97 (12)k]和53(2-1B).
|
| 关 键 词： | 分批排序 带准备时间 最差性能比 同型机 同类机 |
| 文章编号： | 1007-113X（2006）04-0031-04 |
| 收稿时间： | 2006-08-29 |
| 修稿时间： | 2006年8月29日 |
Scheduling Parallel Batch Processing Machines With Non-indentical Job Sizes |
| |
| SUN Zhi-hui,LIU Ming-cheng,ZHANG Xian-zhao.Scheduling Parallel Batch Processing Machines With Non-indentical Job Sizes[J].Journal of Luoyang University,2006,21(4):31-34. |
| |
| Authors: | SUN Zhi-hui LIU Ming-cheng ZHANG Xian-zhao |
| |
| Abstract: | The problems of scheduling jobs with non-simultaneous machine available time on parallel identical and uniform batch processing machines to minimize the makespans are considered.Two heuristic agorithms A and A_1 is provided,and prove that their performance ratios are not more than(2-1B)97 (12)~k] and 53(2-1B)are proved. |
| |
| Keywords: | batching scheduling non-simultaneous worst-case performance ratio approximation algorithm Identical machine uniform machine |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
