Abstract: Since processing times are usually uncertain in discrete manufacturing industry, it is hard to implement production schedules as planned. The robust scheduling of two-stage flow shop with interval processing times is studied, which aims to solve robust schedules conformed to the Min-Max decision rule. The corresponding original scheduling problem is to minimize total completion times. Firstly, the robust scheduling problem is modeled as a semi-infinite programming formulation. Secondly, three theorems are proved and a hybrid algorithm is provided to combine branch-bound method and genetic algorithm, which contribute to solve the problem effectively and efficiently. At last, a computational experiment is conducted to illustrate the robust scheduling problem that can be solved through the modeling method and the hybrid algorithm proposed in this paper.

Key words: robust scheduling, two-stage flow shop, Min-Max decision rule, total completion times, branch and bound-genetic hybrid algorithm

摘要： 离散制造业中加工时间不确定的现象普遍存在，使得生产过程往往难以按照既定的调度方案来执行，而且难以实现满意的生产效果。研究在加工时间为区间数的环境下，以总完工时间为调度目标的两台机器流水生产鲁棒调度问题，旨在求解Min-Max准则的鲁棒调度方案。在详细描述该流水生产鲁棒调度问题的基础上，建立了问题的半无限数学规划模型。为降低求解复杂性，证明了问题的简化性质和占优性质，并设计了用于求解该问题的分支定界-遗传混合算法。仿真实验表明，提出的方法对该鲁棒调度问题具有很好的适用性。

关键词: 鲁棒调度, 两阶段流水生产, Min-Max准则, 总完工时间, 分支定界-遗传混合算法