Bad-scenario Set Based Risk-resisting Robust Scheduling Model
-
摘要: 讨论了场景描述的不确定环境下的鲁棒调度模型. 通过对传统不确定调度模型在追求优良性能的积极性和抗风险的保守性两方面对抗和均衡关系的透视和分析, 建立了一种新的鲁棒调度模型.该模型的优化目标由平衡因子将期望性能和抗风险鲁棒度量组合而成. 抗风险鲁棒度量基于坏场景集概念而定义,坏场景集中坏场景的数目可由一个基准性能来调节,当平衡因子或者基准性能变化时, 构成一族鲁棒调度模型.一系列的定理阐明了本文提出的鲁棒调度模型族与传统不确定调度模型之间的关系, 给出了该鲁棒调度模型有效的条件.仿真测试实验针对加工时间不确定的Job-shop调度问题进行, 计算结果表明新模型在追求优良性能的积极性和抵抗风险的鲁棒性方面相对传统模型具有了更好的全面性和综合性, 可以实现调度解在不同场景下的期望性能和抗风险鲁棒性的更好平衡.Abstract: We discuss robust scheduling models under uncertain environments described by scenario approach. Using the insights revealed by the analysis of traditional uncertain scheduling models involving the conflicting and balancing twofold relevance, which are the motivation of pursuing better performance and the conservatism of resisting risk, we establish a kind of new robust scheduling model. The optimization objective combines expected performance and robustness measure with a balance factor. A risk-resisting robustness measure is defined based on the concept of bad-scenario set, in which the number of bad scenarios can be adjusted by a standard performance. Thus, a set of robust scheduling models is established as the balance factor or the standard performance varies. A series of theorems reveal the relationship among the set of new models proposed in this paper and traditional uncertain scheduling models. And the condition of effectiveness of robustness for the set of new models is proposed as a theorem. Furthermore, an extensive experiment was conducted for job-shop scheduling problems with uncertain processing time. The computational results provide evidence that the set of new models is more comprehensive and more integrated in terms of pursuing better statistic performance and resisting the risk of performance deterioration. Thus, the new model can realize better balance between expected performance and risk-resisting robustness, as comparied against existing uncertain scheduling models.
-
Key words:
- Robust scheduling /
- bad scenario /
- resisting risk /
- expected performance /
- decision preference
-
[1] Herroelen W, Leus R. Project scheduling under uncertainty: survey and research potentials. European Journal of Operational Research, 2005, 165(2): 289-306[2] Kouvelis P, Yu D. Robust Discrete Optimization and Its Applications. Dordrecht: Kluwer Academic Publishers, 1997[3] Wang J. A fuzzy project scheduling approach to minimize schedule risk for product development. Fuzzy Sets and Systems, 2002, 127(2): 99-116[4] Yamashita D S, Armentano V A, Laguna M. Robust optimization models for project scheduling with resource availability cost. Journal of Scheduling, 2007, 10(1): 67-76[5] Assavapokee T, Realff M J, Ammons J C, Hong I H. Scenario relaxation algorithm for finite scenario-based min-max regret and min-max relative regret robust optimization. Computers and Operations Research, 2008, 35(6): 2093-2102[6] Murvey J M, Vanderbei R J, Zenios SA. Robust optimization of large-scale systems. Operations Research, 1995, 43(2): 264-281[7] Pinedo M. Minimizing the expected makespan in stochastic flow shops. Operations Research, 1982, 30(1): 148-162[8] Daniels R L, Kouvelis P. Robust scheduling to hedge against processing time uncertainty in single-stage production. Management Science, 1995, 41(2): 363-376[9] Kouvelis P, Daniels R L, Vairaktarakis G. Robust scheduling of a two-machine flow shop with uncertain processing times. IIE Transactions, 2000, 32(5): 421-432[10] Fisher H, Thompson G L. Probabilistic-learning combinations of local job-shop scheduling rules. Industrial Scheduling. New Jersey: Prentice-Hall, 1963. 225-251[11] Wang Ling. Shop Scheduling with Genetic Algorithms. Beijing: Tsinghua University Press, 2003. 158-162(王凌. 车间调度及其遗传算法. 北京:清华大学出版社, 2003. 158-162)[12] Wang L, Zheng D Z. An effective hybrid optimization strategy for job-shop scheduling problems. Computers and Operations Research, 2001, 28(6): 585-596
计量
- 文章访问数: 2203
- HTML全文浏览量: 51
- PDF下载量: 950
- 被引次数: 0