Preemptive semi-on-line scheduling on two identical machines with rejection(一个可中断两台可拒绝同型机半在线排序问题)
| Autor: | MINXiao(闵啸), ZHANGYu-cai(张玉才) |
|---|---|
| Jazyk: | čínština |
| Rok vydání: | 2007 |
| Předmět: | |
| Zdroj: | Zhejiang Daxue xuebao. Lixue ban, Vol 34, Iss 5, Pp 509-514 (2007) |
| Druh dokumentu: | article |
| ISSN: | 1008-9497 |
| Popis: | 讨论一个两台可拒绝同型机半在线排序问题的近似算法.设有两台同型机，工件逐个到达，可以被接收加工，消耗一定的加工时同tj，也可以被拒绝，但要付出一定的罚值pj，目标是使被加工工件集的最大完工时间(makespan)和被拒绝工件集的罚值之和最小.此外，进一步假定每个工件的罚值和加工长度事先形成固定的比例α∈[0, +∞), 即pj=atj，针对工件加工可中断情形，设计出近似算法PRH，证明其竞争比.同时又给出该问题的下界，它们均为α的分段函数，且算法PRH在达到最优. |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|