Academic Journals Database
Disseminating quality controlled scientific knowledge

Approximation for Batching via Priorities

ADD TO MY LIST
 
Author(s): W. Bein | J. Noga | J. Wiegley

Journal: Scientific Annals of Computer Science
ISSN 1843-8121

Volume: 17;
Start page: 1;
Date: 2007;
VIEW PDF   PDF DOWNLOAD PDF   Download PDF Original page

ABSTRACT
We consider here the one-machine serial batching problem under weighted average completion. This problem is known to be $cal Ncal P$-hard and no good approximation algorithms are known. Batching has wide application in manufacturing, decision management, and scheduling in information technology.We give an approximation algorithm with approximation ratio of $2$; the algorithm is a priority algorithm, which batches jobs in decreasing order of priority. We also give a lower bound of $frac{2 +sqrt{6}}{4} approx 1.1124$ on the approximation ratio of any priority algorithm and conjecture that there is a priority algorithm which matches this bound. Adaptive algorithm experiments are used to support the conjecture. An easier problem is the list version of the problem where the order of the jobs is given. We give a new linear time algorithm for the list batching problem.
Save time & money - Smart Internet Solutions      Why do you need a reservation system?