Approximate algorithm of semi online scheduling on two uniform machines with a rejecting buffer(拒绝可缓冲的2台同类机半在线排序问题的近似算法)
研究了 2个拒绝可缓冲的同类机半在线排序问题.设有2台同类机M1,M2，速度分别为1和s∈[1，+ ∞),加工不允许中断，工件Jj按照列表在线到达，每个工件带有2个参数：加工长度tj、拒绝罚值pj（模型1中）或拒绝获益pj（模型2中），当工件到达时，可以被接受并分给某台机器加工，也可以被拒绝，需付出一定的罚值（模型1)或取得一定的收益（模型2），目标是在第1个模型中要求极小化机器最大负荷和拒绝工件的总罚值之和；第2个模型中要求极大化机器最小负荷和总收益之和.此外，在接受或拒绝的决策环节上提供一个缓冲区B，其容量为k≥1,任一时刻至多可以存放k个工件，当工件到达时，若缓冲区未饱和，则可暂时存入B...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Zhejiang University Press
2014-07-01
|
| Series: | Zhejiang Daxue xuebao. Lixue ban |
| Subjects: | |
| Online Access: | https://doi.org/10.3785/j.issn.1008-9497.2014.04.007 |
| _version_ | 1797235976777498624 |
|---|---|
| author | MINXiao(闵啸) LIUJing(刘静) ZHUJunlei(朱俊蕾) JIANGMing(姜明) |
| author_facet | MINXiao(闵啸) LIUJing(刘静) ZHUJunlei(朱俊蕾) JIANGMing(姜明) |
| author_sort | MINXiao(闵啸) |
| collection | DOAJ |
| description | 研究了 2个拒绝可缓冲的同类机半在线排序问题.设有2台同类机M1,M2，速度分别为1和s∈[1，+ ∞),加工不允许中断，工件Jj按照列表在线到达，每个工件带有2个参数：加工长度tj、拒绝罚值pj（模型1中）或拒绝获益pj（模型2中），当工件到达时，可以被接受并分给某台机器加工，也可以被拒绝，需付出一定的罚值（模型1)或取得一定的收益（模型2），目标是在第1个模型中要求极小化机器最大负荷和拒绝工件的总罚值之和；第2个模型中要求极大化机器最小负荷和总收益之和.此外，在接受或拒绝的决策环节上提供一个缓冲区B，其容量为k≥1,任一时刻至多可以存放k个工件，当工件到达时，若缓冲区未饱和，则可暂时存入B；若已饱和，则必须在新工件和缓冲区内工件中选择一个进行接受或拒绝的决策.本模型所研究的是经典可拒绝模型中的一个松弛问题，属半在线可拒绝模型.最后针对以上2个模型，分别给出了s在区间[1，+∞）上的近似算法，并证明了各自关于s的参数竞争比. |
| first_indexed | 2024-04-24T16:56:31Z |
| format | Article |
| id | doaj.art-e8cef137877445958f7cc7a0b2832827 |
| institution | Directory Open Access Journal |
| issn | 1008-9497 |
| language | zho |
| last_indexed | 2024-04-24T16:56:31Z |
| publishDate | 2014-07-01 |
| publisher | Zhejiang University Press |
| record_format | Article |
| series | Zhejiang Daxue xuebao. Lixue ban |
| spelling | doaj.art-e8cef137877445958f7cc7a0b28328272024-03-29T01:58:33ZzhoZhejiang University PressZhejiang Daxue xuebao. Lixue ban1008-94972014-07-0141439940510.3785/j.issn.1008-9497.2014.04.007Approximate algorithm of semi online scheduling on two uniform machines with a rejecting buffer(拒绝可缓冲的2台同类机半在线排序问题的近似算法)MINXiao(闵啸)0LIUJing(刘静)1ZHUJunlei(朱俊蕾)2JIANGMing(姜明)3 1.College of Mathematics Physics and Information Engineering, Jiaxing University, Jiaxing 314001, Zhejiang Province, China( 1.嘉兴学院数理与信息工程学院，浙江 嘉兴 314001) 1.College of Mathematics Physics and Information Engineering, Jiaxing University, Jiaxing 314001, Zhejiang Province, China( 1.嘉兴学院数理与信息工程学院，浙江 嘉兴 314001) 1.College of Mathematics Physics and Information Engineering, Jiaxing University, Jiaxing 314001, Zhejiang Province, China( 1.嘉兴学院数理与信息工程学院，浙江 嘉兴 314001) 2.Institute of Software and Technology, Hangzhou Dianzi University, Hangzhou 310018, China( 2.杭州电子科技大学软件与智能技术研究所，浙江 杭州 310018)研究了 2个拒绝可缓冲的同类机半在线排序问题.设有2台同类机M1,M2，速度分别为1和s∈[1，+ ∞),加工不允许中断，工件Jj按照列表在线到达，每个工件带有2个参数：加工长度tj、拒绝罚值pj（模型1中）或拒绝获益pj（模型2中），当工件到达时，可以被接受并分给某台机器加工，也可以被拒绝，需付出一定的罚值（模型1)或取得一定的收益（模型2），目标是在第1个模型中要求极小化机器最大负荷和拒绝工件的总罚值之和；第2个模型中要求极大化机器最小负荷和总收益之和.此外，在接受或拒绝的决策环节上提供一个缓冲区B，其容量为k≥1,任一时刻至多可以存放k个工件，当工件到达时，若缓冲区未饱和，则可暂时存入B；若已饱和，则必须在新工件和缓冲区内工件中选择一个进行接受或拒绝的决策.本模型所研究的是经典可拒绝模型中的一个松弛问题，属半在线可拒绝模型.最后针对以上2个模型，分别给出了s在区间[1，+∞）上的近似算法，并证明了各自关于s的参数竞争比.https://doi.org/10.3785/j.issn.1008-9497.2014.04.007同类机半在线可拒绝排序缓冲区竞争比 |
| spellingShingle | MINXiao(闵啸) LIUJing(刘静) ZHUJunlei(朱俊蕾) JIANGMing(姜明) Approximate algorithm of semi online scheduling on two uniform machines with a rejecting buffer(拒绝可缓冲的2台同类机半在线排序问题的近似算法) Zhejiang Daxue xuebao. Lixue ban 同类机 半在线 可拒绝 排序 缓冲区 竞争比 |
| title | Approximate algorithm of semi online scheduling on two uniform machines with a rejecting buffer(拒绝可缓冲的2台同类机半在线排序问题的近似算法) |
| title_full | Approximate algorithm of semi online scheduling on two uniform machines with a rejecting buffer(拒绝可缓冲的2台同类机半在线排序问题的近似算法) |
| title_fullStr | Approximate algorithm of semi online scheduling on two uniform machines with a rejecting buffer(拒绝可缓冲的2台同类机半在线排序问题的近似算法) |
| title_full_unstemmed | Approximate algorithm of semi online scheduling on two uniform machines with a rejecting buffer(拒绝可缓冲的2台同类机半在线排序问题的近似算法) |
| title_short | Approximate algorithm of semi online scheduling on two uniform machines with a rejecting buffer(拒绝可缓冲的2台同类机半在线排序问题的近似算法) |
| title_sort | approximate algorithm of semi online scheduling on two uniform machines with a rejecting buffer 拒绝可缓冲的2台同类机半在线排序问题的近似算法 |
| topic | 同类机 半在线 可拒绝 排序 缓冲区 竞争比 |
| url | https://doi.org/10.3785/j.issn.1008-9497.2014.04.007 |
| work_keys_str_mv | AT minxiaomǐnxiào approximatealgorithmofsemionlineschedulingontwouniformmachineswitharejectingbufferjùjuékěhuǎnchōngde2táitónglèijībànzàixiànpáixùwèntídejìnshìsuànfǎ AT liujingliújìng approximatealgorithmofsemionlineschedulingontwouniformmachineswitharejectingbufferjùjuékěhuǎnchōngde2táitónglèijībànzàixiànpáixùwèntídejìnshìsuànfǎ AT zhujunleizhūjùnlěi approximatealgorithmofsemionlineschedulingontwouniformmachineswitharejectingbufferjùjuékěhuǎnchōngde2táitónglèijībànzàixiànpáixùwèntídejìnshìsuànfǎ AT jiangmingjiāngmíng approximatealgorithmofsemionlineschedulingontwouniformmachineswitharejectingbufferjùjuékěhuǎnchōngde2táitónglèijībànzàixiànpáixùwèntídejìnshìsuànfǎ |