A Metaheuristic Algorithm for Simultaneous Simulation Optimization and Applications to Traveling Salesman and Job Shop Scheduling with Due Dateshop Scheduling with Due Dates

   page       BibTeX_logo.png   
George Jiri Mejtsky
Shane G. Henderson, Bahar Biller, Ming-Hua Hsieh, John Shortle, Jeff Tew, Russel Barton (eds.)
2007 Winter Simulation Conference, pages 1835 -1843
9-12 December 2007

We describe a metaheuristic algorithm for simulation optimization. Traditionally, discrete event simulation optimization is carried out by multiple simulation runs executed sequentially. At the end of each simulation run, the run is evaluated (using model output - black box approach) by an objective function. If we carry out simulation runs simultaneously, then we can evaluate (using model internal data - white box approach) different simulation runs during their execution before the end is reached. Thus, we can eliminate the inferior runs early and allow only the most promising runs to continue to the end. We explore this parallel competition of simulation models on a single processor computer. Applications of the algorithm to traveling salesman and job shop scheduling problems are presented. In conclusion, our results suggest that the algorithm is a suitable approach for solving some combinatorial problems, and it represents a promising "nonsequential" avenue for simulation optimization.

keywordscombinatorial problems;discrete event simulation optimization;job shop scheduling;metaheuristic algorithm;simultaneous simulation optimization;traveling salesman;job shop scheduling;travelling salesman problems;