competitive ratio

On-line Service Scheduling

  • Bo Chen
  • Wenxun Xing
  • Zhenbo Wang
    • Categories Approximation Algorithms, Scheduling Tags , , ,

    This paper is concerned with a scheduling problem that occurs in service systems, where customers are classified as `ordinary’ and `special’. Ordinary customers can be served on any service facility, while special customers can be served only on the flexible service facilities. Customers arrive dynamically over time and their needs become known upon arrival. We … Read more

    Batched Bin Packing

  • Gregory Gutin
  • Anders Yeo
  • Tommy Jensen
    • Categories Approximation Algorithms, Combinatorial Optimization Tags , , ,

    We introduce and study the batched bin packing problem (BBPP), a bin packing problem in which items become available for packing incrementally, one batch at a time. A batched algorithm must pack a batch before the next batch becomes known. A batch may contain several items; the special case when each batch consists of merely … Read more