【摘要】 在实际工业生产中,调度环境的复杂性与不确定性使得调度问题求解难度大大提高.针对加工时间不确定的柔性作业车间调度问题,采用不确定参数描述随机工时波动程度和约束条件允许违背程度,构建工时波动服从指数分布的多目标柔性车间调度模型.基于机会约束规划理论,将不确定调度问题转化为加工时间确定的柔性作业车间调度问题,求解得到一定程度上具有鲁棒性能的调度方案.在执行过程中,采用工序移动调整和重调度方法对作业排产方案进行动态调整.基于双链式编码以及贪婪插入法解码规则,提出了基于变邻域搜索的混合NSGA-Ⅱ算法.针对车间调度问题的多约束性和计算复杂度高等特点,设计了基于机器选择的复合启发式规则,包括依据概率的最小累计机器负载和最短工序加工时间规则,以获取更加接近Pareto前沿的均匀分布初始种群.采用改进工序和设备交叉策略以提高算法的全局搜索能力.此外,基于关键工序和机器选择的多种邻域结构,设计了变邻域搜索策略,以进一步提高算法的局部搜索能力.通过Kacem和Brandimarte标准算例的数值仿真以及与多种代表算法的统计比较,验证了所提算法的有效性.本文所提算法为不确定柔性作业车间调度问题提供了更优的调度方案.更多还原

【Abstract】 In practical industrial production, the complexity and uncertainty of the scheduling environment greatly increase the difficulty in solving the scheduling problem. To resolve the flexible job shop scheduling problem with uncertain processing time, two uncertain parameters are used to describe the fluctuation degree of random processing time and the allowable degree of constraint violation. In addition, a multi-objective flexible job shop scheduling mathematical model is constructed, the processing time fluctuation of which obeys exponential distribution. Based on the chance-constrained programming theory, the uncertain scheduling problem is transformed into a flexible job shop scheduling problem with a determined processing time, and a scheduling scheme with robust performance(to a certain extent) is obtained. During its execution, the process movement adjustment and rescheduling methods are used to dynamically adjust the job scheduling plan. Based on the double-chain coding and greedy insertion method decoding rules, a hybrid variable neighborhood search NSGAII algorithm is proposed. Aiming at the multiple constraints and high computational complexity of job shop scheduling problems, a compound heuristic rule based on machine selection is designed to obtain an initial population with uniform distribution, which is closer to the Pareto frontier, including the rules of minimum cumulative machine load and shortest processing time according to probability. In addition, the improved operation and equipment intersection strategy is adopted to improve the global search ability of the algorithm.Further, a variable neighborhood search strategy is designed based on several neighborhood structures selected by key processes and machines to further improve the local search ability of the algorithm. Through the numerical simulation of Kacem and Brandimarte standard instances and the statistical comparison with various representative algorithms, the effectiveness of the proposed algorithm is verified, and a better scheduling scheme is provided for the uncertain flexible job shop scheduling problem.更多还原