Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(4)
Batch Process
Online Algorithm
Online Scheduling
Longest Processing Time
Subscribe
Academic
Publications
Optimal Semionline Algorithm for Scheduling on a Batch Processing Machine
Optimal Semionline Algorithm for Scheduling on a Batch Processing Machine,10.1007/9783642020261_32,Ming Liu,Yinfeng Xu,Chengbin Chu,Lu Wang
Edit
Optimal Semionline Algorithm for Scheduling on a Batch Processing Machine
BibTex

RIS

RefWorks
Download
Ming Liu
,
Yinfeng Xu
,
Chengbin Chu
,
Lu Wang
We consider two semionline scheduling problems on a single batch (processing) machine with jobs’ nondecreasing processing times and jobs’ nonincreasing processing times, respectively. Our objective is to minimize the makespan. A batch processing machine can handle up to B jobs simultaneously. We study an unbounded model where B = ∞. The jobs that are processed together construct a batch, and all jobs in a batch start and complete at the same time. The processing time of a batch is given by the
longest processing time
of any job in the batch. Jobs arrive over time. Let p j denote the processing time of job J j . Given job J j and its following job J j + 1, we assume that p j + 1 ≥ αp j , where α ≥ 1 is a constant number, for the first problem with jobs’ nondecreasing processing times. For the second problem, we assume that p j + 1 ≤ αp j , where 0 α \fracÖ{a</font >2+4}</font >a</font >2+1\frac{\sqrt{\alpha^2+4}\alpha}{2}+1 for the first problem and \fracÖ{4a</font >+1}+12\frac{\sqrt{4\alpha+1}+1}{2} for the second problem.
Conference:
Conference on Combinatorial Optimization and Applications  COCOA
, pp. 346353, 2009
DOI:
10.1007/9783642020261_32
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
dx.doi.org
)
(
www.informatik.unitrier.de
)
More »
References
(11)
Online computation and competitive analysis
(
Citations: 999
)
Allan Borodin
,
Ran ElYaniv
Published in 1998.
Approximation Algorithms in Batch Processing
(
Citations: 25
)
Xiaotie Deng
,
Chung Keung Poon
,
Yuzhong Zhang
Conference:
International Symposium on Algorithms and Computation  ISAAC
, pp. 153162, 1999
Online scheduling on a batch machine to minimize makespan with limited restarts
(
Citations: 4
)
Ruyan Fu
,
Ji Tian
,
Jinjiang Yuan
,
Cheng He
Journal:
Operations Research Letters  ORL
, vol. 36, no. 2, pp. 255258, 2008
Online Scheduling
(
Citations: 41
)
Unknown
Published in 2008.
Minimizing makespan on a single batch processing machine with dynamic job arrivals
(
Citations: 89
)
C.Y. LEE
Journal:
International Journal of Production Research  INT J PROD RES
, vol. 37, no. 1, pp. 219236, 1999