×

The impact of approximate evaluation on the performance of search algorithms for warehouse scheduling. (English) Zbl 0973.90036

Summary: The Coors warehouse scheduling problem involves finding a permutation of customer orders that minimizes the average time that customers’ orders spend at the loading docks while at the same time minimizing the running average inventory, search-based solutions require fast objective functions. Thus, a fast low-resolution simulation is used as an objective function. A slower high-resolution simulation is used to validate solutions. We compare the performance of a constructive scheduling algorithm to a genetic algorithm and local search approach. The constructive algorithm is based on a heuristic built specifically for this application. We also tested a hybrid of the genetic algorithm and local search approaches by initializing the search using the domain-specific heuristic. This hybrid genetic algorithm was able to find the best solutions when evaluated by the high-resolution simulation. Finally, we consider the effect of using the high-resolution simulation to filter a set of solutions found by the different approaches.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
90B40 Search theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] and , ’Slack-based heuristics for constraint satisfaction scheduling’, Proc. 11th National Conf. on Artificial Intelligence, 1993.
[4] ’Systematic and nonsystematic search strategies’, Artificial Intelligence Planning Systems: Proc. 1st Int. Conf., 1992.
[5] and , ’Limited discrepancy search’, Proc. 14th Int. Joint Conf. on Artificial Intelligence, 1995.
[8] ’Job shop scheduling with genetic algorithms’, in J. Grefenstette (ed.), Int. Conf. on GAs and Their Applications, 1985, pp. 136-140.
[9] , and , ’Exploring problem-specific recombination operators for job shop scheduling’, in and (eds.), Proc. 4th Int. Conf. on GAs, Morgan Kaufmann, Los Altos, CA, 1991, pp. 10-17.
[11] and , ’A heuristic combination method for solving job-shop scheduling problems’, Parallel Problem Solving from Nature-PPSNV, 1998.
[12] and , ’A hybrid genetic algorithm for university timetabling’, in (ed.), Proc. 6th Int. Conf. on GAs, Morgan Kaufmann, Los Altos, CA, 1995.
[13] ’Evolutionary approaches to the partition/timetabling problem’, in and (ed.), Artificial Neural Nets and Genetic Algorithms (ICANNGA-978), Springer, Berlin, 1988, pp. 281-288.
[14] and , ’The Application of genetic algorithms to resource scheduling’, in and (eds.), Proc. 4th Int. Conf. on GAs, Morgan Kaufmann, Los Altos, CA, 1991.
[15] , and , ’A genetic algorithm hybrid for hierarchical reactive scheduling’, Proc. 7th Int. Conf. on Genetic Algorithms, 1997.
[16] and , ’A distributed ga for employee staffing and scheduling’, Proc. 5th Int. Conf. on Genetic Algorithms, 1993.
[17] and , ’The state of the art in evolutionary approaches to timetabling and scheduling’, http://www.dai.ed.ac.uk/daidb/people/homes/emmah/evonet.html, 1993.
[19] , and , ’Comparing heuristic, evolutionary and local search approaches to scheduling’, in (ed.), Proc. 3rd Int. Conf. on Artificial Intelligence Planning Systems, Menlo Park, CA, May 1996, The AAAI Press.
[20] and , ’A genetic algorithm for scheduling with resource consumption’, in and (eds.), New Directions for Operations Research in Manufacturing, Springer, New York, 1992, pp. 129-148.
[21] and , ’Expected solution quality’, Proc. 14th Int. Joint Conf. on Artificial Intelligence, 1995.
[22] , and , ’Texture-based heuristics for scheduling revisited’, Proc. National Conf on Artificial Intelligence (AAAI-97), 1997.
[23] and , ’Applying constraint satisfaction techniques to job shop scheduling’, Technical Report, The Robotics Institute, Carnegie Mellon University, 1995.
[24] ’The GENITOR algorithm and selective pressure: why rank based allocation of reproductive trials is best’, in (ed.), Proc. 3rd Int. Conf. on GAs, Morgan Kaufmann, Los Altos, CA, 1989, pp. 116-121.
[25] Handbook of Genetic Algorithms, Van Nostrand Reinhold, New York, 1991.
[26] Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, Reading, MA, 1989. · Zbl 0721.68056
[27] ’Schedule optimization using genetic algorithms’, in (ed.), Handbook of Genetic Algorithms, Chapter 21, Van Nostrand Reinhold, New York, 1991.
[28] and , ’Modeling permutation encodings in simple genetic algorithm’, in and (eds.), FOGA-3, Morgan Kaufmann, Los Altos, CA, 1995.
[30] and , ’Searching in the presence of noise’, in H. M. Voigt, W. Ebeling, I. Rechenberg and H. P. Schwefel (eds.), Parallel Problem Solving from Nature, 6, Berlin, Germany, 1996, pp. 198-207.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.