loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Proceedings of the 41st Annual Hawaii International Conference on System Sciences (HICSS 2008)
Waikoloa, Big Island, Hawaii
January 07-January 10
ISBN: 0-7695-3075-3
We consider here the one-machine serial batching problem under weighted average completion. This problem is known to be NP-hard and to date no approximation algorithm exists. Batching has wide application in manufacturing, decision management, and scheduling in information technology. In this paper, we give the first approximation algorithm for the problem. The algorithm has an approximation ratio of 2 and is a priority algorithm, which batches jobs in decreasing order of priority. We also give a lower bound of (2+ √6) /4 ≈ 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.
Citation:
Wolfgang Bein, John Noga, Jeffrey Wiegley, "Priority Approximation for Batching," hicss, pp.477, Proceedings of the 41st Annual Hawaii International Conference on System Sciences (HICSS 2008), 2008
Usage of this product signifies your acceptance of the Terms of Use.