Finding ideal utilization of rentable items in ruby

Question

# Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec
rentable_items = [ 
  %w(x x x - - - x x x - - -), # item1
  %w(- - - - - - - - - - - -), # item2
  %w(x x x x x x x - - - - -), # item3
  %w(x x x - - - - x x x x x) ]# item4

Ok,given that data-structure (which represents rent-slots in months of the items) where "x" stands for not-rentable and "-" stands for rentable, i have the following question.

When I have an incoming request for the period from April till June i want the result in the following priorized order:

items = rentable_items.ideal_utilization_for("2010/03/01", "2010/06/30")
items # [item1, item2, item4] #where item4 is the worst

The idea behind this is to fill the gaps of an item first and try to produce as few new gaps as possible.

I need no complete solution, but an advice which tools (library, gem, alogrithm) are availalbe for such a problem. Exemples would be very appreciated.

[Edit: Removed the second example, to focus on the real problem.]

Answer 1

I want to get the items with the least amount of item-swaps-per-rental ... the rentals coming in one-by-one.

Then since we can't predict the future, any algorithm we give you will simply be statistical, and it'll be easy to find a case where the algorithm gives you sub-par results.

Without having to worry about rental patterns for users, or rentals we know about ahead of time, I would simply map each item to its contiguous available date-range (meaning some items will have more than one date-range), then sort by the length of each of those ranges. When a new order comes in, use the smallest date-range that completely fills the order. Remember that a date-range should get smaller as we pass through it in real time, since we don't care if the item was available a week ago.

If people are able to reserve items, wait until the day-of to assign an item to them, then assign them from shortest-to-longest.

This is of course just one answer; there are literally infinitely-many heuristics that you could apply.