|
|
论文:2014,Vol:32,Issue(6):929-936 |
|
|
引用本文： |
|
|
肖世昌, 孙树栋, 杨宏安. 加工时间随机可控Job Shop前摄调度研究[J]. 西北工业大学学报 |
|
|
Xiao Shichang, Sun Shudong, Yang Hongan. Proactive Scheduling Research on Job Shop with Stochastically Controllable Processing Times[J]. Northwestern polytechnical university |
|
|
|
|
|
|
|
| 加工时间随机可控Job Shop前摄调度研究 |
|
| 肖世昌, 孙树栋, 杨宏安 |
|
| 西北工业大学 机电学院, 陕西 西安 710072 |
| 摘要: |
| 针对Job Shop环境中工序加工时间的不确定性,建立加工时间随机可控Job Shop调度问题随机模型。采用效率指标和鲁棒性指标对调度方案进行双目标评价。提出一种分层求解策略实现双目标优化,并采用嵌入最优计算量分配策略的遗传算法求解模型。仿真实验证明了所提出模型及优化算法的可行性。通过与直接采用均值-方差模型进行双目标优化得到的结果进行比较,证明了所提出的分层求解策略和算法可以获得综合性能更好的调度方案。 |
| 关键词:
随机模型
遗传算法
鲁棒性
jobshop
最优计算量分配
加工时间随机可控
|
|
| Proactive Scheduling Research on Job Shop with Stochastically Controllable Processing Times |
|
| Xiao Shichang, Sun Shudong, Yang Hongan |
|
| School of Mechanical Engineering, Northwestern Polytechnical University, Xi'an 710072, China |
| Abstract: |
| Aiming at the uncertainty caused by the randomness of the processing times in job shop,we propose thestochastic model of job shop scheduling problem with stochastically controllable processing times (SCPT-JSP). Weadopt a scheduling method that optimizes this problem with two objectives: (1) efficiency measure; (2) robustnessmeasure. To solve this dual-objective scheduling problem,we propose a two stage hierarchical strategy as well as asimulation based genetic algorithm (GA) in which optimal computing budget allocation is embedded. The feasibilityof the proposed model and the strategy and algorithm for solving the problem are proved with simulationexperiments. According to the comparison with the optimization results obtained with mean-variance model whichoptimize the dual-objective directly,we find that our hierarchical strategy and corresponding algorithm can obtainthe scheduling solution with superior comprehensive performance. |
| Key words:
stochastic model
genetic algorithm
robustness
job shop
optimal computing budget allocation
sto-chastically controllable processing times
|
|
| 收稿日期: 2014-04-16
修回日期:
|
| DOI: |
| 基金项目: 国家自然科学基金(51075337、51475383)资助 |
| 通讯作者:
Email： |
| 作者简介: 肖世昌(1987-)，西北工业大学博士研究生，主要从事生产调度优化及智能进化算法研究。
|
|
|
|
|
|
|
|
参考文献: |
|
|
[1] 陈雄,李海刚,吴启迪. 基于遗传算法的 Job-Shop 调度问题研究[J]. 同济大学学报,2002,30(1): 88-91Chen Xiong,Li Haigang,Wu Qidi. Study on Job-Shop Scheduling Problem Based on Genetic Algorithm[J]. Journal of TongjiUniversity,2002,30(1): 88-91 (in Chinese)
[2] 刘琦,顾幸生. 基于模糊规划的处理时间不确定条件下的 Job-Shop 问题[J]. 华东理工大学学报, 2001, 27(5): 442-450Liu Qi,Gu Xingsheng. A Kind of Job-Shop Schedule Problems with Uncertain Processing Time. Journal of East China Universityof Science and Technology,2001,27(5): 442-450 (in Chinese)
[3] Gu J W,Gu M Z,Cao CW,Gu XS. A Novel Competitive Co-Evolutionary Quantum Genetic Algorithm for Stochastic Job ShopScheduling Problem[J]. Computers and Operations Research,2010,37(5): 927-937
[4] Horng S C,Lin SY. Multi-Stage Ordinal Optimization Based Approach for Job Shop Scheduling Problems[J]. Applied Mathe-matics and Computation,2012,219 (3): 1125-1134
[5] Cowling P,Johansson M. Using Real Time Information for Effective Dynamic Scheduling. European Journal of Operational Re-search,2002,139(2): 230-244
[6] Smith S. Reactive Scheduling Systems ∥ Intelligent Scheduling Systems[M]. Brown D and Scherer W,Boston,KluwerPress,1995
[7] Zhang R,Song S J,Wu C. A Two-Stage Hybrid Particle Swarm Optimization Algorithm for the Stochastic Job Shop SchedulingProblem[J]. Knowledge-Based Systems,2012,27(3): 393-406
[8] Lei D M. Minimizing Makespan for Scheduling Stochastic Job Shop with Random Breakdown[J]. Applied Mathematics and Com-putation,2012,218(24): 11815-11858
[9] Horng S C,Lin S S. Evolutionary Algorithm for Stochastic Job Shop Scheduling with Random Processing Times[J]. Expert Sys-tems with Applications,2012,39(3): 3603-3610
[10] Leon V J,Wu S D,Storer R H. Robustness Measures and Robust Scheduling for Job Shops[J]. IIE Transactions,1994,26(5): 32-43
[11] Pinedo Michael L. Scheduling Theory,Algorithms,and Systems[M]. 4rd Ed,German,Springer,2012
[12] Herroelen W,Leus R. Project Scheduling under Uncertainty: Survey and Research Potentials[J]. European Journal of Opera-tional Research,2005,165(2): 289-306
[13] Goren S,Sabuncuoglu I. Optimization of Schedule Stability and Efficiency under Processing Times Variability and Random Ma-chine Breakdowns in a Job Shop Environment[J]. Naval Research Logistics,2011,59(1): 1-13
[14] VandeVonder S, Demeulemeester E, Herroelen W. Proactive Heuristic Procedures for Robust Project Scheduling: an Experimen-tal Analysis[J]. European Journal of Operational Research,2008,189 (3): 723-733
[15] 张映锋, 赵曦滨, 孙树栋等. 一种基于物联技术的制造执行系统实现方法与关键技术[J]. 计算机集成制造系统,2012,18(12): 2634-2642Zhang Yingfeng,Zhao Xibin,Sun Shudong,et al. Implementing Method and Key Technologies for IoT-Based Manufacturing Ex-ecution System[J]. Computer Integrated Manufacturing System,2012,18(12): 2634-2642 (in Chinese)
[16] Chen C H,Lin J W. Simulation Budget Allocation for Further Enhancing the Efficiency of Ordinal Optimization[J]. Discrete E-vent Dynamic Systems: Theory and Applications,2000,10 (3): 251-270
[17] 杨宏安,孙启峰,李锦远. 求解作业车间提前/拖期调度问题的一种新解码方法[J]. 计算机集成制造系统,2011,17(2): 2652-2659Yang Hongan,Sun Qifeng,Li Jinyuan. Novel Decoding Method for Job Shop Earliness and Tardiness Scheduling Problem[J].Computer Integrated Manufacturing Systems,2011,17(2): 2652 -2659 (in Chinese) |
|
|
|
|
|
|
|
