ONLINE AND SEMI-ONLINE SCHEDULING ON CAPACITATED TWO-PARALLEL MACHINES

An Zhang (), Yiwei Jiang () and Zhiyi Tan ()
Additional contact information
An Zhang: Department of Mathematics, Zhejiang University, Hangzhou 310027, P. R. China
Yiwei Jiang: Key Laboratory of Advanced Textile Materials and Manufacturing Technology, Zhejiang Sci-Tech University, Hangzhou 310018, P. R. China
Zhiyi Tan: Department of Mathematics, State Key Lab of CAD & CG, Zhejiang University, Hangzhou 310027, P. R. China

Asia-Pacific Journal of Operational Research (APJOR), 2011, vol. 28, issue 02, 163-182

Abstract: In this paper, we investigate the capacitated two-parallel machines scheduling problem, where one machine is only available for a special period of time after which it can no longer process any job while the other machine is continuously available. Our objective is to minimize the completion time of the machine which is continuously available. The offline version of the problem is equivalent to the minimization version of the Subset-Sum problem. We first show the lower bound of the online version is infinite. We also consider the semi-online version with known the total job processing time in advance, for which both lower bound and semi-online algorithms are given.

Keywords: Scheduling; design and analysis of algorithm; competitive analysis (search for similar items in EconPapers)
Date: 2011
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595911003119
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:28:y:2011:i:02:n:s0217595911003119

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595911003119

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().