Warehouse scheduling is the problem of sequencing re- quests for products
Warehouse scheduling is the problem of sequencing re- quests for products (i.e., customer orders) so as to min- imize the average time required to fill an order and the amount of product left in inventory. Product can be taken from the warehouse or directly from the production line. The time required to fill an order depends on whether product comes from the production line or whether prod- uct must be move out of inventory. Moving from inventory is slower, but only a small fraction of all possible product types are being produced at any point in time.
The problem is complex due to several factors. First, the search space is quite large: all possible sequences of all orders. Several hundred possible orders are considered for each schedule. Optimization involves several distinct per- formance measures, which can be inversely related. Eval- uating a schedule is costly; a simulation is used to deter- mine when enough of the needed product is available and how long it takes to move product from its starting loca- tion (warehouse or production line) to its transport (rail car or truck).
Search algorithms can be easily applied to warehouse scheduling. However, given the expense of schedule eval- uation and the number of possible schedules, knowledge- poor search algorithms may be too costly. Heuristic-based methods provide a promising alternative, as they explic- itly leverage domain knowledge to directly construct can- didate schedules.
To assess the trade-offs between search and heuristic methods, we compared a variety of standard optimization
techniques. These algorithms fall into three basic cat- egories: stochastic search, domain-based heuristics, and hybrid systems. We investigated three stochastic search techniques: a genetic algorithm and two local search oper- ators. We implemented our own order sequencing heuris- tic and used it in two different contexts for building sched- ules. First, it is used directly as a greedy construction procedure. Second, it is used as the heuristic compo- nent of Limited Discrepancy Search (LDS), a systematic AI search method that has performed well on synthetic test problems in the job shop scheduling domain. Hy- brid approaches combine the stochastic search methods (i.e., the genetic algorithm and the local search methods search techniques) with the heuristics: heuristically gen- erated solutions are used to initialize the stochastic search methods. We describe these approaches in more detail in Section III.
We compared the scheduling methods using three per- formance metrics: schedule makespan, average time to fill an order, and average total inventory (see Section II). The values for the performance metrics were obtained from a coarse-grain simulator we developed. We also developed a more detailed, fine grain simulator. The coarse-grain simulator was used as the objective function in our exper- iments because of the expense of the more detailed sim- ulation. While run-time was substantially reduced, the loss in granularity necessarily produced some inaccuracy in the performance measurements. We refer to the coarse- grained simulation as the “internal simulator” (since it is internal to the optimization procedure) and the detailed simulator as the “external simulator.”
We found that methods combining stochastic search with heuristic initialization significantly outperform heuristic-based methods, given equal amounts of compu- tation. Section IV provides detailed results. Furthermore, the globally motivated search of the genetic algorithm out- performs the local search algorithms. However, heuristic- based methods are not without merit; hybridization of the stochastic search algorithms with heuristic-based initial- ization further improves performance.
A key features of the Limited Discrepancy Search (LDS) is the use of backtracking to undo some number of heuris- tic decisions. We also find that the backtracking of LDS
fails to overcome the deficiencies of the greedy heuristic construction procedure for this particular domain.
The total number of evaluations is limited to 100,000 in our experiments. Thus, our conclusions may not gener- alize to situations where the number of total evaluations is different. We limited total evaluations for two reasons. First, this was done in order to limit total search time to a reasonable amount of time. Second, the largest improve- ments in the objective function appear to occur within the first 100,000 evaluations. Improvement is asymptotic after this point. Given that the fast internal simulator is weakly correlated with the detailed external simula- tor, it is unclear that further optimization with respect to the internal simulator actually translates into further improvement in the external simulator. We are currently investigating this question further.