Artificial intelligence search methods for multi-machine two-stage scheduling with due date penalty, inventory, and machining costs

摘要

This paper evaluates artificial intelligence search methods for multi-machine two-stage scheduling prob- lems with due date penalty, inventory, and machining costs. We compare four search methods : tabu search, simulated annealing, genetic algorithm, and neighborhood search. Computational results show that the tabu search performs best in terms of solution quality. The tabu search also requires much less computational time than the genetic algorithm and simulated annealing. As expected, the neighborhood search needs the smallest computational time, but gives the worst solution quality. To further improve the solution quality and computational time, this paper proposes a two-phase tabu search. The two-phase tabu search sequentially addresses two aspects of sequencing for the same problem, order- and component-based sequencing. The order-based tabu search identifies a sequence for customers' orders. Starting from the sequence identified for customers' orders, the component-based tabu search fine-tunes the sequence for components produced at the fabrication stage. The results show that the two-phase tabu search is better in solution quality and computational time than the one-phase tabu search. The difference in solution quality is more pronounced at the early stage of the search.