A new approximation algorithm for UET-scheduling with chain-type precedence constraints
文献类型：期刊论文
| 作者 | Han, JY; Wen, JJ; Zhang, GC |
| 刊名 | COMPUTERS & OPERATIONS RESEARCH
 |
| 出版日期 | 1998-09-01 |
| 卷号 | 25期号:9页码:767-771 |
| 关键词 | precedence constraints parallel machines makespan approximation algorithm |
| ISSN号 | 0305-0548 |
| 英文摘要 | In this paper a new approximation algorithm with worst case performance ratio 3/2 is presented for the problem of scheduling unit execution time jobs on two parallel machines with the objective of minimizing the makespan where each job can be processed on only one machine and there are chain-type precedence constraints in the jobs. This result answers an open problem in Jansen et al. [Jansen, K., Woeginger, G. J. and Yu, Z., UET-Scheduling with chain-type precedence constraints. Report 277, Technische Universitat Graz, Institut fur Mathematik, Graz, Austria, 1993.]: "Does there exist a polynomial time heuristic with worst-case guarantee better than 5/3 for the problem U2Chain?". The new approximation algorithm is also applied to the problem J2\pmtn\C-max. (C) 1998 Elsevier Science Ltd. All rights reserved. |
| WOS研究方向 | Computer Science ; Engineering ; Operations Research & Management Science |
| 语种 | 英语 |
| WOS记录号 | WOS:000074574700007 |
| 出版者 | PERGAMON-ELSEVIER SCIENCE LTD |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/13739]  |
| 专题 | 中国科学院数学与系统科学研究院 |
| 通讯作者 | Han, JY |
| 作者单位 | 1.Chinese Acad Sci, Inst Appl Math, Beijing 100080, Peoples R China 2.Graz Tech Univ, Inst Math, A-8010 Graz, Austria |
| 推荐引用方式 GB/T 7714 | Han, JY,Wen, JJ,Zhang, GC. A new approximation algorithm for UET-scheduling with chain-type precedence constraints[J]. COMPUTERS & OPERATIONS RESEARCH,1998,25(9):767-771. |
| APA | Han, JY,Wen, JJ,&Zhang, GC.(1998).A new approximation algorithm for UET-scheduling with chain-type precedence constraints.COMPUTERS & OPERATIONS RESEARCH,25(9),767-771. |
| MLA | Han, JY,et al."A new approximation algorithm for UET-scheduling with chain-type precedence constraints".COMPUTERS & OPERATIONS RESEARCH 25.9(1998):767-771. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。