| 带服务器的三台平行机排序问题的复杂性和近似算法 |
| |
| 引用本文： | 苏纯洁,姚恩瑜.带服务器的三台平行机排序问题的复杂性和近似算法[J].高校应用数学学报(A辑),2000,15(2):229-234. |
| |
| 作者姓名： | 苏纯洁 姚恩瑜 |
| |
| 作者单位： | 浙江大学应用数学系,杭州,310027 |
| |
| 摘 要： | 讨论带有两具服务器的三台机的平行机排序问题，在这个问题的实例中，每一个工件都有一个时间长度 安装操作必须要由服务器来完成，每一个服务器在同一时刻只能安装一个工件，用三段式描述表示此问题即为Ｐ３，Ｓ２／ｓｉ＝１／Ｃｍａｘ，证明了此问题为ＮＰ－Ｃ的，分别给出了在在线和离线条件下的近似算法，并且估计了算法的最坏情况界。
|
| 关 键 词： | 复杂性 平行机 排序 近似算法 服务器 |
THE COMPLEXITY AND APPROXIMATION ALGORITHM OF THREE PARALLEL MACHINES SCHEDULING PROBLEM WITH SERVERS |
| |
| Su Chunjie,Yao Enyu.THE COMPLEXITY AND APPROXIMATION ALGORITHM OF THREE PARALLEL MACHINES SCHEDULING PROBLEM WITH SERVERS[J].Applied Mathematics A Journal of Chinese Universities,2000,15(2):229-234. |
| |
| Authors: | Su Chunjie Yao Enyu |
| |
| Abstract: | The problem of scheduling n jobs on 3 parallel identical machines which are tended by two servers is studied.In such a parallel machine system,before a machine begins processing a job,the server has to set up the machine,and then the machine can process the job on its own.The objective is to minimize the makespan.The problem is NP- C.A heuristic method under on- line and off- line conditions is developed respectively.And the worst- case bounds are given. |
| |
| Keywords: | Algorithm Complexity Worst- case Bound |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
