Multiple order pick sequencing in a carousel system: A solvable case of the rural postman problem. (English) Zbl 0873.90040

Summary: We consider the problem of sequencing picks in a set of orders on a single carousel. First we consider the situation in which the sequence of the orders is given. For this problem we present an efficient dynamic programming algorithm. Second, we consider the problem without a given order sequence. We simplify this problem to a Rural Postman Problem on a circle and solve this problem to optimality. Finally, we show that the solution of the Rural Postman Problem requires at most 1.5 revolutions more than a lower bound of an optimum solution to the original problem.


90B30 Production models
90C39 Dynamic programming
90B35 Deterministic scheduling theory in operations research
Full Text: DOI