An infinite server system with general packing constraints

We consider a service system with multiple classes of input requests (customers). Each server can serve multiple customers simultaneously, subject to certain packing constraints, specifying which server packing configurations k are allowed. Service times of different customers are independent; after a service completion, each customer leaves its server (and the system). Each new arriving customer is placed for service immediately; it can be placed into a server already serving other customers (as long as packing constraints are not violated), or to an idle server. We consider a simple parsimonious real-time 1+ algorithm, called Greedy, which attempts to minimize the increment of the objective function k Xk , > 0, caused by each new assignment; here Xk is the number of servers in configuration k. Our main results show that certain versions of the Greedy algorithm are asymptotically optimal, in the sense of 1+ in stationary regime, as the input flow rates grow to infinity. minimizing k Xk