运筹学学报 >
2019 , Vol. 23 >Issue 1: 111 - 118
DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2019.01.013
工件满足一致性的同类机在线分批排序问题
收稿日期: 2017-12-18
网络出版日期: 2019-03-15
基金资助
国家自然科学基金（Nos.11771251，71771138，71672166，71804089），山东省自然科学基金（No.ZR2017MG009），泰山学者工程专项经费
Online batch scheduling problem on uniform machines with agreeable processing times
Received date: 2017-12-18
Online published: 2019-03-15
研究了工件满足一致性，批容量无界的两台同类机在线分批排序问题，目标为极小化工件的最大完工时间和极小化工件的最大流程时间，三元素法分别表示为Q2|ri < rj⇒ pi ≤ pj，B=∞，on-line|Cmax，Q2|ri < rj⇒ pi ≥ pj，B=∞，on-line|Fmax.不失一般性，假设第一台机器速度为1，第二台机器速度为s，s ≥ 1.对于上述两类问题设计了一个在线算法，并分析了算法竞争比的上界.对第一类问题该在线算法的竞争比不超过s+α，这里α为α2+sα-1=0的正根，特别地，当s=1时，该算法的竞争比不超过1.618.对第二类排序问题，该在线算法的竞争比不超过1+1/α.
彭南南, 张玉忠, 柏庆国, 王成飞 . 工件满足一致性的同类机在线分批排序问题[J]. 运筹学学报, 2019 , 23(1) : 111 -118 . DOI: 10.15960/j.cnki.issn.1007-6093.2019.01.013
We study the online batch scheduling problem on two uniform machines, where the batch capacity is unbounded. When the arrival times and the processing times of jobs are agreeable, two scheduling models whose objectives are to minimize the makespan and flow-time are developed and they are expressed as Q2|ri < rj⇒ pi ≤ pj, B=∞, on-line|Cmax and Q2|ri < rj⇒ pi ≥ pj, B=∞, on-line|Fmax. Without loss of generality, the speeds of the two machines are assumed to be 1 and s,s ≥ 1. We propose an on-line algorithm and prove the competitive ratios of the algorithm are not more than s+α and 1+1/α, respectively, where α is the positive root of α2+sα-1=0. Moreover, for the former scheduling model, we prove that the competitive ratio of the algorithm is not more than 1.618, when s=1.
[1] Zhang G C, Cai X Q, Wong C K. On-line algorithm for minimizing makespan on batch processing machines[J]. Naval Research Logistics, 2001, 48(3):241-258.
[2] Ridouard F, Ricard P, Marineau P. On-line scheduling on a batch processing machine with unbounded batch size to minimizing the makespan[J]. European Journal of Operation Research, 2008, 189(3):1327-1342.
[3] 焦成文, 李文华. 工件按加工长度不增序到达的最小化最大流程在线分批排序[J]. 运筹学学报, 2013, 17(4):96-102.
[4] 王成飞, 张玉忠. 提前预知信息的在线分批排序问题[J]. 运筹学学报, 2016, 20(1):84-90.
[5] 张玉忠, 柏庆国, 徐健腾. 工件有尺寸且分两批到达的单机分批排序[J]. 运筹学报, 2006, 10(4):99-105.
[6] Fu R Y, Cheng T C E, Ng C T, et al. An optimal online algorithm for single parallel-batch machine scheduling with incompatible job families to minimize makespan[J]. Operations Research Letters, 2013, 41(3):216-219.
[7] Li W J. A best possible online algorithm for the parallel-machine scheduling to minimize the maximum weighted completion time[J]. Asia-Pacific Journal of Operational Research, 2015, 32(4):1-10.
[8] Li W H, Gao J, Yuan J J. Online-list scheduling on a single bounded parallel-batch machine to minimize makespan[J]. Asia-Pacific Journal of Operational Research, 2015, 32(4):1-15.
[9] Liu P H, Lu X W, Fang Y. A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines[J]. Journal of Scheduling, 2012, 15(1):77-81.
[10] Liu P H, Lu X W. Online unbounded batch scheduling on parallel machines with delivery times[J]. Journal of Combinatorial Optimization, 2015, 29(1):228-236.
[11] Liu H L, Yuan J J, Li W J. Online scheduling of equal length jobs on unbounded parallel batch processing machines with limited restart[J]. Journal of Combinatorial Optimization, 2016, 31(4):1609-1622.
[12] Zhou H, Jiang Y W, Zhou P. Total completion time minimization scheduling on two hierarchical uniform machines[J]. Theoretical Computer Science, 2017, 702:65-76.
[13] Cao Q, Liu Z H. Semi-online scheduling with bounded job sizes on two uniform machines[J].Theoretical Computer Science, 2016, 652:1-17.
[14] Deng X T, Poon C K, Zhang Y Z. Approximation algorithms in batch processing[J]. Journal of Combinatorial Optimization, 2003, 7(3):247-257.
[15] Zhang G C, Cai X Q, Wong C K. Optimal on-line algorithms for scheduling on parallel batch processing machines[J]. ⅡE Transactions, 2003, 35(2):175-181.
[16] Ma R, Wan L, Wei L J, et al. Online bounded-batch scheduling to minimize total weighted completion time on parallel machines[J]. International Journal of Production Economics, 2014, 156:31-38.
/
| 〈 |
|
〉 |
