DocumentCode :
1251650
Title :
Common issues in discrete optimization and discrete-event simulation
Author :
Jacobson, Sheldon H. ; Yücesan, Enver
Author_Institution :
Dept. of Mech. & Ind. Eng., Illinois Univ., Urbana, IL, USA
Volume :
47
Issue :
2
fYear :
2002
fDate :
2/1/2002 12:00:00 AM
Firstpage :
341
Lastpage :
345
Abstract :
This note studies and exploits common issues between discrete-event simulation models and algorithms for discrete optimization problems to prove that two discrete-event simulation search problems are NP-hard. More specifically, NEIGHBORHOOD seeks a sequence of events such that two distinct states can be accessed, one state after executing all but the last k events and another state after executing all the events, while INITIALIZE seeks a sequence of events such that executing the sequence with one particular initial event results in a particular state being reached, while for a second initial event, that particular state cannot be reached. Implications of these results for discrete-event simulation modeling and analysis (e.g., assessing when steady state, termination conditions have been reached, or optimal input parameters values for simulation optimization have been established) as well as for discrete optimization problems (e.g., assessing a priori the effectiveness of a neighborhood for simulated annealing or tabu search) are discussed
Keywords :
computational complexity; discrete event simulation; optimisation; search problems; INITIALIZE; NEIGHBORHOOD; NP-hard problems; discrete optimization; discrete-event simulation; search problems; Analytical models; Computational complexity; Computational modeling; Discrete event simulation; Industrial engineering; Jacobian matrices; Operations research; Search problems; Simulated annealing; Steady-state;
fLanguage :
English
Journal_Title :
Automatic Control, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9286
Type :
jour
DOI :
10.1109/9.983377
Filename :
983377
Link To Document :
بازگشت