| 工件带到达时间和服务器的平行机排序问题复杂性和启发式算法 |
| |
| 引用本文： | 时凌. 工件带到达时间和服务器的平行机排序问题复杂性和启发式算法[J]. 湖北民族学院学报(自然科学版), 2004, 22(3): 15-18 |
| |
| 作者姓名： | 时凌 |
| |
| 作者单位： | 湖北民族学院理学院 湖北恩施445000 |
| |
| 基金项目： | 湖北省教育厅重点项目(2002X13) |
| |
| 摘 要： | 研究带到达时间和单服务器的平行机排序问题，工件在加工之前均有一定的安装时间，且所有安装时间均由单服务器来完成．证明在只有两台平行机的情况下，带到达时间和单服务器的平行机排序问题是强NP-困难的，对于有m台平行机的情况，给出一种改进的启发式算法，并证明该算法的紧界为2．
|
| 关 键 词： | 平行机排序问题 到达时间 服务器 复杂性 启发式算法 |
| 文章编号： | 1008-8423(2004)03-0015-04 |
| 修稿时间： | 2004-04-01 |
Complexity and Heuristic Algorithm for Parallel Machine Scheduling Problem with Release Times and a Single Server |
| |
| SHI Ling. Complexity and Heuristic Algorithm for Parallel Machine Scheduling Problem with Release Times and a Single Server[J]. Journal of Hubei Institute for Nationalities(Natural Sciences), 2004, 22(3): 15-18 |
| |
| Authors: | SHI Ling |
| |
| Abstract: | We discuss parallel machine scheduling problem with a single server. Before processing,each job must be loaded on a machine,which takes certain setup time.All these setups have to be done by a single server,which can handle at most one job at a time.For the two-machine case,we prove that problem is NP-hard in the strong sense even if all processing times are equal to 1.A simple heuristic algorithm is shown to create schedule with the makespan that is at most twice the optimum value for the m-machine. |
| |
| Keywords: | parallel machine complexity heuristic algorithm release time single server |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
