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 |