A Novel Stochastic Simulation Optimization Method in Solving Job Shop Scheduling Problem Under Processing Time Variability
-
摘要: 针对以工件提前/拖期惩罚成本期望值最小化为目标函数、且工序加工时间不确定条件下的作业车间调度问题,将宽度-深度(BD)仿真量全局优化分配机制嵌入至进化序优化(ESOO)算法框架的粗糙仿真评估阶段。宽度仿真量分配用以调整样本数量,并利用进化算法进行调度解的样本取样和迭代优化;而深度仿真量分配则是利用最优计算量分配技术,依据当前种群中个体的均值和方差进行仿真量的自适应分配。最后通过标准调度测试算例验证了ESOO-BD随机仿真优化方法的可行性和有效性。
-
关键词:
- 不确定优化问题 /
- 作业车间调度 /
- 随机仿真 /
- 仿真量分配 /
- 宽度-深度仿真量分配
Abstract: In this paper, a novel method of embedding breadth vs. depth simulation resource allocation mechanism into evolution algorithm with ordinal optimization, i.e. ESOO-BD, is proposed to solve a job shop scheduling problem under processing time variability (JSP-PTV) with the objective of minimizing the expected sum of earliness and tardiness penalties. In breadth vs. depth approach, a simulation allocation method that can dynamically allocate the computational resources to the search process and the performance evaluation process are introduced. Finally, the computational results on the benchmark instances show that the present method outperforms the existing method by achieving better solutions. -
[1] Pinedo M L. Scheduling: theory, algorithms, and systems[M]. 4 editior. Springer, 2012 [2] Sakawa M, Kubota R. Fuzzy programming for multi-objective job shop scheduling with fuzzy processing time and fuzzy due date through genetic algorithms[J]. European Journal of Operational Research, 2000,120:393-407 [3] Lei D M. Interval job shop scheduling problems[J]. International Journal of Advanced Manufacturing Technology, 2012,60(1-4):291-301 [4] 张国军,李婵娟,朱海平,等.不确定信息条件下Job-shop调度的混合智能算法[J].中国机械工程, 2007,18(16):1939-1942 Zhang G J, Li C J, Zhu H P, et al. A hybrid intelligent algorithm for job-shop scheduling under uncertain information environment[J]. China Mechanical Engineering,2007,18(16):1939-1942 (in Chinese) [5] Beck J C, Wilson N. Proactive algorithms for job shop scheduling with probabilistic durations[J]. Journal of Artificial Intelligence Research, 2007,28:183-232 [6] Horng S C, Lin S S, Yang F Y. Evolutionary algorithm for stochastic job shop scheduling with random processing time[J]. Expert Systems with Applications, 2012,39(3):3603-3610 [7] Ho Y C, Sreenivas R S. Ordinal optimization of DEDS[J]. Discrete Event Dynamic Systems: Theory and Applications, 1992,2(1):61-88 [8] Yang H A, Lü Y Y, Xia C K, et al. Optimal computing budget allocation for ordinal optimization in solving stochastic job shop scheduling problems[J]. Mathematical Problems in Engineering, 2014, Article ID 619254 [9] Lin X, Lee L H. A new approach to discrete stochastic optimization problems[J]. European Journal of Operational Research, 2006,172:761-782
点击查看大图
计量
- 文章访问数: 145
- HTML全文浏览量: 29
- PDF下载量: 7
- 被引次数: 0