Regular PapersNo Access

Online Order Scheduling Problem with the Same Order Size on Two Identical Machines

Qian Cao

College of Economics and Management, Shanghai University of Electric Power, Shanghai 201399, P. R. China

E-mail Address: qcao@shiep.edu.cn

Corresponding author.

Search for more papers by this author

Yi Li

Antai College of Economics and Management, Shanghai Jiao Tong University, Shanghai 200030, P. R. China

E-mail Address: liyish@sjtu.edu.cn

Search for more papers by this author

, and

Guohua Wan

Antai College of Economics and Management, Shanghai Jiao Tong University, Shanghai 200030, P. R. China

E-mail Address: ghwan@sjtu.edu.cn

Search for more papers by this author

https://doi.org/10.1142/S0217595917500063Cited by:0 (Source: Crossref)

Abstract

In this paper, we consider an online order scheduling problem with the same order size on two identical machines. The objective is to minimize the makespan. An order list $O = (O_{1}, O_{2}, \dots, O_{b})$ is given, where $b$ is a positive integer. For the problem under study, we assume that $b \geq B$ ( $B = 2, 3, 4, \dots$ ), that is to say, at least $B$ orders arrive. A lower bound $\frac{B + 2}{B + 1}$ for $b \geq B$ is obtained. Also, we design two optimal algorithms $A_{1}$ and $A_{2}$ for $B = 2 m$ and $B = 2 m + 1$ ( $m = 1, 2, 3, \dots$ ), respectively.

Keywords:

References

Azar, Y and O Regev (2001). Online bin stretching. Theoretical Computer Science, 268, 17–41. Crossref, Web of Science, Google Scholar
Cao, Q, ZH Liu and TCE Cheng (2011). Semi-online scheduling with known partial information about job sizes on two identical machines. Theoretical Computer Science, 412, 3731–3737. Crossref, Web of Science, Google Scholar
Epstein, L (2003). Bin stretching revisited. Acta Informatica, 39, 97–117. Crossref, Web of Science, Google Scholar
Faigle, U, W Kern and G Turan (1989). On the performance of online algorithms for partition problems. Acta Cybernetica, 9, 107–119. Google Scholar
Graham, RL (1966). Bounds for certain multiprocessor anomalies. Bell Systems Technical Journal, 45, 1563–1581. Crossref, Web of Science, Google Scholar
He, Y and GC Zhang (1999). Semi on-line scheduling on two identical machines. Computing, 62, 179–187. Crossref, Web of Science, Google Scholar
Seiden, S, J Sgall and G Woeginger (2000). Semi-online scheduling with decreasing job sizes. Operations Research Letters, 27, 215–227. Crossref, Web of Science, Google Scholar
Tan, ZY and Y He (2002). Semi-online problems on two identical machines with combined partial information. Operations Research Letters, 30, 408–414. Crossref, Web of Science, Google Scholar