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 ().