Abstract: To improve the feasibility of scheduling and ensure the stability of production processes,a robust optimization approach was proposed to address flexible job shop scheduling problem under stochastic processing times.After introducing two uncertain parameters to describe the degree of disturbance volatility and allowable constraints violence respectively,the generalized robust optimization framework for common linear programming problems was formulated,in which the stochastic variables were expressed as probability distributions.Consequently,the intractable problem of scheduling stochastic flexible job shops was reformulated into its deterministic robust counterpart model.Based on this model,a robust optimization algorithm was developed to make double decisions concurrently on operation sequences and machine assignments by formulating a fitness function with stochastic processing times and combining the global optimization of genetic evolution and the local improvement of neighborhood search.Experimental results showed that the proposed approach could obtain the optimal solution within 95% confidence level in a short computational time and at reasonable productivity loss.

Key words: flexible job shop, robust counterpart model, genetic algorithms, neighborhood search

摘要： 为了提高柔性加工车间调度方案的可行性、保障生产过程的稳定性,提出一种鲁棒优化调度方法。引入两个不确定参数来描述随机工时的波动程度和约束条件的允许违背程度,提出随机变量服从概率分布时一般线性规划问题的鲁棒优化方法。采用该方法将含随机工时而难以求解的随机型柔性加工车间调度模型转化为确定型鲁棒对等模型。基于该模型,将随机工时融入适应度函数中,结合遗传进化的全局优化和邻域搜索的空间拓展能力研制出鲁棒调度算法,同步实现工件排序和机器分配的双重决策。案例测试表明,所提方法可以在较短计算时间内、以较小性能损失、将近95%的置信度获得当前最优解。

关键词: 柔性加工车间, 鲁棒对等模型, 遗传算法, 邻域搜索