ISYE SEMINAR SERIES - Collecting n Items Randomly Located on a Circle

Event Details
  • Date/Time:
    • Wednesday May 8, 2002
      11:00 am - 11:59 pm
  • Location: IC 209
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
Barbara Christopher
Industrial and Systems Engineering
Contact Barbara Christopher

Summary Sentence: ISYE SEMINAR SERIES - Collecting n Items Randomly Located on a Circle

Full Summary: ISYE SEMINAR SERIES - Collecting n Items Randomly Located on a Circle

Consider n items located randomly on a circle of length 1. The locations of the items are assumed to be independent and uniformly distributed on [0,1). A picker starts at point 0, and he has to collect all the n items moving along the circle at unit speed in either direction. We study the travel time of the picker. The problem is motivated by performance analysis of carousel systems which are widely used automated warehousing systems. The travel time highly depends on the pick strategy. For example, the picker may use the 'greedy' strategy: always travel to the nearest item to be picked. This simple algorithm is often used in practice. One can also
consider so-called m-step strategies: the picker chooses the shortest route among the ones that change direction at most once after collecting at most m items. Already for small values of m, the travel time under the m-step strategies is very close to the optimal (minimal) one. It is a non-trivial problem to find the travel time distribution under the strategies mentioned above. We develop an approach based on the well-known
relations between exponential random variables and uniform spacings. We first prove two distributional identities which are of pure mathematical interest as new peculiar properties of exponentials. Using these results, we derive the travel time distribution under the 'greedy' and the m-step strategy provided 2m counterintuitive) results on collecting n items on a circle.

Additional Information

In Campus Calendar

School of Industrial and Systems Engineering (ISYE)

Invited Audience
No audiences were selected.
No keywords were submitted.
  • Created By: Barbara Christopher
  • Workflow Status: Published
  • Created On: Oct 8, 2010 - 7:43am
  • Last Updated: Oct 7, 2016 - 9:53pm