Name
Abstract | ||
|---|---|---|
This paper concerns the problem of scheduling jobs with unit processing time and nonidentical sizes on single or parallel identical batch machines. The objective is to minimize the total completion time of all jobs. We show that the worst-case ratio of the algorithm based on the bin-packing algorithm First Fit Increasing lies in the interval 10982,2+22 approximate to[1.3293,1.7071]\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\left[ \frac{109}{82}, \frac{2+\sqrt{2}}{2}\right] \approx [1.3293, 1.7071]$$\end{document} for the single machine case, and is no more than 6+24 approximate to 1.8536\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{6+\sqrt{2}}{4}\approx 1.8536$$\end{document} for the parallel machines case. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1007/s10878-019-00419-9 | JOURNAL OF COMBINATORIAL OPTIMIZATION |
Keywords | DocType | Volume |
Scheduling, Bin-packing, Worst-case ratio, Batch machine | Journal | 42 |
Issue | ISSN | Citations |
3 | 1382-6905 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rongqi Li | 1 | 2 | 1.75 |
| Zhiyi Tan | 2 | 270 | 27.77 |
| Qianyu Zhu | 3 | 0 | 0.34 |