Semi on-line preemptive scheduling on two uniform machines with rejection(两台可中断同类机可拒绝半在线排序问题的近似算法)
研究一个两台同类机可拒绝半在线排序问题,机器速度一个为1,另一个为s∈[1, +∞),加工允许中断.当工件到达时,可以将其接受加工,占用一定的机器负荷,也可以将其拒绝,付出相应的罚值,目标为使被接受工件集产生的makespan和被拒绝工件集的总罚值之和最小.问题进一步假定每个工件在选择是否加工时有两个拒绝尺度,各自独立决策,最后选择较好的结果作为最终输出.笔者设计了算法H,得到其关于s的参数竞争比为,优于只有一个拒绝尺度的经典情形.最后又给出问题的一个下界,上下界的最大差距在s=1时达到0.167....
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Zhejiang University Press
2010-09-01
|
| Series: | Zhejiang Daxue xuebao. Lixue ban |
| Subjects: | |
| Online Access: | https://doi.org/10.3785/j.issn.1008-9497.2010.05.009 |
| _version_ | 1797236145481842688 |
|---|---|
| author | MINXiao(闵啸) LIUJing(刘静) WANGYu-qing(王玉青) |
| author_facet | MINXiao(闵啸) LIUJing(刘静) WANGYu-qing(王玉青) |
| author_sort | MINXiao(闵啸) |
| collection | DOAJ |
| description | 研究一个两台同类机可拒绝半在线排序问题,机器速度一个为1,另一个为s∈[1, +∞),加工允许中断.当工件到达时,可以将其接受加工,占用一定的机器负荷,也可以将其拒绝,付出相应的罚值,目标为使被接受工件集产生的makespan和被拒绝工件集的总罚值之和最小.问题进一步假定每个工件在选择是否加工时有两个拒绝尺度,各自独立决策,最后选择较好的结果作为最终输出.笔者设计了算法H,得到其关于s的参数竞争比为,优于只有一个拒绝尺度的经典情形.最后又给出问题的一个下界,上下界的最大差距在s=1时达到0.167. |
| first_indexed | 2024-04-24T16:59:12Z |
| format | Article |
| id | doaj.art-6782de6cae2542789606c44a02b4ae7f |
| institution | Directory Open Access Journal |
| issn | 1008-9497 |
| language | zho |
| last_indexed | 2024-04-24T16:59:12Z |
| publishDate | 2010-09-01 |
| publisher | Zhejiang University Press |
| record_format | Article |
| series | Zhejiang Daxue xuebao. Lixue ban |
| spelling | doaj.art-6782de6cae2542789606c44a02b4ae7f2024-03-29T01:58:28ZzhoZhejiang University PressZhejiang Daxue xuebao. Lixue ban1008-94972010-09-0137551952310.3785/j.issn.1008-9497.2010.05.009Semi on-line preemptive scheduling on two uniform machines with rejection(两台可中断同类机可拒绝半在线排序问题的近似算法)MINXiao(闵啸)0LIUJing(刘静)1WANGYu-qing(王玉青)2Department of Mathematics and Information Engineering, Jiaxing College, Jiaxing 314001, Zhejiang Province, China(嘉兴学院数学与信息工程学院，浙江 嘉兴 314001)Department of Mathematics and Information Engineering, Jiaxing College, Jiaxing 314001, Zhejiang Province, China(嘉兴学院数学与信息工程学院，浙江 嘉兴 314001)Department of Mathematics and Information Engineering, Jiaxing College, Jiaxing 314001, Zhejiang Province, China(嘉兴学院数学与信息工程学院，浙江 嘉兴 314001)研究一个两台同类机可拒绝半在线排序问题,机器速度一个为1,另一个为s∈[1, +∞),加工允许中断.当工件到达时,可以将其接受加工,占用一定的机器负荷,也可以将其拒绝,付出相应的罚值,目标为使被接受工件集产生的makespan和被拒绝工件集的总罚值之和最小.问题进一步假定每个工件在选择是否加工时有两个拒绝尺度,各自独立决策,最后选择较好的结果作为最终输出.笔者设计了算法H,得到其关于s的参数竞争比为,优于只有一个拒绝尺度的经典情形.最后又给出问题的一个下界,上下界的最大差距在s=1时达到0.167.https://doi.org/10.3785/j.issn.1008-9497.2010.05.009同类机半在线可拒绝竞争比 |
| spellingShingle | MINXiao(闵啸) LIUJing(刘静) WANGYu-qing(王玉青) Semi on-line preemptive scheduling on two uniform machines with rejection(两台可中断同类机可拒绝半在线排序问题的近似算法) Zhejiang Daxue xuebao. Lixue ban 同类机 半在线 可拒绝 竞争比 |
| title | Semi on-line preemptive scheduling on two uniform machines with rejection(两台可中断同类机可拒绝半在线排序问题的近似算法) |
| title_full | Semi on-line preemptive scheduling on two uniform machines with rejection(两台可中断同类机可拒绝半在线排序问题的近似算法) |
| title_fullStr | Semi on-line preemptive scheduling on two uniform machines with rejection(两台可中断同类机可拒绝半在线排序问题的近似算法) |
| title_full_unstemmed | Semi on-line preemptive scheduling on two uniform machines with rejection(两台可中断同类机可拒绝半在线排序问题的近似算法) |
| title_short | Semi on-line preemptive scheduling on two uniform machines with rejection(两台可中断同类机可拒绝半在线排序问题的近似算法) |
| title_sort | semi on line preemptive scheduling on two uniform machines with rejection 两台可中断同类机可拒绝半在线排序问题的近似算法 |
| topic | 同类机 半在线 可拒绝 竞争比 |
| url | https://doi.org/10.3785/j.issn.1008-9497.2010.05.009 |
| work_keys_str_mv | AT minxiaomǐnxiào semionlinepreemptiveschedulingontwouniformmachineswithrejectionliǎngtáikězhōngduàntónglèijīkějùjuébànzàixiànpáixùwèntídejìnshìsuànfǎ AT liujingliújìng semionlinepreemptiveschedulingontwouniformmachineswithrejectionliǎngtáikězhōngduàntónglèijīkějùjuébànzàixiànpáixùwèntídejìnshìsuànfǎ AT wangyuqingwángyùqīng semionlinepreemptiveschedulingontwouniformmachineswithrejectionliǎngtáikězhōngduàntónglèijīkějùjuébànzàixiànpáixùwèntídejìnshìsuànfǎ |