A Flexible On-line Scheduling Algorithm for Batch Machine with Infinite Capacity

被引：3

作者：

Chung Keung Poon

Wenci Yu

机构：

[1] City University of Hong Kong,Department of Computer Science

[2] East China University of Science and Technology,Institute of Applied Mathematics

来源：

Annals of Operations Research | 2005年 / 133卷

关键词：

scheduling; batch; makespan; on-line; unbounded capacity;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

We study on-line scheduling on a batch machine with infinite capacity. We present a flexible on-line scheduling algorithm that aims at minimizing the makespan and achieves the optimal competitive ratio of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$(1+\sqrt{5})/2$\end{document}.

引用

页码：175 / 181

页数：6

共 15 条

[1]

Brucker P.(1998)Scheduling a Batching Machine Journal of Scheduling 1 31-54

[2]

Gladky A.(1992)Efficient Algorithms for Scheduling Semiconductor Burn-in Operations Operations Research 40 764-775

[3]

Hoogeveen H.(2000)Scheduling One Batch Processor Subject to Job Release Dates Discrete Applied Mathematics 105 129-136

[4]

Kovalyov M.Y.(2001)On-line Algorithms for Minimizing Makespan on Batch Processing Machines Naval Research Logistics 48 241-258

[5]

Potts C.N.(undefined)undefined undefined undefined undefined-undefined

[6]

Tautenhahn T.(undefined)undefined undefined undefined undefined-undefined

[7]

van Velde S.L.(undefined)undefined undefined undefined undefined-undefined

[8]

Lee C.Y.(undefined)undefined undefined undefined undefined-undefined

[9]

Uzsoy R.(undefined)undefined undefined undefined undefined-undefined

[10]

Martin Vega L.A.(undefined)undefined undefined undefined undefined-undefined

← 1 2 →