一种求解不确定作业车间调度问题的随机仿真优化方法

王荪馨; 李言; 张燕荣; 淮文博

doi:10.13433/j.cnki.1003-8728.2015.0813

一种求解不确定作业车间调度问题的随机仿真优化方法

doi: 10.13433/j.cnki.1003-8728.2015.0813

1.
西安理工大学机械与精密仪器工程学院, 西安 710048;
2.
西安理工大学高等技术学院, 西安 710082

基金项目:

国家自然科学基金项目（51475366）资助

详细信息

作者简介:
王荪馨（1974-），副教授，博士研究生，研究方向为先进制造技术、智能优化调度方法，wsx8280@126.com

计量
- 文章访问数: 120
- HTML全文浏览量: 16
- PDF下载量: 5
- 被引次数: 0
出版历程
- 收稿日期: 2014-01-18
- 刊出日期: 2015-08-05

A Novel Stochastic Simulation Optimization Method in Solving Job Shop Scheduling Problem Under Processing Time Variability

1.
School of Mechanical and Precision Instrument Engineering, Xi'an University of Technology, Xi'an 710048, China;
2.
School of Technology, Xi'an University of Technology, Xi'an 710082, China

摘要

摘要: 针对以工件提前/拖期惩罚成本期望值最小化为目标函数、且工序加工时间不确定条件下的作业车间调度问题，将宽度-深度（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.
- breath vs. depth approach /
- job shop scheduling /
- simulation resource allocation /
- stochastic simulation /
- uncertain optimization

HTML全文

参考文献(9)

[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